Chen Wen-Pei, Hung Che-Lun, Lin Yaw-Ling
Department of Applied Chemistry, Providence University, Taichung 433, Taiwan.
Biomed Res Int. 2013;2013:984014. doi: 10.1155/2013/984014. Epub 2013 Nov 11.
Patterns of linkage disequilibrium plays a central role in genome-wide association studies aimed at identifying genetic variation responsible for common human diseases. These patterns in human chromosomes show a block-like structure, and regions of high linkage disequilibrium are called haplotype blocks. A small subset of SNPs, called tag SNPs, is sufficient to capture the haplotype patterns in each haplotype block. Previously developed algorithms completely partition a haplotype sample into blocks while attempting to minimize the number of tag SNPs. However, when resource limitations prevent genotyping all the tag SNPs, it is desirable to restrict their number. We propose two dynamic programming algorithms, incorporating many diversity evaluation functions, for haplotype block partitioning using a limited number of tag SNPs. We use the proposed algorithms to partition the chromosome 21 haplotype data. When the sample is fully partitioned into blocks by our algorithms, the 2,266 blocks and 3,260 tag SNPs are fewer than those identified by previous studies. We also demonstrate that our algorithms find the optimal solution by exploiting the nonmonotonic property of a common haplotype-evaluation function.
连锁不平衡模式在全基因组关联研究中起着核心作用，这类研究旨在识别导致常见人类疾病的基因变异。人类染色体中的这些模式呈现出块状结构，高连锁不平衡区域被称为单倍型块。一小部分单核苷酸多态性（SNP），即标签SNP，足以捕获每个单倍型块中的单倍型模式。先前开发的算法在试图最小化标签SNP数量的同时，将单倍型样本完全划分为各个块。然而，当资源限制使得无法对所有标签SNP进行基因分型时，限制它们的数量就很有必要。我们提出了两种动态规划算法，纳入了许多多样性评估函数，用于使用有限数量的标签SNP进行单倍型块划分。我们使用所提出的算法对21号染色体单倍型数据进行划分。当样本通过我们的算法完全划分为各个块时，得到的2266个块和3260个标签SNP比先前研究识别出的要少。我们还证明，我们的算法通过利用常见单倍型评估函数的非单调特性找到了最优解。
