6533b81ffe1ef96bd1278ec4
RESEARCH PRODUCT
Fast dendrogram-based OTU clustering using sequence embedding
Bertil SchmidtChee Keong KwohThuy-diem Nguyensubject
Brown clusteringCURE data clustering algorithmSingle-linkage clusteringCorrelation clusteringCanopy clustering algorithmData miningBiologyHierarchical clustering of networksCluster analysiscomputer.software_genrecomputerHierarchical clusteringdescription
Biodiversity assessment is an important step in a metagenomic processing pipeline. The biodiversity of a microbial metagenome is often estimated by grouping its 16S rRNA reads into operational taxonomic units or OTUs. These metagenomic datasets are typically large and hence require effective yet accurate computational methods for processing.In this paper, we introduce a new hierarchical clustering method called CRiSPy-Embed which aims to produce high-quality clustering results at a low computational cost. We tackle two computational issues of the current OTU hierarchical clustering approach: (1) the compute-intensive sequence alignment operation for building the distance matrix and (2) the quadratic memory requirement of the clustering procedure.Our performance evaluation shows that CRiSPy-Embed achieves higher efficiency in terms of both runtime and memory consumption in comparison to existing dendrogram-based approaches. Furthermore, to obtain the final OTU grouping, CRiSPy-Embed dynamically determines a natural cutoff of the dendrogram. With this strategy, CRiSPy-Embed achieves better and more robust clustering outcomes compared to other notable OTU clustering pipelines.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2014-09-20 | Proceedings of the 5th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics |