Paper Info
Title
DACIDR: deterministic annealed clustering with interpolative dimension reduction using a large collection of 16S rRNA sequences
Abstract
The recent advance in next generation sequencing (NGS) techniques has enabled the direct analysis of the genetic information within a whole microbial community, bypassing the culturing individual microbial species in the lab. One can profile the marker genes of 16S rRNA encoded in the sample through the amplification of highly variable regions in the genes and sequencing of them by using Roche/454 sequencers to generate half to a few millions of 16S rRNA fragments of about 400 base pairs. The main computational challenge of analyzing such data is to group these sequences into operational taxonomic units (OTUs). Common clustering algorithms (such as hierarchical clustering) require quadratic space and time complexity that makes them not suitable for large datasets with millions of sequences. An alternative is to use greedy heuristic clustering methods (such as CD-HIT and UCLUST); although these enable fast sequence analyzing, the hard-cutoff similarity threshold set for them and the random starting seeds can result in reduced accuracy and overestimation (too many clusters). In this paper, we propose DACIDR: a parallel sequence clustering and visualization pipeline, which can address the overestimation problem along with space and time complexity issues as well as giving robust result. The pipeline starts with a parallel pairwise sequence alignment analysis followed by a deterministic annealing method for both clustering and dimension reduction. No explicit similarity threshold is needed with the process of clustering. Experiments with our system also proved the quadratic time and space complexity issue could be solved with a novel heuristic method called Sample Sequence Partition Tree (SSP-Tree), which allowed us to interpolate millions of sequences with sub-quadratic time and linear space requirement. Furthermore, SSP-Tree can enhance the speed of fine-tuning on the existing result, which made it possible to recursive clustering to achieve accurate local results. Our experiments showed that DACIDR produced a more reliable result than two popular greedy heuristic clustering methods.
Year
DOI
Venue
2012
10.1145/2382936.2382978
BCB
Keywords
Field
DocType
parallel sequence clustering,interpolative dimension reduction,deterministic annealed clustering,hierarchical clustering,existing result,rrna sequence,large collection,robust result,accurate local result,quadratic time,common clustering algorithm,linear space requirement,quadratic space,reliable result,interpolation,exploratory data analysis,multidimensional scaling
Sequence clustering,Fuzzy clustering,Data mining,CURE data clustering algorithm,Data stream clustering,Correlation clustering,Algorithm,Constrained clustering,Cluster analysis,Mathematics,Single-linkage clustering
Conference
Citations 
PageRank 
References 
6
0.50
10
Authors
7
Name
Order
Citations
PageRank
Yang Ruan11126.26
Saliya Ekanayake2909.34
Mina Rho3342.62
Haixu Tang468396.67
Seung-Hee Bae557131.67
Judy Qiu674343.25
Geoffrey Fox74070575.38