On the complexity of haplotyping a microbial community

Sam Nicholls, Wayne Aubrey, Kurt de Grave, Leander Schietgat, Chris Creevey, Amanda Clare

Research output: Contribution to journalArticlepeer-review

9 Citations (SciVal)
90 Downloads (Pure)


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.

The problem of single individual haplotyping (SIH) was first formalised by Lancia et al in 2001. Now, nearly two decades later, we discuss the complexity of “haplotyping” metagenomic samples, with a new formalisation of Lancia et al ‘s 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 (MIH) problem. We also provide software implementations of our proposed pairwise single nucleotide variant (SNV) co-occurrence matrix and greedy graph traversal algorithm.

Availability and implementation
Our reference implementation of the described pairwise SNV matrix (Hansel) and greedy haplotype path traversal algorithm (Gretel) are open source, MIT licensed and freely available online at github.com/samstudio8/hansel and github.com/samstudio8/gretel, respectively.
Original languageEnglish
Article numberbtaa977
Pages (from-to)1360-1366
Number of pages7
Issue number10
Early online date13 Jan 2021
Publication statusPublished - 15 May 2021


Dive into the research topics of 'On the complexity of haplotyping a microbial community'. Together they form a unique fingerprint.

Cite this