{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:44:52Z","timestamp":1773272692447,"version":"3.50.1"},"reference-count":39,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2018,7,13]],"date-time":"2018-07-13T00:00:00Z","timestamp":1531440000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["GM108348"],"award-info":[{"award-number":["GM108348"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Center for Microbiome Informatics and Therapeutics Pilot"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,1,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Vastly greater quantities of microbial genome data are being generated where environmental samples mix together the DNA from many different species. Here, we present Opal for metagenomic binning, the task of identifying the origin species of DNA sequencing reads. We introduce \u2018low-density\u2019 locality sensitive hashing to bioinformatics, with the addition of Gallager codes for even coverage, enabling quick and accurate metagenomic binning.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>On public benchmarks, Opal halves the error on precision\/recall (F1-score) as compared with both alignment-based and alignment-free methods for species classification. We demonstrate even more marked improvement at higher taxonomic levels, allowing for the discovery of novel lineages. Furthermore, the innovation of low-density, even-coverage hashing should itself prove an essential methodological advance as it enables the application of machine learning to other bioinformatic challenges.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>Full source code and datasets are available at http:\/\/opal.csail.mit.edu and https:\/\/github.com\/yunwilliamyu\/opal.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Supplementary information<\/jats:title>\n                    <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/bty611","type":"journal-article","created":{"date-parts":[[2018,7,13]],"date-time":"2018-07-13T07:24:21Z","timestamp":1531466661000},"page":"219-226","source":"Crossref","is-referenced-by-count":25,"title":["Metagenomic binning through low-density hashing"],"prefix":"10.1093","volume":"35","author":[{"given":"Yunan","family":"Luo","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Illinois at Urbana-Champaign, Champaign, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yun William","family":"Yu","sequence":"additional","affiliation":[{"name":"Department of Biomedical Informatics, Harvard Medical School, Boston, MA, USA"},{"name":"Department of Mathematics and Computer Science and AI Laboratory, Massachusetts Institute of Technology, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianyang","family":"Zeng","sequence":"additional","affiliation":[{"name":"Machine Learning and Computational Biology Group, Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China and"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bonnie","family":"Berger","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science and AI Laboratory, Massachusetts Institute of Technology, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jian","family":"Peng","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois at Urbana-Champaign, Champaign, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2018,7,13]]},"reference":[{"key":"2023013107225773400_bty611-B1","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1038\/nature11632","article-title":"An integrated map of genetic variation from 1, 092 human genomes","volume":"491","author":"1000 Genomes Project Consortium.","year":"2012","journal-title":"Nature"},{"key":"2023013107225773400_bty611-B2","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J. Mol. Biol."},{"key":"2023013107225773400_bty611-B3","doi-asserted-by":"crossref","first-page":"1144","DOI":"10.1038\/nmeth.3103","article-title":"Binning metagenomic contigs by coverage and composition","volume":"11","author":"Alneberg","year":"2014","journal-title":"Nat. Methods"},{"key":"2023013107225773400_bty611-B4","doi-asserted-by":"crossref","first-page":"2253","DOI":"10.1093\/bioinformatics\/btt389","article-title":"Scalable metagenomic taxonomy classification using a reference genome database","volume":"29","author":"Ames","year":"2013","journal-title":"Bioinformatics"},{"key":"2023013107225773400_bty611-B5","first-page":"459","article-title":"Near-optimal hashing algorithms for approximate nearest neighbor in high dimension","volume-title":"Foundations of Computer Science","author":"Andoni","year":"2006"},{"key":"2023013107225773400_bty611-B6","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1038\/nbt.3238","article-title":"Assembling large genomes with single-molecule sequencing and locality-sensitive hashing","volume":"33","author":"Berlin","year":"2015","journal-title":"Nat. Biotechnol."},{"key":"2023013107225773400_bty611-B7","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1038\/nmeth.1358","article-title":"Phymm and phymmbl: metagenomic phylogenetic classification with interpolated markov models","volume":"6","author":"Brady","year":"2009","journal-title":"Nat. Methods"},{"key":"2023013107225773400_bty611-B8","doi-asserted-by":"crossref","first-page":"3584","DOI":"10.1093\/bioinformatics\/btv419","article-title":"Spaced seeds improve k-mer-based metagenomic classification","volume":"31","author":"B\u0159inda","year":"2015","journal-title":"Bioinformatics"},{"key":"2023013107225773400_bty611-B9","doi-asserted-by":"crossref","first-page":"3823","DOI":"10.1093\/nar\/gkm238","article-title":"SNAP: predict effect of non-synonymous polymorphisms on function","volume":"35","author":"Bromberg","year":"2007","journal-title":"Nucleic Acids Res."},{"key":"2023013107225773400_bty611-B10","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1038\/nmeth.3176","article-title":"Fast and sensitive protein alignment using Diamond","volume":"12","author":"Buchfink","year":"2015","journal-title":"Nat. Methods"},{"key":"2023013107225773400_bty611-B11","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1093\/bioinformatics\/17.5.419","article-title":"Efficient large-scale sequence comparison by locality-sensitive hashing","volume":"17","author":"Buhler","year":"2001","journal-title":"Bioinformatics"},{"key":"2023013107225773400_bty611-B12","doi-asserted-by":"crossref","first-page":"1053","DOI":"10.1038\/nbt.3329","article-title":"Detection of low-abundance bacterial strains in metagenomic datasets by Eigengenome partitioning","volume":"33","author":"Cleary","year":"2015","journal-title":"Nat. Biotechnol."},{"key":"2023013107225773400_bty611-B13","doi-asserted-by":"crossref","first-page":"e49138","DOI":"10.1371\/journal.pone.0049138","article-title":"integrated metagenomics\/metaproteomics reveals human host-microbiota signatures of Crohn\u2019s disease","volume":"7","author":"Erickson","year":"2012","journal-title":"PLoS One"},{"key":"2023013107225773400_bty611-B14","doi-asserted-by":"crossref","first-page":"1107","DOI":"10.1126\/science.1220761","article-title":"The shared antibiotic resistome of soil bacteria and human pathogens","volume":"337","author":"Forsberg","year":"2012","journal-title":"Science"},{"key":"2023013107225773400_bty611-B15","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1109\/TIT.1962.1057683","article-title":"Low-density parity-check codes","volume":"8","author":"Gallager","year":"1962","journal-title":"IEEE Trans. Inform. Theory"},{"key":"2023013107225773400_bty611-B16","doi-asserted-by":"crossref","first-page":"2761","DOI":"10.1128\/JCM.01228-07","article-title":"16S rRNA gene sequencing for bacterial identification in the diagnostic laboratory: pluses, perils, and pitfalls","volume":"45","author":"Janda","year":"2007","journal-title":"J. Clin. Microbiol."},{"key":"2023013107225773400_bty611-B17","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/S0166-218X(03)00382-2","article-title":"On spaced seeds for similarity search","volume":"138","author":"Keich","year":"2004","journal-title":"Discrete Appl. Math."},{"key":"2023013107225773400_bty611-B18","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1038\/nmeth.1923","article-title":"Fast gapped-read alignment with Bowtie 2","volume":"9","author":"Langmead","year":"2012","journal-title":"Nat. Methods"},{"key":"2023013107225773400_bty611-B19","first-page":"1303.3997","article-title":"Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM","author":"Li","year":"2013","journal-title":"arXiv Preprint arXiv:"},{"key":"2023013107225773400_bty611-B20","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1093\/bioinformatics\/18.3.440","article-title":"PatternHunter: faster and more sensitive homology search","volume":"18","author":"Ma","year":"2002","journal-title":"Bioinformatics"},{"key":"2023013107225773400_bty611-B21","article-title":"Short-chain fatty acid fermentation products of the gut microbiome: implications in autism spectrum disorders","volume":"23","author":"MacFabe","year":"2012","journal-title":"Microb. Ecol. Health Dis."},{"key":"2023013107225773400_bty611-B22","doi-asserted-by":"crossref","first-page":"1645","DOI":"10.1049\/el:19961141","article-title":"Near Shannon limit performance of low density parity check codes","volume":"32","author":"MacKay","year":"1996","journal-title":"Electron. Lett."},{"key":"2023013107225773400_bty611-B23","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1038\/nmeth976","article-title":"Accurate phylogenetic classification of variable-length dna fragments","volume":"4","author":"McHardy","year":"2007","journal-title":"Nat. Methods"},{"key":"2023013107225773400_bty611-B24","doi-asserted-by":"crossref","first-page":"11257","DOI":"10.1038\/ncomms11257","article-title":"Fast and sensitive taxonomic classification for metagenomics with Kaiju","volume":"7","author":"Menzel","year":"2016","journal-title":"Nat. Commun."},{"key":"2023013107225773400_bty611-B25","doi-asserted-by":"crossref","first-page":"1005","DOI":"10.1038\/nmeth.3642","article-title":"Microbiology: the strain in metagenomics","volume":"12","author":"Nawy","year":"2015","journal-title":"Nat. Methods"},{"key":"2023013107225773400_bty611-B26","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1186\/s13059-016-0997-x","article-title":"Mash: fast genome and metagenome distance estimation using MinHash","volume":"17","author":"Ondov","year":"2016","journal-title":"Genome Biol."},{"key":"2023013107225773400_bty611-B27","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-48221-6_21","article-title":"Higher classification accuracy of short metagenomic reads by discriminative spaced k-mers","volume-title":"Algorithms in Bioinformatics. WABI 2015","author":"Ounit","year":"2015"},{"key":"2023013107225773400_bty611-B28","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1186\/s12864-015-1419-2","article-title":"CLARK: fast and accurate classification of metagenomic and genomic sequences using discriminative k-mers","volume":"16","author":"Ounit","year":"2015","journal-title":"BMC Genomics"},{"key":"2023013107225773400_bty611-B29","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1038\/nmeth0311-191","article-title":"Taxonomic metagenome sequence assignment with structured output models","volume":"8","author":"Patil","year":"2011","journal-title":"Nat. Methods"},{"key":"2023013107225773400_bty611-B30","doi-asserted-by":"crossref","first-page":"S11","DOI":"10.1186\/1752-0509-7-S4-S11","article-title":"16S rRNA metagenome clustering and diversity estimation using locality sensitive hashing","volume":"7","author":"Rasheed","year":"2013","journal-title":"BMC Syst. Biol."},{"key":"2023013107225773400_bty611-B31","doi-asserted-by":"crossref","first-page":"2082","DOI":"10.1093\/bioinformatics\/btx106","article-title":"Pseudoalignment for metagenomic read assignment","volume":"33","author":"Schaeffer","year":"2017","journal-title":"Bioinformatics"},{"key":"2023013107225773400_bty611-B32","doi-asserted-by":"crossref","first-page":"902","DOI":"10.1038\/nmeth.3589","article-title":"MetaPhlAn2 for enhanced metagenomic taxonomic profiling","volume":"12","author":"Truong","year":"2015","journal-title":"Nat. Methods"},{"key":"2023013107225773400_bty611-B33","doi-asserted-by":"crossref","first-page":"e67","DOI":"10.1093\/nar\/gku138","article-title":"Strain\/species identification in metagenomes using genome-specific markers","volume":"42","author":"Tu","year":"2014","journal-title":"Nucleic Acids Res."},{"key":"2023013107225773400_bty611-B34","doi-asserted-by":"crossref","first-page":"4153","DOI":"10.1113\/jphysiol.2009.174136","article-title":"The core gut microbiome, energy balance and obesity","volume":"587","author":"Turnbaugh","year":"2009","journal-title":"J. Physiol."},{"key":"2023013107225773400_bty611-B35","doi-asserted-by":"crossref","first-page":"1023","DOI":"10.1093\/bioinformatics\/btv683","article-title":"Largescale machine learning for metagenomics sequence classification","volume":"32","author":"Vervier","year":"2016","journal-title":"Bioinformatics"},{"key":"2023013107225773400_bty611-B36","doi-asserted-by":"crossref","first-page":"5261","DOI":"10.1128\/AEM.00062-07","article-title":"Naive bayesian classifier for rapid assignment of rRNA sequences into the new bacterial taxonomy","volume":"73","author":"Wang","year":"2007","journal-title":"Appl. Environ. Microbiol."},{"key":"2023013107225773400_bty611-B37","doi-asserted-by":"crossref","first-page":"R46","DOI":"10.1186\/gb-2014-15-3-r46","article-title":"Kraken: ultrafast metagenomic sequence classification using exact alignments","volume":"15","author":"Wood","year":"2014","journal-title":"Genome Biol."},{"key":"2023013107225773400_bty611-B38","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/j.cels.2015.08.004","article-title":"Entropy-scaling search of massive biological data","volume":"1","author":"Yu","year":"2015","journal-title":"Cell Syst."},{"key":"2023013107225773400_bty611-B39","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1038\/nbt.3170","article-title":"Quality score compression improves genotyping accuracy","volume":"33","author":"Yu","year":"2015","journal-title":"Nat. Biotechnol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/35\/2\/219\/48962562\/bioinformatics_35_2_219.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/35\/2\/219\/48962562\/bioinformatics_35_2_219.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T05:05:56Z","timestamp":1675141556000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/35\/2\/219\/5053315"}},"subtitle":[],"editor":[{"given":"Inanc","family":"Birol","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2018,7,13]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,1,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bty611","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/133116","asserted-by":"object"}]},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2019,1,15]]},"published":{"date-parts":[[2018,7,13]]}}}