title: Fast sequence clustering using a suffix array algorithm.
abstract: 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/.
authors.affiliation: Department of Informatics, University of Bergen, HIB, N5020 Norway. ketil@ii.uib.no
authors.forename: Ketil
authors.initials: K
authors.lastname: Malde
authors.forename: Eivind
authors.initials: E
authors.lastname: Coward
authors.forename: Inge
authors.initials: I
authors.lastname: Jonassen
mesh_terms: 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