Vgan Github
Adabella Frierdich
Current mitochondrial DNA (mtDNA) haplogroup classification tools map reads to a single reference genome and perform inference based on the detected mutations to this reference. This approach biases haplogroup assignments towards the reference and prohibits accurate calculations of the uncertainty in assignment. We present HaploCart, a probabilistic mtDNA haplogroup classifier which uses a pangenomic reference graph framework together with principles of Bayesian inference. We demonstrate that our approach significantly outperforms available tools by being more robust to lower coverage or incomplete consensus sequences and producing phylogenetically-aware confidence scores that are unbiased towards any haplogroup. HaploCart is available both as a command-line tool and through a user-friendly web interface. The C++ program accepts as input consensus FASTA, FASTQ, or GAM files, and outputs a text file with the haplogroup assignments of the samples along with the level of confidence in the assignments. Our work considerably reduces the amount of data required to obtain a confident mitochondrial haplogroup assignment.
Pangenome graphs are powerful and relatively nascent data structures for representing an entire collection of genomic sequences and their homology. Here we present HaploCart, a tool which leverages the power of pangenomics, in conjunction with maximum-likelihood estimation, to improve human mtDNA haplotype inference on single-source samples (i.e. the sample is not a mixture of multiple contributors, be they human or contaminant). In this context, mapping to many reference genomes at once vastly reduces the Eurocentric bias inherent in contemporary methods, and also improves haplotyping performance at low coverage depths. We show that HaploCart is far more accurate than competing programs on simulated and empirical datasets, and reports clade-level posterior probabilities that accurately reflect confidence in our phylogenetic assignments. Our work can easily be generalized to other haploid markers and suggests that pangenome-based approaches combined with Bayesian methods show promise for improving inference and mitigating ethnicity-related bias in a large class of bioinformatics problems involving sequencing data.
Copyright: 2023 Rubin et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Data Availability: All relevant datasets generated and/or analysed during the current study are available in the following repository: _Experiment_Data. The repository is also backed up at HaploCart is available as a command-line tool at and as a web server at
Funding: Funding for this research was provided by a Novo Nordisk Data Science Investigator grant number NNF20OC0062491 (GR). This funding source provided the salaries for JDR and NAV. Additional funding for computational resources was provided by the Department for Health Technology at DTU. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.
The human mitochondrial genome is a small molecule, comprising a mere 16.5 Kb, yet certain properties of the mitogenome make it an invaluable trove of information for researchers in a number of disparate fields including health and human population studies [1]. Mitochondrial DNA (mtDNA) is clonally inherited, meaning that a mother and her child will harbor the same mitogenomic sequence in the absence of mutations. When a point mutation does occur (which happens more frequently than in the autosomes [2]) a new branch breaks off on the mitochondrial phylogenetic tree. The need to classify the diversity of human mitogenomes has given rise to haplogroups. These are a set of alphanumeric labels which represent monophyletic clusters where individuals in the same haplogroup generally share the same set of mutations and share a more recent mitochondrial ancestry. These labels are man-made and represent the current state of our knowledge about mtDNA variation in humans. As such, these labels are always liable to be refined in light of new data.
Only a few programs perform inference directly on NGS reads aligned to a reference. One such program is mixemt [19], which performs maximum-likelihood estimation to determine the haplogroups and proportions for each contributor to an mtDNA mixture. The other is HaploCheck, a wrapper program which runs HaploGrep2 on a consensus called upstream (by mutserve) for BAM input and performs further downstream analyses [20]. A potential complication with aligning NGS reads directly to a mitochondrial reference is the presence of regions in the nuclear genome that share some similarity with the mitochondrial genome. Reads stemming from such regions, otherwise called NuMTs, can align to the mitochondrial reference as well [21].
Several haplogrouping tools are solely available as web servers, e.g. EMMA [22]. Web servers are important for user convenience, but they are simply impractical for high-throughput analysis or large-scale benchmarking experiments. In 2021, a study benchmarked haplogrouping tools on high-throughput sequencing data, among command-line interface (CLI) haplogrouping tools aimed at unmixed, single-source samples. HaploCheck (for BAM input) and HaploGrep2 (for consensus FASTA input) are the most accurate and robust tools, especially for short reads. For example, in a 2021 benchmarking study HaploCheck was the only algorithm to correctly classify all samples in the whole-exome dataset for BAM input and HaploGrep2 was the only CLI tool to correctly classify all samples in the whole-genome dataset [23]. The conclusion that HaploGrep2 is currently the most reliable tool reaffirms a view which had previously been concluded in the literature [24].
However, current mtDNA haplogrouping pipelines present a number of shortcomings. For one, programs which call a consensus will typically map reads to a single linear reference genome, quite often to a Eurasian reference known as the rCRS (Revised Cambridge Reference Sequence) [25]. They are thereby susceptible to reference bias meaning that DNA fragments similar to the linear reference are retained or called with higher quality. This constitutes undesired behavior since the underlying haplogroup of the linear reference is arbitrary [26, 27]. This bias entails that a lack of mutation to the reference may be conflated with missing data due to poor coverage and lead to potentially misleading experimental results. Also, the mitogenome is circular, so mapping to a linear reference may bias against reads which span the artificial rCRS junction. An additional shortcoming of contemporary methods is the absence of sensible reporting of the confidence in haplogroup assignments. For example, we have found from our reported quality experiment that HaploGrep2 quality scores will always be 0.5 when the predicted haplogroup is that of the rCRS. Finally, while current methods will converge to the correct haplogroup assignment given sufficient coverage depth, their inference lacks a solid mathematical foundation and is therefore ill-suited to sparse data.
We introduce HaploCart, a novel maximum-likelihood inference method using genome graphs that significantly outperforms current methods for inferring human haplogroups. We show that our approach is substantially more robust to low-coverage mitogenomes. As our tool uses a database built on a comprehensive set of human mitogenomes rather than relying on a single one, it fully addresses the biases plaguing current approaches, namely with regards to alignment and the estimation of confidence. Moreover, genome graphs have the ability to be circularized thus solving the issue of linearity in representing mitogenomes. Crucially, we report a phylogenetically-aware confidence score based on the Bayesian theorem that is unbiased towards any haplogroup. Our software takes either unaligned NGS reads in FASTQ format or FASTA consensus. It is released under a GPL v3.0 license. As a rough estimate, haplogroup prediction on a single consensus FASTA sequence takes around thirty seconds using one thread, and around nine seconds using eight threads. HaploCart is a C++ program released as a subcommand of vgan, a suite of tools for pangenomics. The program supports multi-threading and is supported for Linux systems.
HaploCart accepts as input either consensus FASTA or FASTQ files. We first present results on consensus FASTA and then we present results on simulated and empirical FASTQ datasets. Finally we discuss our method of sensibly reporting confidence and the computational requirements of the program.
As missing regions are generally contiguous on mitogenomes due to read length, we masked regions of various length contiguously i.e. a single region is masked on a mitogenome. We masked between a 1Kb to 16Kb bases with a step of 1Kb and created 100 replicates for each number of bases as to measure average behavior.
The results of the masking experiment confirm that HaploCart outperforms HaploGrep2 on input with masked regions, both in terms of the total number of exactly correct predictions (Fig A in S1 File) and in terms of the distribution of edit distances between ground truth and predicted haplogroups for every level of masking from 2Kb up to 16Kb. (Fig 1). While we see HaploGrep2 narrowly outperforming at the 1Kb level in terms of exact correctness, we actually see the reverse (i.e. HaploCart narrowly outperforming HaploGrep2) in terms of log edit distance at this level of masking.
Distribution of log edit (Levenshtein) distances between true and predicted haplogroup over 100 replicates for each number of (contiguous) masked nucleobases from 1Kb to 16Kb, inclusive. If the edit distance was zero, the score was also considered zero. HaploCart outperforms HaploGrep2 and Phy-Mer up to 15 Kb.
c80f0f1006