umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
The complete parsimony haplotype inference problem and algorithms based on integer programming, branch-and-bound and Boolean satisfiability
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2016 (English)In: Journal of Discrete Algorithms, ISSN 1570-8667, E-ISSN 1570-8675, Vol. 37, 68-83 p.Article in journal (Refereed) Published
Resource type
Text
Abstract [en]

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 CHIPP. We study intrinsic haplotype features, such as backbone haplotypes and fat genotypesas well as equal columns and decomposability. We explicitly exploit these features in three computational approaches that are based on integer linear programming, depth-first branch-and-bound, and Boolean satisfiability. Further we introduce two hybrid algorithms that draw upon the diverse strengths of the 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 into the intrinsic features of this important problem.

Place, publisher, year, edition, pages
Elsevier, 2016. Vol. 37, 68-83 p.
Keyword [en]
Haplotype inference, Pure parsimony, Branch-and-bound, Integer programming, Boolean satisfiability
National Category
Algebra and Logic
Identifiers
URN: urn:nbn:se:umu:diva-124271DOI: 10.1016/j.jda.2016.06.001ISI: 000379021500007OAI: oai:DiVA.org:umu-124271DiVA: diva2:950597
Conference
2015 London Stringology Days and London Algorithmic Workshop (LSD & LAW)
Note

Special Issue

Available from: 2016-08-01 Created: 2016-07-29 Last updated: 2016-12-15Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Jäger, Gerold
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Journal of Discrete Algorithms
Algebra and Logic

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 15 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf