A grammar-based distance metric enables fast and accurate clustering of large sets of 16S sequences

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. Th...

Full description

Saved in:
Bibliographic Details
Published in:BMC bioinformatics 2010-12, Vol.11 (1), p.601-601, Article 601
Main Authors: Russell, David J, Way, Samuel F, Benson, Andrew K, Sayood, Khalid
Format: Article
Language:English
Subjects:
Algorithms
Base Sequence
Cluster Analysis
Deoxyribonucleic acid
DNA
Grammar
Heuristic programming
Information management
Methodology
Methods
Nucleotide sequencing
RNA, Ribosomal, 16S - analysis
Sequence Analysis, RNA - methods
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. 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. 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.
ISSN:1471-2105
1471-2105
DOI:10.1186/1471-2105-11-601