Unsupervised statistical clustering of environmental shotgun sequences
<p>Abstract</p> <p>Background</p> <p>The development of effective environmental shotgun sequence binning methods remains an ongoing challenge in algorithmic analysis of metagenomic data. While previous methods have focused primarily on supervised learning involving extr...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2009-10-01
|
| Series: | BMC Bioinformatics |
| Online Access: | http://www.biomedcentral.com/1471-2105/10/316 |
| _version_ | 1811294137398329344 |
|---|---|
| author | Bhatnagar Srijak Kislyuk Andrey Dushoff Jonathan Weitz Joshua S |
| author_facet | Bhatnagar Srijak Kislyuk Andrey Dushoff Jonathan Weitz Joshua S |
| author_sort | Bhatnagar Srijak |
| collection | DOAJ |
| description | <p>Abstract</p> <p>Background</p> <p>The development of effective environmental shotgun sequence binning methods remains an ongoing challenge in algorithmic analysis of metagenomic data. While previous methods have focused primarily on supervised learning involving extrinsic data, a first-principles statistical model combined with a self-training fitting method has not yet been developed.</p> <p>Results</p> <p>We derive an unsupervised, maximum-likelihood formalism for clustering short sequences by their taxonomic origin on the basis of their <it>k</it>-mer distributions. The formalism is implemented using a Markov Chain Monte Carlo approach in a <it>k</it>-mer feature space. We introduce a space transformation that reduces the dimensionality of the feature space and a genomic fragment divergence measure that strongly correlates with the method's performance. Pairwise analysis of over 1000 completely sequenced genomes reveals that the vast majority of genomes have sufficient genomic fragment divergence to be amenable for binning using the present formalism. Using a high-performance implementation, the binner is able to classify fragments as short as 400 nt with accuracy over 90% in simulations of low-complexity communities of 2 to 10 species, given sufficient genomic fragment divergence. The method is available as an open source package called LikelyBin.</p> <p>Conclusion</p> <p>An unsupervised binning method based on statistical signatures of short environmental sequences is a viable stand-alone binning method for low complexity samples. For medium and high complexity samples, we discuss the possibility of combining the current method with other methods as part of an iterative process to enhance the resolving power of sorting reads into taxonomic and/or functional bins.</p> |
| first_indexed | 2024-04-13T05:12:10Z |
| format | Article |
| id | doaj.art-8558242e8d6149d48a90fe8284324ab4 |
| institution | Directory Open Access Journal |
| issn | 1471-2105 |
| language | English |
| last_indexed | 2024-04-13T05:12:10Z |
| publishDate | 2009-10-01 |
| publisher | BMC |
| record_format | Article |
| series | BMC Bioinformatics |
| spelling | doaj.art-8558242e8d6149d48a90fe8284324ab42022-12-22T03:01:00ZengBMCBMC Bioinformatics1471-21052009-10-0110131610.1186/1471-2105-10-316Unsupervised statistical clustering of environmental shotgun sequencesBhatnagar SrijakKislyuk AndreyDushoff JonathanWeitz Joshua S<p>Abstract</p> <p>Background</p> <p>The development of effective environmental shotgun sequence binning methods remains an ongoing challenge in algorithmic analysis of metagenomic data. While previous methods have focused primarily on supervised learning involving extrinsic data, a first-principles statistical model combined with a self-training fitting method has not yet been developed.</p> <p>Results</p> <p>We derive an unsupervised, maximum-likelihood formalism for clustering short sequences by their taxonomic origin on the basis of their <it>k</it>-mer distributions. The formalism is implemented using a Markov Chain Monte Carlo approach in a <it>k</it>-mer feature space. We introduce a space transformation that reduces the dimensionality of the feature space and a genomic fragment divergence measure that strongly correlates with the method's performance. Pairwise analysis of over 1000 completely sequenced genomes reveals that the vast majority of genomes have sufficient genomic fragment divergence to be amenable for binning using the present formalism. Using a high-performance implementation, the binner is able to classify fragments as short as 400 nt with accuracy over 90% in simulations of low-complexity communities of 2 to 10 species, given sufficient genomic fragment divergence. The method is available as an open source package called LikelyBin.</p> <p>Conclusion</p> <p>An unsupervised binning method based on statistical signatures of short environmental sequences is a viable stand-alone binning method for low complexity samples. For medium and high complexity samples, we discuss the possibility of combining the current method with other methods as part of an iterative process to enhance the resolving power of sorting reads into taxonomic and/or functional bins.</p>http://www.biomedcentral.com/1471-2105/10/316 |
| spellingShingle | Bhatnagar Srijak Kislyuk Andrey Dushoff Jonathan Weitz Joshua S Unsupervised statistical clustering of environmental shotgun sequences BMC Bioinformatics |
| title | Unsupervised statistical clustering of environmental shotgun sequences |
| title_full | Unsupervised statistical clustering of environmental shotgun sequences |
| title_fullStr | Unsupervised statistical clustering of environmental shotgun sequences |
| title_full_unstemmed | Unsupervised statistical clustering of environmental shotgun sequences |
| title_short | Unsupervised statistical clustering of environmental shotgun sequences |
| title_sort | unsupervised statistical clustering of environmental shotgun sequences |
| url | http://www.biomedcentral.com/1471-2105/10/316 |
| work_keys_str_mv | AT bhatnagarsrijak unsupervisedstatisticalclusteringofenvironmentalshotgunsequences AT kislyukandrey unsupervisedstatisticalclusteringofenvironmentalshotgunsequences AT dushoffjonathan unsupervisedstatisticalclusteringofenvironmentalshotgunsequences AT weitzjoshuas unsupervisedstatisticalclusteringofenvironmentalshotgunsequences |