{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T20:34:01Z","timestamp":1772138041620,"version":"3.50.1"},"reference-count":22,"publisher":"Oxford University Press (OUP)","issue":"10","license":[{"start":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T00:00:00Z","timestamp":1605657600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"BBSRC Institute Strategic Programme Grant"},{"name":"Rumen Systems Biology","award":["BB\/E\/W\/10964A01"],"award-info":[{"award-number":["BB\/E\/W\/10964A01"]}]},{"name":"Meth-Abate project","award":["R3192GFS"],"award-info":[{"award-number":["R3192GFS"]}]},{"name":"EC via Horizon 2020","award":["818368"],"award-info":[{"award-number":["818368"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,6,16]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Population-level genetic variation enables competitiveness and niche specialization in microbial communities. Despite the difficulty in culturing many microbes from an environment, we can still study these communities by isolating and sequencing DNA directly from an environment (metagenomics). Recovering the genomic sequences of all isoforms of a given gene across all organisms in a metagenomic sample would aid evolutionary and ecological insights into microbial ecosystems with potential benefits for medicine and biotechnology. A significant obstacle to this goal arises from the lack of a computationally tractable solution that can recover these sequences from sequenced read fragments. This poses a problem analogous to reconstructing the two sequences that make up the genome of a diploid organism (i.e. haplotypes) but for an unknown number of individuals and haplotypes.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>The problem of single individual haplotyping was first formalized by Lancia et al. in 2001. Now, nearly two decades later, we discuss the complexity of \u2018haplotyping\u2019 metagenomic samples, with a new formalization of Lancia et al.\u2019s data structure that allows us to effectively extend the single individual haplotype problem to microbial communities. This work describes and formalizes the problem of recovering genes (and other genomic subsequences) from all individuals within a complex community sample, which we term the metagenomic individual haplotyping problem. We also provide software implementations for a pairwise single nucleotide variant (SNV) co-occurrence matrix and greedy graph traversal algorithm.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>Our reference implementation of the described pairwise SNV matrix (Hansel) and greedy haplotype path traversal algorithm (Gretel) is open source, MIT licensed and freely available online at github.com\/samstudio8\/hansel and github.com\/samstudio8\/gretel, respectively.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaa977","type":"journal-article","created":{"date-parts":[[2020,11,9]],"date-time":"2020-11-09T07:30:03Z","timestamp":1604907003000},"page":"1360-1366","source":"Crossref","is-referenced-by-count":20,"title":["On the complexity of haplotyping a microbial community"],"prefix":"10.1093","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4081-065X","authenticated-orcid":false,"given":"Samuel M","family":"Nicholls","sequence":"first","affiliation":[{"name":"Department of Computer Science, Aberystwyth University , Aberystwyth SY23 3DB, UK"},{"name":"Department of Computer Science, Katholieke Universiteit Leuven , 3001 Leuven, Belgium"},{"name":"Institute of Biological, Rural and Environmental Sciences, Aberystwyth University , Aberystwyth SY23 3DA, UK"},{"name":"Institute of Microbiology and Infection, School of Biosciences, University of Birmingham , Birmingham B15 2TT, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3351-1758","authenticated-orcid":false,"given":"Wayne","family":"Aubrey","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Aberystwyth University , Aberystwyth SY23 3DB, UK"}]},{"given":"Kurt","family":"De Grave","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Katholieke Universiteit Leuven , 3001 Leuven, Belgium"},{"name":"Flanders Make , 3920 Lommel, Belgium"}]},{"given":"Leander","family":"Schietgat","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Katholieke Universiteit Leuven , 3001 Leuven, Belgium"},{"name":"Artificial Intelligence Lab, Vrije Universiteit Brussel , 1050 Ixelles, Belgium"}]},{"given":"Christopher J","family":"Creevey","sequence":"additional","affiliation":[{"name":"Institute of Biological, Rural and Environmental Sciences, Aberystwyth University , Aberystwyth SY23 3DA, UK"},{"name":"Institute of Global Food Security, School of Biological Sciences, Queen\u2019s University , Belfast BT9 5DL, UK"}]},{"given":"Amanda","family":"Clare","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Aberystwyth University , Aberystwyth SY23 3DB, UK"}]}],"member":"286","published-online":{"date-parts":[[2021,1,13]]},"reference":[{"key":"2023051709343873900_btaa977-B1","doi-asserted-by":"crossref","first-page":"i352","DOI":"10.1093\/bioinformatics\/btt213","article-title":"Haplotype assembly in polyploid genomes and identical by descent shared tracts","volume":"29","author":"Aguiar","year":"2013","journal-title":"Bioinformatics"},{"key":"2023051709343873900_btaa977-B2","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/S0888-7543(05)80288-5","article-title":"The accuracy of DNA sequences: estimating sequence quality","volume":"14","author":"Churchill","year":"1992","journal-title":"Genomics"},{"key":"2023051709343873900_btaa977-B3","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1007\/11557067_11","volume-title":"Algorithms in Bioinformatics","author":"Cilibrasi","year":"2005"},{"key":"2023051709343873900_btaa977-B4","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1186\/s13059-019-1709-0","article-title":"Haplotype-aware diplotyping from noisy long reads","volume":"20","author":"Ebler","year":"2019","journal-title":"Genome Biol"},{"key":"2023051709343873900_btaa977-B5","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1038\/s41587-018-0009-7","article-title":"A human gut bacterial genome and culture collection for improved metagenomic analyses","volume":"37","author":"Forster","year":"2019","journal-title":"Nat. Biotechnol"},{"key":"2023051709343873900_btaa977-B6","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1186\/s12864-018-4464-9","article-title":"Efficient algorithms for polyploid haplotype phasing","volume":"19","author":"He","year":"2018","journal-title":"BMC Genomics"},{"key":"2023051709343873900_btaa977-B7","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1038\/s41587-019-0072-8","article-title":"Assembly of long, error-prone reads using repeat graphs","volume":"37","author":"Kolmogorov","year":"2019","journal-title":"Nat. Biotechnol"},{"key":"2023051709343873900_btaa977-B8","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1038\/nbt.3416","article-title":"Synthetic long-read sequencing reveals intraspecies diversity in the human microbiome","volume":"34","author":"Kuleshov","year":"2016","journal-title":"Nat. Biotechnol"},{"key":"2023051709343873900_btaa977-B9","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1051\/ro\/2015037","article-title":"Algorithmic approaches for the single individual haplotyping problem","volume":"50","author":"Lancia","year":"2016","journal-title":"RAIRO Oper. Res"},{"key":"2023051709343873900_btaa977-B10","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1007\/3-540-44676-1_15","volume-title":"Algorithms \u2013 ESA 2001","author":"Lancia","year":"2001"},{"key":"2023051709343873900_btaa977-B11","doi-asserted-by":"crossref","first-page":"e1007843","DOI":"10.1371\/journal.pcbi.1007843","article-title":"Ranbow: a fast and accurate method for polyploid haplotype reconstruction","volume":"16","author":"Moeinzadeh","year":"2020","journal-title":"PLoS Comput. Biol"},{"key":"2023051709343873900_btaa977-B12","author":"Nicholls","year":"2018"},{"key":"2023051709343873900_btaa977-B13","doi-asserted-by":"crossref","first-page":"giz043","DOI":"10.1093\/gigascience\/giz043","article-title":"Ultra-deep, long-read nanopore sequencing of mock microbial community standards","volume":"8","author":"Nicholls","year":"2019","journal-title":"Gigascience"},{"key":"2023051709343873900_btaa977-B14","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1101\/gr.213959.116","article-title":"metaSPAdes: a new versatile metagenomic assembler","volume":"27","author":"Nurk","year":"2017","journal-title":"Genome Res"},{"key":"2023051709343873900_btaa977-B15","doi-asserted-by":"crossref","first-page":"1510","DOI":"10.1038\/ismej.2017.34","article-title":"Divergent functional isoforms drive niche specialisation for nutrient acquisition and use in rumen microbiome","volume":"11","author":"Rubino","year":"2017","journal-title":"ISME J"},{"key":"2023051709343873900_btaa977-B16","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1186\/s13059-020-02158-1","article-title":"Haplotype threading: accurate polyploid phasing from long reads","volume":"21","author":"Schrinner","year":"2020","journal-title":"Genome Biol"},{"key":"2023051709343873900_btaa977-B17","doi-asserted-by":"crossref","first-page":"e00190","DOI":"10.1128\/mSystems.00190-17","article-title":"On the road to strain-resolved comparative metagenomics","volume":"3","author":"Segata","year":"2018","journal-title":"mSystems"},{"key":"2023051709343873900_btaa977-B18","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1038\/nbt.4110","article-title":"Cultivation and sequencing of rumen microbiome members from the Hungate1000 Collection","volume":"36","author":"Seshadri","year":"2018","journal-title":"Nat. Biotechnol"},{"key":"2023051709343873900_btaa977-B19","doi-asserted-by":"crossref","first-page":"953","DOI":"10.1038\/s41587-019-0202-3","article-title":"Compendium of 4,941 rumen metagenome-assembled genomes for rumen microbiome biology and enzyme discovery","volume":"37","author":"Stewart","year":"2019","journal-title":"Nat. Biotechnol"},{"key":"2023051709343873900_btaa977-B20","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1038\/s41579-020-0368-1","article-title":"Diversity within species: interpreting strains in microbiomes","volume":"18","author":"Van Rossum","year":"2020","journal-title":"Nature Reviews Microbiology"},{"key":"2023051709343873900_btaa977-B21","doi-asserted-by":"crossref","first-page":"1155","DOI":"10.1038\/s41587-019-0217-9","article-title":"Accurate circular consensus long-read sequencing improves variant detection and assembly of a human genome","volume":"37","author":"Wenger","year":"2019","journal-title":"Nat. Biotechnol"},{"key":"2023051709343873900_btaa977-B22","doi-asserted-by":"crossref","first-page":"1920","DOI":"10.3390\/md8061920","article-title":"Research and application of marine microbial enzymes: status and prospects","volume":"8","author":"Zhang","year":"2010","journal-title":"Marine Drugs"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btaa977\/35823962\/btaa977.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/10\/1360\/50360994\/btaa977.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/10\/1360\/50360994\/btaa977.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,17]],"date-time":"2023-05-17T05:50:09Z","timestamp":1684302609000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/37\/10\/1360\/5988481"}},"subtitle":[],"editor":[{"given":"Pier","family":"Luigi Martelli","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2021,1,13]]},"references-count":22,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2021,6,16]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaa977","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2020.08.10.244848","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":[[2021,5,15]]},"published":{"date-parts":[[2021,1,13]]}}}