Minimal Positional Substring Cover: A Haplotype Threading Alternative to Li & Stephens Model.

Area of Science:

• Computational biology
• Genetics
• Bioinformatics

Background:

• The Li & Stephens (LS) hidden Markov model (HMM) is foundational for haplotype phasing and imputation but is computationally inefficient for large reference panels.
• LS HMM has linear time complexity (O(MN)), making it infeasible for biobank-scale datasets with millions of haplotypes.

Approach:

• Introduced the Minimal Positional Substring Cover (MPSC) problem as an alternative formulation of LS, enabling haplotype threading with time complexity independent of sample size (O(N)).
• Developed new algorithms for MPSC, including solution enumeration and optimal solutions (Length Maximal MPSC, h-MPSC), by identifying required regions and proposing an MPSC graph.
• Leveraged PBWT (Positional Burrows-Wheeler Transform) for smoothing to enhance algorithm robustness and explore the LS solution space for large panels.

Key Points:

• MPSC formulation allows for efficient haplotype threading on biobank-scale reference panels.
• New algorithms reveal the solution space of the LS HMM for large datasets.
• The approach provides insights into biobank-scale data characteristics.

Conclusions:

• The MPSC approach and associated algorithms overcome the scalability limitations of the LS HMM for large-scale haplotype reconstruction.
• This work enhances genotype imputation accuracy and provides a scalable method for analyzing large genetic datasets.
• The developed algorithms offer a pathway to understanding the solution space of haplotype phasing and imputation in massive cohorts.