Haplotype assembly in polyploid genomes and identical by descent shared tracts

Abstract

Motivation: Genome-wide haplotype reconstruction from sequence data, or haplotype assembly, is at the center of major challenges in molecular biology and life sciences. For complex eukaryotic organisms like humans, the genome is vast and the population samples are growing so rapidly that algorithms processing high-throughput sequencing data must scale favorably in terms of both accuracy and computational efficiency. Furthermore, current models and methodologies for haplotype assembly (i) do not consider individuals sharing haplotypes jointly, which reduces the size and accuracy of assembled haplotypes, and (ii) are unable to model genomes having more than two sets of homologous chromosomes (polyploidy). Polyploid organisms are increasingly becoming the target of many research groups interested in the genomics of disease, phylogenetics, botany and evolution but there is an absence of theory and methods for polyploid haplotype reconstruction.

Results: In this work, we present a number of results, extensions and generalizations of compass graphs and our HapCompass framework. We prove the theoretical complexity of two haplotype assembly optimizations, thereby motivating the use of heuristics. Furthermore, we present graph theory-based algorithms for the problem of haplotype assembly using our previously developed HapCompass framework for (i) novel implementations of haplotype assembly optimizations (minimum error correction), (ii) assembly of a pair of individuals sharing a haplotype tract identical by descent and (iii) assembly of polyploid genomes. We evaluate our methods on 1000 Genomes Project, Pacific Biosciences and simulated sequence data.

Availability and implementation: HapCompass is available for download at http://www.brown.edu/Research/Istrail_Lab/.

Supplementary information: Supplementary data are available at Bioinformatics online.

Fig. 1.

Construction of the input to the haplotype assembly problem

Fig. 2.

Construction of the compass graph from SNP-fragment matrix M. The SNP-fragment matrix M (left) contains four fragments and four SNPs. Each SNP’s pairwise phasing relationship defined by the fragments is represented on the edges of the compass graph (right). The majority rule phasing for one of the haplotypes is shown in red on the compass graph edges

Fig. 3.

A graph of the haplotype transitions defined by the majority rule phasings of a compass graph. SNPs 1, 2, 3, 4 and 5 (left to right) are shown with both alleles (vertices), and edge transitions are encoded by a specific type of line depending on whether the haplotype is shared IBD or unique to the child or parent. The genotype of the parent and child are 22 222 and 22 122, respectively (where the two corresponds to the heterozygote and 0 and 1 correspond to homozygous for the major and minor alleles, respectively)

Fig. 4.

Compass graphs , a non-conflicting polyploid cycle (left), and , a conflicting polyploid cycle (right). The vector on the edge corresponds to the haplotype counts for an edge in the format [00,01,10,11]. In both compass graphs, the haplotypes are 000, 000 and 111, while the reads in are 000, 000 and 111, and the reads in are 00–, 01–, 10–, –00, –00, –11, 0–0, 0–0 and 1–1

Fig. 5.

The chain graphs (top) and (bottom) corresponding to and , respectively

Fig. 6.

The auxiliary flow graphs (top) and (bottom) . For a k-ploid organism (in this case k = 3), a flow of k with 1 capacity on each edge corresponds to a valid assignment of haplotype paths to haplotypes of the phasing a level 1

Fig. 7.

Comparison between haplotype assembling the child individually versus with a parent. The haplotype size is number of SNPs in the component of G_C, which represents the maximum number of SNPs that may be phased together

Fig. 8.

Comparison of the percentage of correctly phased polyploid SNP pairs for the greedy and probabilistic binning algorithms for varying number of input reads