k-link EST clustering: evaluating error introduced by chimeric sequences under different degrees of linkage

• Published in: Bioinformatics 2009-09, Vol.25 (18), p.2302-2308
• Main Authors: Bragg, Lauren M., Stone, Glenn
• Format: Article
• Language: English
• Subjects: Algorithms; Base Sequence; Biological and medical sciences; Cluster Analysis; Computational Biology - methods; Expressed Sequence Tags; Fundamental and applied biological sciences. Psychology; General aspects; Mathematics in biology. Statistical analysis. Models. Metrology. Data processing in biology (general aspects); Original Papers; Software
• ISSN: 1367-4803; 1460-2059; 1367-4811
• DOI: 10.1093/bioinformatics/btp410

Motivation: The clustering of expressed sequence tags (ESTs) is a crucial step in many sequence analysis studies that require a high level of redundancy. Chimeric sequences, while uncommon, can make achieving the optimal EST clustering a challenge. Single-linkage algorithms are particularly vulnerable to the effects of chimeras. To avoid chimera-facilitated erroneous merges, researchers using single-linkage algorithms are forced to use stringent sequence–similarity thresholds. Such thresholds reduce the sensitivity of the clustering algorithm. Results: We introduce the concept of k-link clustering for EST data. We evaluate how clustering error rates vary over a range of linkage thresholds. Using k-link, we show that Type II error decreases in response to increasing the number of shared ESTs (ie. links) required. We observe a base level of Type II error likely caused by the presence of unmasked low-complexity or repetitive sequence. We find that Type I error increases gradually with increased linkage. To minimize the Type I error introduced by increased linkage requirements, we propose an extension to k-link which modifies the required number of links with respect to the size of clusters being compared. Availability: The implementation of k-link is available under the terms of the GPL from http://www.bioinformatics.csiro.au/products.shtml. k-link is licensed under the GNU General Public License, and can be downloaded from http://www.bioinformatics.csiro.au/products.shtml. k-link is written in C++. Contact: [e-mail] Supplementary information: Supplementary data are available at Bioinformatics online.