Haplotyping populations by pure parsimony based on compatible genotypes and greedy heuristics

I. Lin Wang, Hui E. Yang

研究成果: Article同行評審

1 引文 斯高帕斯(Scopus)


The population haplotype inference problem based on the pure parsimony criterion (HIPP) infers an m × n genotype matrix for a population by a 2m × n haplotype matrix with the minimum number of distinct haplotypes. Previous integer programming based HIPP solution methods are time-consuming, and their practical effectiveness remains unevaluated. On the other hand, previous heuristic HIPP algorithms are efficient, but their theoretical effectiveness in terms of optimality gaps has not been evaluated, either. We propose two new heuristic HIPP algorithms (MGP and GHI) and conduct more complete computational experiments. In particular, MGP exploits the compatible relations among genotypes to solve a reduced integer linear programming problem so that a solution of good quality can be obtained very quickly; GHI exploits a weight mechanism to selects better candidate haplotypes in a greedy fashion. The computational results show that our proposed algorithms are efficient and effective, especially for solving cases with larger recombination rates.

頁(從 - 到)9798-9809
期刊Applied Mathematics and Computation
出版狀態Published - 2011 8月 1

All Science Journal Classification (ASJC) codes

  • 計算數學
  • 應用數學


深入研究「Haplotyping populations by pure parsimony based on compatible genotypes and greedy heuristics」主題。共同形成了獨特的指紋。