TY - JOUR
T1 - PuzzleCluster
T2 - A novel unsupervised clustering algorithm for binning DNA fragments in metagenomics
AU - Siege, Kyler
AU - Altenburger, Kristen
AU - Hon, Yu Sing
AU - Lin, Jessey
AU - Yu, Chenglong
PY - 2015
Y1 - 2015
N2 - Metagenomic datasets are composed of DNA fragments from large numbers of different and potentially novel organisms. These datasets can contain up to several million sequences taken from heterogeneous populations of extremely varied abundance. Unlike traditional genomic studies, metagenomic analysis requires an additional binning step. This process groups DNA fragments from the same or similar species of origin. However, existing unsupervised metagenomic binning programs cannot accurately analyze datasets containing a large number of species or with significantly unbalanced abundance ratios. To improve upon these current limitations, we present PuzzleCluster, a novel unsupervised binning algorithm. PuzzleCluster incorporates a unique cluster refinement step by automatically grouping reads which share a nucleotide word (i.e. reverse complement pairs) of a predetermined length. Additionally, the clustering parameters are estimated by fitting the Jensen-Shannon distance among sequences using the expectation maximization algorithm. Since clustering parameters are computed based on each dataset, our approach can adapt to the peculiarities of each dataset and is not confined by universal parameters. Furthermore, PuzzleCluster utilizes no prior assumptions about the genetic makeup or number of organisms present in the sample, making it well-suited for applications with a large amount of biodiversity and completely unknown organisms. As a comparison, PuzzleCluster has an accuracy 9%, 19.8%, 15.7%, and 19.5% higher than MetaCluster 3.0 for taxonomic levels phylum, class, order, and family, respectively. PuzzleCluster source code is freely available at http://math.stanford.edu/~ksiegel/PuzzleCluster.html.
AB - Metagenomic datasets are composed of DNA fragments from large numbers of different and potentially novel organisms. These datasets can contain up to several million sequences taken from heterogeneous populations of extremely varied abundance. Unlike traditional genomic studies, metagenomic analysis requires an additional binning step. This process groups DNA fragments from the same or similar species of origin. However, existing unsupervised metagenomic binning programs cannot accurately analyze datasets containing a large number of species or with significantly unbalanced abundance ratios. To improve upon these current limitations, we present PuzzleCluster, a novel unsupervised binning algorithm. PuzzleCluster incorporates a unique cluster refinement step by automatically grouping reads which share a nucleotide word (i.e. reverse complement pairs) of a predetermined length. Additionally, the clustering parameters are estimated by fitting the Jensen-Shannon distance among sequences using the expectation maximization algorithm. Since clustering parameters are computed based on each dataset, our approach can adapt to the peculiarities of each dataset and is not confined by universal parameters. Furthermore, PuzzleCluster utilizes no prior assumptions about the genetic makeup or number of organisms present in the sample, making it well-suited for applications with a large amount of biodiversity and completely unknown organisms. As a comparison, PuzzleCluster has an accuracy 9%, 19.8%, 15.7%, and 19.5% higher than MetaCluster 3.0 for taxonomic levels phylum, class, order, and family, respectively. PuzzleCluster source code is freely available at http://math.stanford.edu/~ksiegel/PuzzleCluster.html.
KW - Clustering
KW - Expectation maximization
KW - Jensen-Shannon distance
KW - Metagenome
KW - Quality threshold algorithm
KW - Word agreement
UR - http://www.scopus.com/inward/record.url?scp=84989221532&partnerID=8YFLogxK
U2 - 10.2174/157489361002150518150716
DO - 10.2174/157489361002150518150716
M3 - Article
AN - SCOPUS:84989221532
SN - 1574-8936
VL - 10
SP - 225
EP - 231
JO - Current Bioinformatics
JF - Current Bioinformatics
IS - 2
ER -