Haplotype Threading Using the Positional Burrows-Wheeler Transform.

Area of Science:

• Population Genetics
• Computational Biology
• Bioinformatics

Background:

• The classic Li and Stephens model uses hidden Markov models (HMMs) for haplotype threading.
• HMMs are computationally expensive for biobank-scale genetic panels due to their linear scaling with sample size.

Purpose of the Study:

• To develop a more efficient computational framework for haplotype threading.
• To address the scalability limitations of existing HMM-based methods for large genetic datasets.

Main Methods:

• Formulated haplotype threading as the Minimal Positional Substring Cover problem.
• Developed a solution using a sequential set of greedy set maximal matches.
• Bounded the solution space using left-most and right-most greedy solutions.

Main Results:

• The proposed greedy approach provides a novel method for solving the Minimal Positional Substring Cover problem.
• The solution space for haplotype threading can be effectively bounded.
• This framework lays the groundwork for variations of the problem.

Conclusions:

• The Minimal Positional Substring Cover formulation offers a theoretical basis for efficient haplotype threading.
• This approach has potential applications in genotype imputation and haplotype phasing, especially for large genetic datasets.
• Further generalization to include mismatches is a future research direction.