A Linear Space Algorithm for Haplotype Blocks Partitioning Using Limited Number of Tag SNPs

Abstract

The pattern of linkage disequilibrium (LD) plays a cen- tral role in genome-wide association studies of identi- fying genetic variation responsible of common human diseases. A Single Nucleotide Polymorphism or SNP is a DNA sequence variation occurring when a sin- gle nucleotide in the genome di®ers between members of species. Recent studies show that the patterns of linkage disequilibrium observed in human chromosome reveal a block-like structure; the high LD regions are called haplotype blocks, and furthermore, a small sub- set of SNPs, called tag SNPs, is su±cient to capture the haplotype patterns in each haplotype block. Both Patil [18] and Zhang et al. [24] have proposed algo- rithms to partition haplotype sample into blocks fully under the circumstances of requiring minimal number of tag SNPs. However, when resources are limited, in- vestigators and biologists may not be able to genotype all the tag SNPs and instead must restrict the num- ber of tag SNPs used in their studies. In this paper, we examine several haplotype block diversity evalua- tion functions and propose dynamic programming al- gorithms for haplotype block partitioning with using the limited number of tag SNPs. We implement these algorithms and analyze the chromosome 21 haplotype data given by Patil et al. [18]. When the sample is par- titioned into blocks fully, we identify a total of 2,266 blocks and 3,260 tag SNPs which is smaller than those identi¯ed by Zhang et al. [24]. We demonstrate that Zhang's algorithm does not ¯nd the optimal solution due to ignoring the non-monotonic property of com- mon haplotype evaluation function. The algorithms described have been implemented in the web-based system as the analysis tools for bioinformaticists and geneticists.