Haplotype Inference By Pure Parsimony Via A New Hybrid Algorithm

With the deepening of human life studies, research angle from macro to micro, to cells from individuals, from cell and molecular. Gene polymorphism is caused by gene fragments or mutation. A large number of studies show that, Numerous studies show that gene polymorphisms affect biological external shape, genetic disease, susceptible constitution of human. The genetic data has become an importent source of information. biological haplotypeinformation can provide more information of the gene. Methods for obtaining biological information is haplotype inference and haplotype assembly. This paper focuses on the problem of haplotype inference.Method for solving the haplotype inference problem can be divided into two kinds. One is the biology experiment methods, the advantage of this method is in solving the haplotype inference problem can get accurate information for the following experiments to provide more reliable and more accurate data. However, the disadvantage of this method is also obvious, time-consuming, high cost, and not a repeat. these have become the restricting of practical application. Another method is the calculation method, this method has the advantages of fast and accurate processing of large amounts of data. At present, the results of calculation method for the biological method has reduced the experimental data made great contributions, therefore, researchers designed efficient computational methods to solve the haplotype inference problem.In the haplotype inference problem, according to the Pure Parsimony principle, Haplotype Inference by Pure Parsimony(HIPP) problem is a given population genotype set, find can represent a set of haplotypes in the gene set, also asked the minimum number of different haplotype. Research has shown that, the computational complexity of this problem is NP hard.Whatever the precise algorithm or approximate algorithm, can solve the haplotype inference problem of thrift. The early researchers design precise algorithm to solve this problem, such as dynamic programming, linear programming. In recent years, with the development of gene sequencing technology promotion, more genetic data we could get. so the exact algorithm can not meet the demand of solving a large amount of data. Scientific research personnel to design more and more approximation algorithm to solve the HIPP problem. Although the approximate algorithm inaccuracy, but the approximate algorithm can handle the size of data that precise algorithms don`t, approximate algorithms can take a good solution in a very short period of time. Therefore, more and more of the approximate algorithm is designed, such as genetic algorithm, pseudo Boolean optimization algorithm.GTHap algorithm design based on Genetic algorithm and tabu search hybrid algorithm, joining the resolution pool and combined mutation strategy overcomes the shortcomings of genetic algorithm which the solution quality dependence on initialization. Adding random hopping strategies to overcome insufficiency of the tabu search out of local optimal capability. Consider the problem of structural features, join the greedy strategy. And in the population initialization,join the super individual strategy.In the SU-100 kb data set. The experiments prove that each method is effective. In the verification strategy effectiveness after design a set of comparative experiments, in the same running time, solution quality of the GTHap algorithm is much better than RPoly algorithm and RPoly1000 algorithm which is best algorithm in SU-100 kb data set. Although the GTHap algorithm outperforms the other algorithms, but in case of individual problems, GTHap algorithm is not the best results, in the future work, the heuristic function to try to design the need for better, and better side strategies to get better results.