Complete parsimony haplotype inference problem and algorithms

Gerold Jäger, Sharlee Climer, Weixiong Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Scopus citations


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.

Original languageEnglish
Title of host publicationAlgorithms - ESA 2009 - 17th Annual European Symposium, Proceedings
Number of pages12
StatePublished - 2009
Event17th Annual European Symposium on Algorithms, ESA 2009 - Copenhagen, Denmark
Duration: Sep 7 2009Sep 9 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5757 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference17th Annual European Symposium on Algorithms, ESA 2009


Dive into the research topics of 'Complete parsimony haplotype inference problem and algorithms'. Together they form a unique fingerprint.

Cite this