A dynamic programming algorithm for haplotype block partitioning

TLDR

Haplotype block partitioning relies on quality measures that vary by application, and prior work by Patil et al. sought blocks of limited haplotype diversity on chromosome 21. This study develops a dynamic programming algorithm to minimize the number of representative SNPs needed to capture most common haplotypes within each block. The algorithm is applied to chromosome 21 haplotype data from Patil et al., using their criteria and also a diversity‑based criterion to identify blocks.

Abstract

We develop a dynamic programming algorithm for haplotype block partitioning to minimize the number of representative single nucleotide polymorphisms (SNPs) required to account for most of the common haplotypes in each block. Any measure of haplotype quality can be used in the algorithm and of course the measure should depend on the specific application. The dynamic programming algorithm is applied to analyze the chromosome 21 haplotype data of Patil et al. [Patil, N., Berno, A. J., Hinds, D. A., Barrett, W. A., Doshi, J. M., Hacker, C. R., Kautzer, C. R., Lee, D. H., Marjoribanks, C., McDonough, D. P., et al. (2001) Science 294, 1719–1723], who searched for blocks of limited haplotype diversity. Using the same criteria as in Patil et al. , we identify a total of 3,582 representative SNPs and 2,575 blocks that are 21.5% and 37.7% smaller, respectively, than those identified using a greedy algorithm of Patil et al . We also apply the dynamic programming algorithm to the same data set based on haplotype diversity. A total of 3,982 representative SNPs and 1,884 blocks are identified to account for 95% of the haplotype diversity in each block.