A parallel computational framework for ultra-large-scale sequence clustering analysis
Wei Zheng, Qi Mao, Robert J. Genco et al. · Bioinformatics · 2018
Motivation: The rapid development of sequencing technology has led to an explosive accumulation of genomic data. Clustering is often the first step to be performed in sequence analysis. However, existing methods scale poorly with respect to the unprecedented growth of input data size. As high-performance computing systems are becoming widely accessible, it is highly desired that a clustering method can easily scale to handle large-scale sequence datasets by leveraging the power of parallel computing. Results: In this paper, we introduce SLAD (Separation via Landmark-based Active Divisive clustering), a generic computational framework that can be used to parallelize various de novo operational taxonomic unit (OTU) picking methods and comes with theoretical guarantees on both accuracy and efficiency. The proposed framework was implemented on Apache Spark, which allows for easy and efficient utilization of parallel computing resources. Experiments performed on various datasets demonstrated that SLAD can significantly speed up a number of popular de novo OTU picking methods and meanwhile maintains the same level of accuracy. In particular, the experiment on the Earth Microbiome Project dataset (∼2.2B reads, 437 GB) demonstrated the excellent scalability of the proposed method. Availability and implementation: Open-source software for the proposed method is freely available at https://www.acsu.buffalo.edu/~yijunsun/lab/SLAD.html. Supplementary information: Supplementary data are available at Bioinformatics online.
Cited by 10 works. doi:10.1093/bioinformatics/bty617 Open-access PDF
Authors
References
- QIIME allows analysis of high-throughput community sequencing data
- Search and clustering orders of magnitude faster than BLAST
- Cd-hit: a fast program for clustering and comparing large sets of protein or nucleotide sequences
- A tutorial on spectral clustering
- Introducing DOTUR, a Computer Program for Defining Operational Taxonomic Units and Estimating Species Richness
- An improved Greengenes taxonomy with explicit ranks for ecological and evolutionary analyses of bacteria and archaea
- MLlib: Machine Learning in Apache Spark
- ESPRIT: estimating species richness using large collections of 16S rRNA pyrosequences
- The Human Oral Microbiome Database: a web accessible resource for investigating oral microbe taxonomic and genomic information
- Assessing and Improving Methods Used in Operational Taxonomic Unit-Based Approaches for 16S rRNA Gene Sequence Analysis