TY - GEN
T1 - Complete parsimony haplotype inference problem and algorithms
AU - Jäger, Gerold
AU - Climer, Sharlee
AU - Zhang, Weixiong
PY - 2009
Y1 - 2009
N2 - Haplotype inference by pure parsimony (HIPP) is a well-known paradigm for haplotype inference. In order to assess the biological significance of this paradigm, we generalize the problem of HIPP to the problem of finding all optimal solutions, which we call complete HIPP. We study intrinsic haplotype features, such as backbone haplotypes and fat genotypes as well as equal columns and decomposability. We explicitly exploit these features in three computational approaches which are based on integer linear programming, depth-first branch-and-bound, and a hybrid algorithm that draws on the diverse strengths of the first two approaches. Our experimental analysis shows that our optimized algorithms are significantly superior to the baseline algorithms, often with orders of magnitude faster running time. Finally, our experiments provide some useful insights to the intrinsic features of this interesting problem.
AB - Haplotype inference by pure parsimony (HIPP) is a well-known paradigm for haplotype inference. In order to assess the biological significance of this paradigm, we generalize the problem of HIPP to the problem of finding all optimal solutions, which we call complete HIPP. We study intrinsic haplotype features, such as backbone haplotypes and fat genotypes as well as equal columns and decomposability. We explicitly exploit these features in three computational approaches which are based on integer linear programming, depth-first branch-and-bound, and a hybrid algorithm that draws on the diverse strengths of the first two approaches. Our experimental analysis shows that our optimized algorithms are significantly superior to the baseline algorithms, often with orders of magnitude faster running time. Finally, our experiments provide some useful insights to the intrinsic features of this interesting problem.
UR - http://www.scopus.com/inward/record.url?scp=70350397064&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-04128-0_31
DO - 10.1007/978-3-642-04128-0_31
M3 - Conference contribution
AN - SCOPUS:70350397064
SN - 3642041272
SN - 9783642041273
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 337
EP - 348
BT - Algorithms - ESA 2009 - 17th Annual European Symposium, Proceedings
T2 - 17th Annual European Symposium on Algorithms, ESA 2009
Y2 - 7 September 2009 through 9 September 2009
ER -