Block Partition and Tag Selection in Human SNP Haplotypes
Yaw-Ling Lin, Guan-Jie Hua, Wen-Pei Chen · 2010
Recent studies show that the patterns of linkage disequilibrium (LD) observed in human chromosome reveal a block-like structure; the high LD regions are called haplotype blocks. The existence of haplotype block structures has serious implications for association-based methods in mapping of disease genes. A Single Nucleotide Polymorphism or SNP is a DNA sequence variation occurring when a single nucleotide in the genome differs between members of species. In this paper, we propose several efficient algorithms for identifying haplotype blocks in the genome. Especially, we develop a dynamic programming algorithm for haplotype block partitioning to minimize the number of tagSNPs required to account for most of the common haplotypes in each block. We implement these algorithms and analyze the chromosome 21 haplotype data given by Patil et al. [1]. As a result, we identify a total of 2, 432 blocks (3, 333 tagSNPs) which is 41.2% (27%) smaller than those identified by Patil et al. or Zhang et al. [2].