k-link EST clustering: evaluating error introduced by chimeric sequences under different degrees of linkage.
BACKGROUND
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.


BACKGROUND
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++.
Bragg
Lauren M
LM
CSIRO Mathematical and Information Sciences, North Ryde, NSW, Australia. lauren.bragg@csiro.au
Stone
Glenn
G
D000465:Algorithms; D001483:Base Sequence; D016000:Cluster Analysis; D019295:Computational Biology / Q000379:methods*; D020224:Expressed Sequence Tags; D012984:Software