Fast sequence clustering using a suffix array algorithm

Motivation: Efficient clustering is important for handling the large amount of available EST sequences. Most con-temporary 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 pre-sented. Sub-quadratic time complexity is achieved by using an algorithm based on suffix arrays. A prototype implementation has been developed and run on a bench-mark 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 implemen-tation is available under a GPL license fro