Most eukaryotic organisms are diploid, meaning they carry two homologous copies of each chromosome—one inherited from each parent. When we sequence a genome, however, standard high-throughput technologies do not inherently distinguish between these two physical sources. Instead, they output a blended, unphased mixture of genetic variants known as a genotype.
The challenge of determining which genetic variants reside together on the same physical chromosome is known as haplotype phasing or haplotype assembly. Without phasing, genomic data suffers from phase ambiguity, leading assembly algorithms to merge distinct maternal and paternal sequences into an artificial mosaic consensus. This phenomenon, known as haplotype collapse, obscures critical structural variations, compound mutations, and allele-specific features.
Unphased Genotype: ---(A/G)-----------(C/T)--- (Ambiguous linkage)
Possible Phased Haplotypes:
Configuration 1: ---A---------------C--- (Maternal)
---G---------------T--- (Paternal)
Configuration 2: ---A---------------T--- (Maternal)
---G---------------C--- (Paternal)
To resolve this ambiguity, computational biologists have developed two primary strategies: statistical phasing, which infers the most likely configuration from population patterns and family lineages, and read-based assembly phasing, which uses physical properties of long DNA molecules and spatial proximity to separate maternal and paternal sequences.
Statistical Phasing: Inferring Linkage from Population Patterns
When sequencing reads are too short to physically connect neighboring variants, we can look to population genetics for clues. Because human and animal genomes are inherited in chunks that change slowly over generations due to limited recombination events, variants close to one another tend to be tightly linked in conserved regions called haplotype blocks, as described by Koivisto et al. in An MDL Method for Finding Haplotype Blocks and for Estimating the Strength of Haplotype Block Boundaries.
Markov Chains and Reference Panels
If we know the common haplotype configurations in a population, we can treat phasing as a pathfinding problem through a state space of reference haplotypes. Eronen et al. demonstrated in A Markov Chain Approach to Reconstruction of Long Haplotypes that variable-order Markov models can effectively capture these local dependencies. Similarly, Landwehr introduced constrained hidden Markov models in Constrained hidden Markov models for population-based haplotyping to prune rare transitions and efficiently find the most probable sequence of hidden states (the true haplotypes) behind the observed genotypes.
As datasets grew to biobank scale, traditional Markov models faced severe computational bottlenecks. To scale these approaches, Delaneau et al. leveraged the Positional Burrows–Wheeler Transform (PBWT) in Accurate, scalable and integrative haplotype estimation, achieving sub-linear running times by rapidly finding matches within massive reference panels. As an alternative to traditional probabilistic frameworks, Sanaullah proposed a combinatorial approach in Minimal positional substring cover is a haplotype threading alternative to Li and Stephens model, using substring covers to thread unphased genotypes through reference panels at high speeds.
Leveraging Family Lineages
When population panels are insufficient, family relationships provide rigid mathematical boundaries that eliminate phase ambiguity. By analyzing parent-offspring "trios," algorithms can track the exact transmission of alleles. Chen et al. showed in Genotype calling and haplotyping in parent-offspring trios that combining family-based inheritance rules with population patterns reduces phasing switch errors by over 95%.
Where pedigree data alone leaves ties unresolved—such as when all family members are heterozygous for the same variant—hybrid frameworks like the one proposed by Li et al. in Detecting Genome-wide Haplotype Polymorphism by Combined Use of Mendelian Constraints and Local Population Structure use population frequencies to break ties, pruning up to 95% of the algorithmic search space.
Read-Based and Assembly Phasing: Physical Separation
While statistical inference is powerful, it relies on prior data and struggles with rare or unique mutations. Read-based phasing bypasses inference entirely by using sequencing reads that are long enough to physically span multiple heterozygous sites, directly capturing which alleles coexist on the same molecule.
Heterozygous Sites: (A/G)=======(C/T)=======(G/C)
Long Sequencing Read 1: --A---------C-- -> Binned to Haplotype 1
Long Sequencing Read 2: --T---------C-- -> Binned to Haplotype 2
Long Sequencing Read 3: --G---------T-- -> Binned to Haplotype 2
Pre-Assembly Partitioning
The most reliable way to prevent haplotype collapse is to separate sequencing reads into maternal and paternal groups before constructing an assembly graph. As shown by Chaisson et al. in Multi-platform discovery of haplotype-resolved structural variation in human genomes, combining long, error-prone reads with highly accurate short reads allows algorithms to map out variants and partition the data into independent haploid datasets.
Building on this, tools like PECAT, developed by Nie et al. in De novo diploid genome assembly using long noisy reads, implement haplotype-aware error correction directly on raw, noisy long reads. By distinguishing true haplotype variations from sequencing errors during the initial alignment phase, the algorithm constructs highly contiguous string graphs without requiring parental data.
Spatial Proximity Scaffolding (Hi-C)
To achieve chromosome-scale phasing, researchers exploit the three-dimensional architecture of the nucleus. Chromosomes tend to occupy distinct spatial territories, meaning a DNA molecule on the maternal chromosome 1 is physically much closer to other regions of the maternal chromosome 1 than it is to its paternal counterpart.
By capturing these spatial interactions via Hi-C sequencing, frameworks can group distant contigs into their respective parental origins. This approach was utilized by Lehmann et al. in Finding Nemo’s Genes: A chromosome‐scale reference assembly of the genome of the orange clownfish Amphiprion percula and by Yoo et al. in Complete sequencing of ape genomes to generate gapless, telomere-to-telomere reference genomes that preserve structural variations across entire chromosomes.
Combinatorial Optimization Paradigms
From a mathematical perspective, read-based phasing can be framed as an optimization problem: given a set of fragmented, noisy reads, how do we partition them into two sets that minimize conflicts?
One common framing is Haplotype Inference by Pure Parsimony (HIPP), which seeks to find the smallest possible set of unique haplotypes that can explain a given collection of genotypes. Because this problem is NP-hard, researchers have explored several computational frameworks to find exact or near-optimal solutions efficiently:
- Boolean Satisfiability (SAT): Lynce et al. introduced SHIPs in Efficient Haplotype Inference with Boolean Satisfiability, encoding the parsimony problem into a SAT formula. By applying symmetry-breaking constraints, they converted the combinatorial search into a highly optimized boolean evaluation.
- Pseudo-Boolean Optimization (PBO): Expanding on SAT encodings, Graça et al. demonstrated in Generic ILP vs Specialized 0-1 ILP for Haplotype Inference that specialized 0-1 integer programming solvers significantly outperform general-purpose linear programming tools like CPLEX by exploiting the boolean structure of allele choices.
- Genetic Algorithms: To handle larger search spaces, Tangherloni et al. developed GenHap in GenHap: A novel computational method based on genetic algorithms for haplotype assembly. This approach treats read assignment as an evolutionary optimization task, using a divide-and-conquer strategy across parallel architectures to scale up to modern long-read datasets (Tangherloni et al.; Tangherloni).
To understand the fundamental boundaries of these optimization methods, Kamath et al. mapped haplotype assembly to the decoding of convolutional codes in Optimal Haplotype Assembly from High-Throughput Mate-Pair Reads, establishing the exact information-theoretic limits and minimum sequencing coverage required for perfect reconstruction.
Why Phasing Matters for Downstream Biology
Resolving phase ambiguity is not just an algorithmic exercise; it is essential for understanding the functional mechanics of genomes.
Unmasking Structural and Epigenetic Variation
Large-scale structural variants (SVs), such as inversions and duplications, are highly prone to being misaligned or completely lost during collapsed assemblies. Sudmant et al. highlighted this in An integrated map of structural variation in 2,504 human genomes, showing that phased maps are required to understand how large structural changes are inherited alongside single-nucleotide variants.
Furthermore, phasing extends beyond the DNA sequence itself to the epigenetic layer. As Ni et al. demonstrated in DNA 5-methylcytosine detection and methylation phasing using PacBio circular consensus sequencing, linking DNA methylation states directly to specific haplotypes allows researchers to observe allele-specific regulatory mechanisms, revealing which parent's copy of a gene is actively silenced or expressed.
Resolving 3D Chromosome Conformation
In structural biology, unphased data introduces fundamental mathematical ambiguities. When mapping the three-dimensional folding of a genome using Hi-C, an unphased contact map mixes the interactions of both homologous chromosome copies.
As argued by Belyaeva et al. in Identifying 3D Genome Organization in Diploid Organisms via Euclidean Distance Geometry, reconstructing 3D genome structures from unphased contact frequencies is inherently non-identifiable using pairwise distance constraints alone. Without separating the contacts of the maternal copy from the paternal copy, the resulting 3D models are distorted averages. Using Bayesian inference frameworks, single-cell approaches like the one developed by Carstens in Inferential Structure Determination of Chromosomes from Single-Cell Hi-C Data help disentangle these homologous interactions, providing a clear view of individual chromosomal architectures.
Clinical Diagnostics and Complex Loci
Phasing is critical in medical genetics, particularly for highly polymorphic regions like the Major Histocompatibility Complex (MHC), which governs immune responses. Li et al. demonstrated in De novo genome assembly depicts the immune genomic characteristics of cattle that haplotype-resolved assemblies are required to capture the true structural diversity of immune loci, which would otherwise be lost in a collapsed consensus reference.
Compound Heterozygosity (Phased View):
Scenario A (Trans - Pathogenic): ---(Mutation 1)------------------------ (Maternal)
------------------------(Mutation 2)--- (Paternal)
[Both copies damaged -> Disease]
Scenario B (Cis - Benign): ---(Mutation 1)---------(Mutation 2)--- (Maternal)
--------------------------------------- (Paternal)
[One copy fully functional -> Healthy]
In clinical diagnostics, phasing allows doctors to distinguish between benign variations and pathogenic compound heterozygosity—a state where an individual inherits two different mutations in the same gene. If both mutations are on the same chromosome (cis), the other chromosome remains fully functional, and the individual is typically healthy. If the mutations are on different chromosomes (trans), both copies of the gene are broken, leading to disease.
By resolving these spatial relationships, targeted long-read sequencing approaches, such as the one developed by Sun et al. in Targeted long-read sequencing enables higher diagnostic yield of ADPKD by accurate PKD1 genetic analysis, can successfully bypass nearly identical pseudogenes to diagnose complex genetic disorders with high precision.
Key Foundational Work
An MDL Method for Finding Haplotype Blocks and for Estimating the Strength of Haplotype Block Boundaries (2003) — contributed 2 concept elements to this direction.
A Markov Chain Approach to Reconstruction of Long Haplotypes (2004) — contributed 1 concept elements to this direction.