A dynamic programming algorithm for haplotype block partitioning
A dynamic programming algorithm for haplotype block partitioning
复制标题
DOI：
10.1073/pnas.102186799
复制
发表时间：
2002-05-28
影响因子：
11.1
通讯作者：
Sun, FZ
中科院分区：
文献类型：
--
作者：
Zhang, K;Deng, MH;Sun, FZ
我们开发了一个动态规划算法的单倍型块分区，以尽量减少所需的代表性单核苷酸多态性（SNP）占大多数常见的单倍型在每个块的数量。单倍型质量的任何测量都可以用于算法中，当然测量应该取决于具体应用。应用动态规划算法来分析Patil等人[Patil，N.，Berno，A. J.，Hinds，D.一、巴雷特，W。一、Doshi，J.M.，哈克角R.，考茨尔角R.，Lee，D. H、Marjoribanks，C.，麦克多诺，D. P.的人，等人（2001）Science 294，1719-1723]，他们搜索了有限单倍型多样性的区块。使用与Patil等人相同的标准，我们鉴定了总共3，582个代表性SNPs和2，575个区块，它们分别比使用Patil等人的贪婪算法鉴定的那些小21.5%和37.7%。我们还将动态规划算法应用于基于单倍型多样性的相同数据集。总共鉴定了3，982个代表性SNP和1，884个区块，占每个区块中单倍型多样性的95%。
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.