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
Complete Parsimony Haplotype Inference Problem and Algorithms
Computer Science Institute, University of Halle-Wittenberg, Germany.
School of Medicine, Washington University, United states.
Department of Computer Science/Department of Genetics, Washington University, United States.
2009 (English)In: Proceedings of 17th Annual European Symposium on Algorithms (ESA 2009) / [ed] A. Fiat and P. Sanders, Berlin-Heidelberg: Springer Berlin-Heidelberg , 2009, 337-348 p.Conference paper, Published paper (Refereed)
Abstract [en]

Haplotype inference by pure parsimony (HIPP) is a wellknown 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.

Place, publisher, year, edition, pages
Berlin-Heidelberg: Springer Berlin-Heidelberg , 2009. 337-348 p.
Series
Lecture Notes in Computer Science, Volume 5757
National Category
Bioinformatics (Computational Biology)
Identifiers
URN: urn:nbn:se:umu:diva-84448OAI: oai:DiVA.org:umu-84448DiVA: diva2:684110
Conference
17th Annual European Symposium on Algorithms (ESA 2009)
Available from: 2014-01-07 Created: 2014-01-07 Last updated: 2014-12-19Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Jäger, Gerold
Bioinformatics (Computational Biology)

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 37 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