Beaches of islands of tractability : algorithms for parsimony and minimum perfect phylogeny haplotyping problems

L.J.J. Iersel, van, J.C.M. Keijsper, S.M. Kelk, L. Stougie

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

2 Citations (Scopus)

Abstract

The problem Parsimony Haplotyping (PH) asks for the smallest set of haplotypes which can explain a given set of genotypes, and the problem Minimum Perfect Phylogeny Haplotyping (MPPH) asks for the smallest such set which also allows the haplotypes to be embedded in a perfect phylogeny evolutionary tree, a well-known biologically-motivated data structure. For PH we extend recent work of [17] by further mapping the interface between "easy" and "hard" instances, within the framework of (k, l)-bounded instances. By exploring, in the same way, the tractability frontier of MPPH we provide the first concrete, positive results for this problem, and the algorithms underpinning these results offer new insights about how MPPH might be further tackled in the future. In both PH and MPPH intriguing open problems remain.
Original languageEnglish
Title of host publicationAlgorithms in Bioinformatics (Proceedings 6th International Workshop, WABI 2006, Zurich, Switzerland, September 11-13, 2006)
EditorsP. Bücher, B.M.E. Moret
Place of PublicationBerlin
PublisherSpringer
Pages80-91
ISBN (Print)3-540-39583-0
DOIs
Publication statusPublished - 2006

Publication series

NameLecture Notes in Computer Science
Volume4175
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Beaches of islands of tractability : algorithms for parsimony and minimum perfect phylogeny haplotyping problems'. Together they form a unique fingerprint.

Cite this