Fast embedding methods for clustering tens of thousands of sequences.
Most sequence clustering methods require a full distance matrix to be computed between all pairs of sequences. This requires computer memory and time proportional to N(2) for N sequences. For small N or say up to 10000 or so, this can be accomplished in reasonable times for sequences of moderate length. For very large N, however, this becomes increasingly prohibitive. In this paper, we have tested variations on a class of published embedding methods that have been designed for clustering large numbers of complex objects where the individual distance calculations are expensive. These methods involve embedding the sequences in a space where the similarities within a set of sequences can be closely approximated without having to compute all pair-wise distances. We show how this approach greatly reduces computation time and memory requirements for clustering large numbers of sequences and demonstrate the quality of the clusterings by benchmarking them as guide trees for multiple alignments. Source code is available on request from the authors.
Blackshields
Gordon
G
UCD Conway Institute of Biomolecular and Biomedical Sciences, University College Dublin, Dublin 4, Ireland. Gordon.blackshields@ucd.ie
Larkin
Mark
M
Wallace
Iain M
IM
Wilm
Andreas
A
Higgins
Desmond G
DG
D000465:Algorithms; D000595:Amino Acid Sequence; D016000:Cluster Analysis; D030562:Databases, Protein; D008969:Molecular Sequence Data; D011506:Proteins / Q000737:chemistry* / Q000235:genetics; D016415:Sequence Alignment / Q000379:methods*; D017386:Sequence Homology, Amino Acid; D013997:Time Factors
D011506:Proteins