title: A grammar-based distance metric enables fast and accurate clustering of large sets of 16S sequences.
abstract: BACKGROUND
  We propose a sequence clustering algorithm and compare the partition quality and execution time of the proposed algorithm with those of a popular existing algorithm. The proposed clustering algorithm uses a grammar-based distance metric to determine partitioning for a set of biological sequences. The algorithm performs clustering in which new sequences are compared with cluster-representative sequences to determine membership. If comparison fails to identify a suitable cluster, a new cluster is created.
  
  
  RESULTS
  The performance of the proposed algorithm is validated via comparison to the popular DNA/RNA sequence clustering approach, CD-HIT-EST, and to the recently developed algorithm, UCLUST, using two different sets of 16S rDNA sequences from 2,255 genera. The proposed algorithm maintains a comparable CPU execution time with that of CD-HIT-EST which is much slower than UCLUST, and has successfully generated clusters with higher statistical accuracy than both CD-HIT-EST and UCLUST. The validation results are especially striking for large datasets.
  
  
  CONCLUSIONS
  We introduce a fast and accurate clustering algorithm that relies on a grammar-based sequence distance. Its statistical clustering quality is validated by clustering large datasets containing 16S rDNA sequences.
authors.affiliation: Department of Electrical Engineering, University of Nebraska-Lincoln, 209N WSEC, Lincoln, NE 68588-0511, USA. drussell@engr.unl.edu
authors.forename: David J
authors.initials: DJ
authors.lastname: Russell
authors.forename: Samuel F
authors.initials: SF
authors.lastname: Way
authors.forename: Andrew K
authors.initials: AK
authors.lastname: Benson
authors.forename: Khalid
authors.initials: K
authors.lastname: Sayood
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D016000:Cluster Analysis; D012336:RNA, Ribosomal, 16S / Q000032:analysis*; D017423:Sequence Analysis, RNA / Q000379:methods*
chemical_list: D012336:RNA, Ribosomal, 16S