Paper Info
Title
Beaches of islands of tractability: algorithms for parsimony and minimum perfect phylogeny haplotyping problems
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.
Year
DOI
Venue
2006
10.1007/11851561_8
WABI
Keywords
Field
DocType
smallest set,perfect phylogeny evolutionary tree,problem minimum perfect phylogeny,problem parsimony haplotyping,recent work,positive result,mpph intriguing open problem,tractability frontier,minimum perfect phylogeny,new insight,bounded instance,evolutionary trees,data structure,genetics
Data structure,Combinatorics,Phylogenetic tree,Computer science,Haplotype,Algorithm,Bioinformatics,Perfect phylogeny
Conference
Volume
ISSN
ISBN
4175
0302-9743
3-540-39583-0
Citations 
PageRank 
References 
2
0.37
17
Authors
4
Name
Order
Citations
PageRank
Leo van Iersel121524.58
J. C. M. Keijsper2393.93
Steven Kelk319325.60
Leen Stougie4892107.93