Hybrid Approaches for the Selection of Tag SNPs based on Block Partition and Linkage Disequilibrium

Abstract. Studies over recent years have revealed that a small subset of SNPs (called tag SNPs) is sufficient to capture the haplotype diversity in high linkage disequilibrium (LD) regions. Methods for finding tag SNPs are mainly based on either the assumption that the haplotypes in the human genome conform to a block-like structure or based on the extent of LD across the human genome. The block-based methods identify tag SNPs that are compression of haplotypes in each block but is sensitive to the the predefined block partition. On the other hand, the LD-based methods is free from the block partition but often produce numerous singleton tag SNPs having no sufficient LD with others. We design and implement two hybrid methods which reduce the number of tag SNPs by both considering the block-like structure and the extent of LD in distinct blocks. A faster algorithm is proposed to boost the computational efficiency of LD among all pairs of SNPs and is internally used by these two hybrid methods. The experimental results indicate that the hybrid methods not only reduce the numbers of tag SNPs but also run much faster than existing LD- or block-based method