TY - JOUR
T1 - Haplotyping populations by pure parsimony based on compatible genotypes and greedy heuristics
AU - Wang, I. Lin
AU - Yang, Hui E.
N1 - Funding Information:
I-Lin Wang was partly supported by the National Science Council of Taiwan under Grant NSC96-2221-E-006-015 .
PY - 2011/8/1
Y1 - 2011/8/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=79958179325&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79958179325&partnerID=8YFLogxK
U2 - 10.1016/j.amc.2011.04.073
DO - 10.1016/j.amc.2011.04.073
M3 - Article
AN - SCOPUS:79958179325
SN - 0096-3003
VL - 217
SP - 9798
EP - 9809
JO - Applied Mathematics and Computation
JF - Applied Mathematics and Computation
IS - 23
ER -