Polyploid Haplotype Assembly from Sequencing Reads

20 concepts17 papers1 proposal

Haplotype assembly is the process of reconstructing the individual genetic sequences—or haplotypes—that an organism inherits from its parents. While humans are diploid, carrying two sets of chromosomes, many other organisms are polyploid, possessing three or more sets. This occurs frequently in economically vital crops, such as wheat and potatoes, as well as in the heterogeneous genomic landscapes of cancerous tumors.

Reconstructing these sequences is computationally difficult because modern sequencing technologies do not read entire chromosomes at once. Instead, they produce millions of short, fragmented "reads." The assembly task requires correctly assigning each fragment to its chromosome of origin. As Hashemi et al. and Barik and Vikalo note, this problem is NP-hard even for diploids, but it becomes exponentially more complex as the number of chromosome copies (ploidy) increases.

The Combinatorial Explosion of Ploidy

The primary challenge in polyploid assembly is the "combinatorial explosion" of possible allele combinations. In a diploid organism, a specific genetic site (locus) with two different alleles has only two possible phasings. In a polyploid organism with ploidy $k$, the number of ways to distribute alleles across $k$ chromosomes grows rapidly. Berger et al. and Shen et al. emphasize that this complexity makes traditional algorithms, which often assume a standard diploid genome, computationally infeasible for higher-order organisms.

Furthermore, many existing bioinformatics pipelines were built on the "diploidy assumption." Stephens et al. argue that this constraint makes standard tools unsuitable for studying polyploid species or the sub-populations found in metagenomic mixtures and tumor samples.

Probabilistic and Optimization Frameworks

To overcome the NP-hard nature of the problem, researchers have moved toward probabilistic models and global optimization techniques.

  • Bayesian Inference: Berger et al. introduced HapTree, a Bayesian framework that uses a tree-based structure to explore the most likely haplotype combinations. Similarly, Ahn and Vikalo proposed ParticleHap, which applies a sequential Monte Carlo algorithm (a "particle filter") to identify genotypes and assemble haplotypes simultaneously, correcting errors on the fly.
  • Matrix and Tensor Decomposition: Some methods treat the assembly problem as a data completion task. Barik and Vikalo framed it as a rank-one matrix completion problem, providing theoretical guarantees for accuracy. Hashemi et al. extended this logic to higher dimensions with AltHap, using sparse tensor decomposition to handle the multi-chromosomal nature of polyploids efficiently.
  • Mathematical Programming: Das developed SDhaP, which reformulates haplotype assembly as a low-rank semi-definite program (SDP). This approach allows for faster execution and better accuracy in minimizing error correction objectives compared to earlier combinatorial methods.

Neural Networks and Graph Representations

Recent advancements have shifted toward representing sequencing data as graphs, where nodes represent reads and edges represent the likelihood that two reads belong to the same chromosome.

Ke and Vikalo introduced GAEseq, a graph auto-encoder that learns to cluster reads by their genomic origin, effectively ignoring sequencing errors. Building on this, Xue et al. proposed NeurHap, which treats assembly as a graph coloring problem. By using Graph Neural Networks (GNNs) to perform global searches for optimal colorings (where each color represents a distinct haplotype), the authors demonstrated significant performance gains in complex polyploid and viral datasets.

To capture relationships between reads that do not physically overlap, Consul and Ke introduced XHap, which utilizes Transformer networks to learn long-distance correlations. This allows the model to phase variants across much larger genomic distances than traditional overlap-based methods.

Scalability and High-Performance Computing

As sequencing throughput increases, the speed of assembly becomes a bottleneck. Zhou et al. developed KSNP, a tool using de Bruijn graphs that approaches "data-in" time, processing human haplotypes in roughly 30 minutes.

For the specific challenges of polyploidy, Tangherloni et al. proposed GenHap, which uses Genetic Algorithms and a "divide-and-conquer" strategy. By partitioning the genome into smaller sub-problems and solving them in parallel across multi-core architectures, the authors achieved substantial speedups while maintaining the flexibility needed to handle the increased chromosomal sets of polyploid organisms.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 17 papers
  2. Version 1 · 2026-10-04 · 23 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_polyploid_haplotype_assembly_74e00abf,
  title = {polyploid haplotype assembly},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/polyploid-haplotype-assembly/rdr_74e00abfdd5c4e4991766fcbc9533b6a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_polyploid_haplotype_assembly_74e00abf_v2,
  title = {polyploid haplotype assembly},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/polyploid-haplotype-assembly/rdr_74e00abfdd5c4e4991766fcbc9533b6a/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake