Fast sequence clustering using a suffix array algorithm.
BACKGROUND
Efficient clustering is important for handling the large amount of available EST sequences. Most contemporary methods are based on some kind of all-against-all comparison, resulting in a quadratic time complexity. A different approach is needed to keep up with the rapid growth of EST data.


RESULTS
A new, fast EST clustering algorithm is presented. Sub-quadratic time complexity is achieved by using an algorithm based on suffix arrays. A prototype implementation has been developed and run on a benchmark data set. The produced clusterings are validated by comparing them to clusterings produced by other methods, and the results are quite promising.


BACKGROUND
The source code for the prototype implementation is available under a GPL license from http://www.ii.uib.no/~ketil/bio/.
Malde
Ketil
K
Department of Informatics, University of Bergen, HIB, N5020 Norway. ketil@ii.uib.no
Coward
Eivind
E
Jonassen
Inge
I
D000465:Algorithms; D016000:Cluster Analysis; D020224:Expressed Sequence Tags; D020869:Gene Expression Profiling / Q000379:methods*; D010363:Pattern Recognition, Automated; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods*; D017421:Sequence Analysis / Q000379:methods*; D017385:Sequence Homology