New algorithm preserves haplotype diversity while correcting long-read sequencing errors

Genome assembly pipelines often begin with a deceptively simple step: correcting the errors that inevitably creep into long-read sequencing data. But for organisms with more than one set of chromosomes, that step carries a hidden trap. Correcting a read too aggressively can erase the very differences between maternal and paternal chromosomes that researchers are trying to map. The researchers now report a mathematically grounded way to fix sequencing errors while keeping those haplotype-specific differences intact, and they have shown that their approach matches the accuracy of the best existing tools on human and plant genomes.

Rather than relying on ad-hoc heuristics or deep learning models, the researchers framed the correction task as a combinatorial optimization problem inspired by the minimum error correction framework used in reference-based haplotype phasing. They also proved something important about their formulation: solving it exactly is NP-hard, meaning no efficient algorithm is expected to exist for the general case.

The problem arises because long reads, despite their length and improving accuracy, still carry errors that can rival the biological differences between chromosome copies. In humans, the two haplotypes are approximately 99.9 percent identical, so reads from the maternal and paternal chromosomes overlap frequently. Current Pacific Biosciences reads have error rates below 0.5 percent, while Oxford Nanopore reads range between 1 and 5 percent, yet certain regions such as homopolymers remain error-prone. A naive majority-vote correction across all overlapping reads would smooth away true biological variation, treating genuine haplotype differences as if they were sequencing mistakes.

Existing tools handle this challenge in different ways. Hifiasm, a popular genome assembler, uses heuristics to identify heterozygous loci and discards overlapping reads that do not match the target read at those positions. Herro, a dedicated correction tool, employs a supervised learning model built from convolutional blocks and a transformer encoder. PECAT applies a heuristic scoring strategy based on a partial-order alignment graph, and DeChat combines a de Bruijn graph pre-correction with variant-aware multiple sequence alignment. These methods work well in practice, but their logic is embedded in heuristics or learned models rather than explicit mathematical objectives.

HALE takes a different route. For each read to be corrected, called the target read, the algorithm builds a multiple sequence alignment between a substring of that read and substrings of overlapping reads. The goal is to select a subset of those overlapping reads that truly originate from the same haplotype and genomic region as the target read, so that a simple majority vote within that subset yields an accurate correction. The researchers formalized this as an optimization problem: choose a fixed number of vectors from the alignment, along with a consensus center, to maximize the total agreement across the selected reads and the target. Once the optimal subset is found, the consensus center becomes the corrected version of the target substring.

Proving the problem NP-hard was no small feat. The researchers reduced the Max-Cut problem, a classic hard problem in graph theory, to their formulation, using an elegant construction based on Hadamard codes, collections of mutually orthogonal vectors with useful norm properties. The proof shows that any polynomial-time algorithm for the general correction problem would imply an efficient solution to Max-Cut, which is considered unlikely. Interestingly, their formulation differs from reference-guided phasing tools such as WhatsHap, which partition all reads exhaustively into two clusters. HALE instead seeks a subset of reads matching the target’s haplotype and region, a design better suited to de novo assembly, where no reference genome exists and the number of read clusters is not fixed in advance.

Because the exact problem is computationally hard, the team built practical heuristics into the implementation. They use Minimap2 to compute overlaps among all reads, then construct multiple sequence alignments following the star alignment approach adapted from Herro. The alignment is divided into windows of 4096 base pairs, and only the top 20 overlapping substrings by sequence identity are retained in each window. Crucially, the algorithm identifies informative alignment columns, those where at least two distinct characters occur with a minimum frequency, and removes columns where all reads agree, since the latter carry little value for distinguishing true overlaps from false ones. The reduced problem is then solved exactly by brute-force search, evaluating all possible subsets of the chosen size, which remains feasible because the alignment has been shrunk so dramatically.

The evaluation used publicly available PacBio HiFi datasets from a diploid human sample, HG002, and a haploid Arabidopsis thaliana sample, at 40-fold and 60-fold sequencing coverage. For the human data, the team focused on chromosome 9, which is rich in satellite DNA tandem repeats and considered one of the more challenging chromosomes to assemble. Because no ground truth exists for real sequencing errors, the researchers mapped corrected reads to high-quality reference assemblies and measured Q-concordance, a log-scaled measure of sequence identity, along with counts of mismatch and indel errors. Only reads that were fully corrected by all methods were compared, ensuring a fair contest against Hifiasm, which does not chop uncorrectable segments.

The results showed HALE achieving accuracy comparable to Herro and Hifiasm, with all three methods delivering more than a tenfold improvement in read accuracy over raw, uncorrected reads. On the diploid human data, HALE showed a marginally higher percentage of reads containing at least one mismatch error at 40-fold coverage, though that difference declined at 60-fold. The team also compared HALE against two simplified versions of itself that skip the optimization step. One naive version applied a majority vote across all columns, and while its overall Q-concordance was surprisingly similar to HALE’s, HALE provided a significant improvement in correcting mismatch errors, confirming that the optimization preserves haplotype variation that a direct consensus would eliminate. The other naive version, which left informative columns untouched, produced far more indel errors, since many informative columns actually reflect clustered sequencing errors rather than biological variation. On the haploid Arabidopsis data, where haplotype preservation matters less, the naive consensus approach performed on par with or slightly better than HALE, exactly as theory would predict.

Runtime figures favor HALE over Herro in the correction step itself: on the 60-fold human chromosome 9 dataset, HALE needed 9 minutes on 64 CPU threads, while Herro required 10 minutes on a server with four NVIDIA A100 GPUs, though Herro’s GPU acceleration and Hifiasm’s tightly integrated overlap computation complicate direct comparisons. The all-vs-all overlap computation, which took Minimap2 26 minutes, remains the bottleneck for HALE. The authors are candid about limitations: the tool processes alignment windows independently, which can falter in noisy or low-coverage regions, and its key parameters were set empirically rather than derived from first principles. They also note that HALE is not yet a practical replacement for state-of-the-art tools, and that extending it to noisier nanopore reads is future work. Still, the study demonstrates that a theoretically rigorous, interpretable formulation can match the performance of deep learning and heuristic methods, offering genome assembly a foundation built on provable principles rather than undocumented engineering.

Subject of Research: Haplotype-aware error correction of long-read sequencing data using a provably hard optimization formulation

Article Title: Haplotype-aware long-read error correction

Article References: Barak, P., Gibney, D., & Jain, C. (2026). Haplotype-aware long-read error correction. Algorithms for Molecular Biology, 21(1), Article 13. https://doi.org/10.1186/s13015-026-00302-3

Image Credits: AI Generated

DOI: 10.1186/s13015-026-00302-3

Keywords: genome assembly, long-read sequencing, error correction, haplotype, NP-hard, combinatorial optimization, PacBio HiFi, minimum error correction, bioinformatics, HG002, Arabidopsis thaliana, algorithm design