Fast sequence clustering using a suffix array algorithm |
| |
Authors: | Malde Ketil Coward Eivind Jonassen Inge |
| |
Affiliation: | Department of Informatics, University of Bergen, HIB, N5020 Norway. ketil@ii.uib.no |
| |
Abstract: | MOTIVATION: 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. AVAILABILITY: The source code for the prototype implementation is available under a GPL license from http://www.ii.uib.no/~ketil/bio/. |
| |
Keywords: | |
本文献已被 PubMed Oxford 等数据库收录! |
|