A dynamic programming algorithm for haplotype block partitioning.

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Haplotype block partitioning is crucial for analyzing genetic variation.
• Previous methods, like greedy algorithms, may not be optimal for minimizing representative markers.
• Identifying blocks with limited haplotype diversity is key for genetic association studies.

Purpose of the Study:

• To develop a dynamic programming algorithm for haplotype block partitioning.
• To minimize the number of representative single nucleotide polymorphisms (SNPs) needed to capture common haplotypes.
• To apply and evaluate the algorithm on chromosome 21 haplotype data.

Main Methods:

• Developed a dynamic programming algorithm for haplotype block partitioning.
• Algorithm accommodates various haplotype quality measures.
• Applied the algorithm to chromosome 21 haplotype data from Patil et al. (2001).

Main Results:

• Identified 3,582 representative SNPs and 2,575 blocks using Patil et al.'s criteria, achieving 21.5% and 37.7% reduction, respectively, compared to a greedy algorithm.
• When optimizing for haplotype diversity, identified 3,982 representative SNPs and 1,884 blocks capturing 95% of diversity.
• Demonstrated significant reduction in block and SNP numbers.

Conclusions:

• The dynamic programming algorithm offers a more efficient approach to haplotype block partitioning.
• This method effectively reduces the number of required SNPs while preserving essential haplotype information.
• The algorithm provides a valuable tool for genomic analysis and identifying regions of genetic interest.