摘要翻译：
问题简约性单倍型(PH)要求最小的单倍型集合来解释给定的基因型集合，而问题最小完美系统发育单倍型(MPPH)要求最小的单倍型集合来允许单倍型嵌入完美系统发育树，这是一个有生物学动机限制的进化树。对于PH，我们扩展了最近的工作，在(k，l)有界实例的框架内，进一步映射了easy实例和hard实例之间的界面，其中输入矩阵的每列和每行的个数是受限制的。通过探索MPPH的可处理性边界，我们为该问题提供了第一个具体的、积极的结果，支持这些结果的算法为未来如何进一步解决MPPH提供了新的见解。此外，根据输入矩阵列的性质，构造了PH和MPPH多项式时间逼近算法。我们最后概述了PH和MPPH中有趣的开放问题。
---
英文标题：
《Shorelines of islands of tractability: Algorithms for parsimony and
  minimum perfect phylogeny haplotyping problems》
---
作者：
Leo van Iersel, Judith Keijsper, Steven Kelk, Leen Stougie
---
最新提交年份：
2007
---
分类信息：

一级分类：Quantitative Biology        数量生物学
二级分类：Other Quantitative Biology        其他定量生物学
分类描述：Work in quantitative biology that does not fit into the other q-bio classifications
不适合其他q-bio分类的定量生物学工作
--
一级分类：Quantitative Biology        数量生物学
二级分类：Populations and Evolution        种群与进化
分类描述：Population dynamics, spatio-temporal and epidemiological models, dynamic speciation, co-evolution, biodiversity, foodwebs, aging; molecular evolution and phylogeny; directed evolution; origin of life
种群动力学；时空和流行病学模型；动态物种形成；协同进化；生物多样性；食物网；老龄化；分子进化和系统发育；定向进化；生命起源
--

---
英文摘要：
  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, an evolutionary tree with biologically-motivated restrictions. For PH, we extend recent work by further mapping the interface between ``easy'' and ``hard'' instances, within the framework of (k,l)-bounded instances where the number of 2's per column and row of the input matrix is restricted. 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 addition, we construct for both PH and MPPH polynomial time approximation algorithms, based on properties of the columns of the input matrix. We conclude with an overview of intriguing open problems in PH and MPPH.
---
PDF链接：
https://arxiv.org/pdf/q-bio/0605024