Grouping preprocess to accurately extend application of EM algorithm to haplotype inference.

Area of Science:

• Genetics and Bioinformatics
• Medical Science
• Computational Biology

Background:

• Haplotype inference is crucial for medical science, particularly in genome-wide association studies (GWAS).
• The conventional expectation-maximization (EM) algorithm for haplotype inference is computationally expensive due to its exponential cost related to heterozygous loci, limiting its application.
• A need exists for efficient haplotype inference methods applicable to larger genetic datasets.

Purpose of the Study:

• To propose a novel, computationally efficient method for haplotype inference.
• To enable the analysis of larger haplotype blocks containing tens of single nucleotide polymorphism (SNP) loci.
• To provide an alternative to the conventional EM algorithm with equivalent inference criteria but improved scalability.

Main Methods:

• Developed a haplotype inference method incorporating a haplotype-grouping preprocess.
• Exploited symmetrical and inclusive haplotype relationships based on Hardy-Weinberg equilibrium to reduce computational cost.
• Maintained exact equivalence to the criteria of the expectation-maximization (EM) algorithm.

Main Results:

• The proposed method empirically accommodates up to several tens of single nucleotide polymorphism (SNP) loci within a single haplotype block.
• The computational cost is significantly reduced compared to the conventional EM algorithm.
• Testing on real data sets demonstrated a wider range of applications than the EM algorithm.

Conclusions:

• The novel haplotype inference method offers a scalable and efficient alternative to the traditional EM algorithm.
• This approach expands the applicability of haplotype inference in genetic studies, including GWAS.
• The method provides accurate haplotype inference with reduced computational burden, facilitating larger-scale genetic analyses.