NDLI: Efficient and Accurate OTU Clustering with GPU-Based Sequence Alignment and Dynamic Dendrogram Cutting

Content Provider	IEEE Xplore Digital Library
Author	Thuy-Diem Nguyen Schmidt, B. Zejun Zheng Chee-Keong Kwoh
Copyright Year	2004
Abstract	De novo clustering is a popular technique to perform taxonomic profiling of a microbial community by grouping 16S rRNA amplicon reads into operational taxonomic units (OTUs). In this work, we introduce a new dendrogram-based OTU clustering pipeline called CRiSPy. The key idea used in CRiSPy to improve clustering accuracy is the application of an anomaly detection technique to obtain a dynamic distance cutoff instead of using the de facto value of 97 percent sequence similarity as in most existing OTU clustering pipelines. This technique works by detecting an abrupt change in the merging heights of a dendrogram. To produce the output dendrograms, CRiSPy employs the OTU hierarchical clustering approach that is computed on a genetic distance matrix derived from an all-against-all read comparison by pairwise sequence alignment. However, most existing dendrogram-based tools have difficulty processing datasets larger than 10,000 unique reads due to high computational complexity. We address this difficulty by developing two efficient algorithms for CRiSPy: a compute-efficient GPU-accelerated parallel algorithm for pairwise distance matrix computation and a memory-efficient hierarchical clustering algorithm. Our experiments on various datasets with distinct attributes show that CRiSPy is able to produce more accurate OTU groupings than most OTU clustering applications.
Sponsorship	IEEE Computer Society
Starting Page	1060
Ending Page	1073
Page Count	14
File Size	1790741
File Format	PDF
ISSN	15455963
Volume Number	12
Issue Number	5
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-09-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Graphics processing units Genetics Sparse matrices Bioinformatics Clustering algorithms Computational biology GPU-accelerated distance matrix computation OTU clustering hierarchical clustering dynamic dendrogram cutting
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Genetics Biotechnology

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A Family of Bit-Representation-Optimized Formats for Fast Sparse Matrix-Vector Multiplication on the GPU

GPU-Accelerated Finite-Element Matrix Generation for Lossless, Lossy, and Tensor Media [EM Programmer's Notebook]

A Performance Modeling and Optimization Analysis Tool for Sparse Matrix-Vector Multiplication on GPUs

Two Efficient Algorithms for Approximately Orthogonal Nonnegative Matrix Factorization

GPU accelerated greedy algorithms for compressed sensing

Performance Analysis and Optimization for SpMV on GPU Using Probabilistic Modeling

GPU-Accelerated Parallel Sparse LU Factorization Method for Fast Circuit Analysis

Computational aspects of GPU - accelerated sparse matrix - vector multiplication for solving Markov models

CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment

Efficient and Accurate OTU Clustering with GPU-Based Sequence Alignment and Dynamic Dendrogram Cutting

Similar Documents

A Family of Bit-Representation-Optimized Formats for Fast Sparse Matrix-Vector Multiplication on the GPU

GPU-Accelerated Finite-Element Matrix Generation for Lossless, Lossy, and Tensor Media [EM Programmer's Notebook]

A Performance Modeling and Optimization Analysis Tool for Sparse Matrix-Vector Multiplication on GPUs

Two Efficient Algorithms for Approximately Orthogonal Nonnegative Matrix Factorization

GPU accelerated greedy algorithms for compressed sensing

Performance Analysis and Optimization for SpMV on GPU Using Probabilistic Modeling

GPU-Accelerated Parallel Sparse LU Factorization Method for Fast Circuit Analysis

Computational aspects of GPU - accelerated sparse matrix - vector multiplication for solving Markov models

CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment

Efficient and Accurate OTU Clustering with GPU-Based Sequence Alignment and Dynamic Dendrogram Cutting