Research On A Parameterized Algorithm For The Haplotype Assembly Problem Weighted Minimum Letter Flips

Haplotype detection has expansive application in inherited gene's orientation,medicine reaction's research and individual identification. The cost of time and money is too expensive to detect the individual haplotype under the current experiment technique,so the use of computer to confirm the individual haplotype has great significance.Haplotye detection can be classified into two classes:Haplotye assembly problem and haplotype inference problem.This paper mainly does research on models and algorithms of haplotype assembly problem.Because most of the models are NP-hard,if the number of fragments and the SNPs is biggish,there is few feasible accurate algorithms.But the approximation of approximate algorithms is uncertain,such as the heuristic algorithms,and these algorithms can't get the optimal result in most cases.So it has great significance to improve the time and space's efficiency of accurate algorithms.This paper emphasizes on how to make use of the parameter technique to reduce the time and space's complexity of computation models.It forwards a parameterize algorithm for the haplotype assembly problem Weighted Minimum Letter Flips(WMLF)which has the time complexity O(nk₂2^k2+mlogm+mk₁).This algorithm can get the accurate result quickly,and it is scalable and applicable in practice.Because the parameterized algorithm is an accurate algorithm and it has the property of low time and space's complexity,we can make use of parameterized algorithm to compare the haplotype reconstruction rate for different models.This paper does specific analysis on MSR,MFR,MEC,WMLF and MEC/GI,and forwards some new judge standard.After that we do a lot of experiments.Our analysis and results demonstrate new prospects on designing new computation models.