A dynamic programming algorithm for haplotype block partitioning
AUTOR(ES)
Zhang, Kui
FONTE
The National Academy of Sciences
RESUMO
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.
ACESSO AO ARTIGO
http://www.pubmedcentral.nih.gov/articlerender.fcgi?artid=124231Documentos Relacionados
- A dynamic programming algorithm for finding alternative RNA secondary structures.
- Incorporating chemical modification constraints into a dynamic programming algorithm for prediction of RNA secondary structure
- A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an RNA secondary structure
- A filter algorithm for nonlinear semidefinite programming
- Haplotype Block Partitioning and Tag SNP Selection Using Genotype Data and Their Applications to Association Studies