The Research Of Haplotype Block Partitioning And Tag SNP Selection Algorithms Based On Various Diversity Functions

Single Nucleotide Polymorphism(SNP)is a DNA set of polymorphism based on the single nucleotide variations at the human genomic level.Patterns of linkage disequilibrium plays a central role in genome wide association studies aimed at identification 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 is sufficient to capture the haplotype patterns in each haplotype block.The existing algorithms completely partition a haplotype sample into blocks while attempting to minimize the number of tag SNPs.The main research results are as follows:Firstly,we propose two dynamic programming algorithms,incorporating many diversity evaluation functions,for haplotype block partitioning using a limited number of tag SNPs.The two algorithms use their own recurrence relation to divide the original problem into equivalent subproblems recursively.When the haplotype sample is fully partitioned into blocks by our algorithms,the number of blocks and tag SNPs are fewer than those identified by previous studies from our experimental results.We also demonstrate that our algorithms find the optimal solution by exploiting the nonmonotonic property of a common haplotype evaluation function.Furthermore,large amount of gene data with specific biological characteristics exist missing alleles.Many computer algorithms are designed to predict the missing alleles and change the data into the one that biologists want.At present,some methods of imputation mainly rely on the information of haplotypes exist in the test data.We use the block partitioning here and the test data in the block can be divided into two categories: intact and missing.The intact can be used as reference haplotype.The imputation of missing data can be completed by the statistical of frequency of haplotype in the block.In the paper,two categories of imputation without reference haplotype are described in detail,we show the experimental results of five different methods on haplotype data and the results are analysed and compared,we have the conclusion that the modified JH method does not filter the missing haplotype and can achieve better results.