On the Complexity of Rearrangement Problems under the Breakpoint Distance
On the Complexity of Rearrangement Problems under the Breakpoint Distance
复制标题
论断点距离下重排问题的复杂性
DOI：
10.1089/cmb.2013.0004
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Jakub Kovác
中科院分区：
文献类型：
--
作者：
Jakub Kovác
我们研究了Tannier等人的广义断点模型中重排问题的复杂性。并解决几个公开问题。我们改善了中位数问题的算法，并表明它等同于找到最大的基数非分数匹配（线性降低）的问题。另一方面，我们证明了更一般的小系统发育问题是NP-HARD。令人惊讶的是，我们表明四重奏系统发育已经是NP-HARD（甚至APX）。我们还表明，在Unichromosomal和多线性断点模型中，减半问题是NP-HARD，反驳了Tannier等人的猜想。有趣的是，这是断点模型中的第一个问题，而不是在双重切割和加入或逆转模型中。
We study the complexity of rearrangement problems in the generalized breakpoint model of Tannier et al. and settle several open questions. We improve the algorithm for the median problem and show that it is equivalent to the problem of finding maximum cardinality nonbipartite matching (under linear reduction). On the other hand, we prove that the more general small phylogeny problem is NP-hard. Surprisingly, we show that it is already NP-hard (or even APX-hard) for a quartet phylogeny. We also show that in the unichromosomal and the multilinear breakpoint model the halving problem is NP-hard, refuting the conjecture of Tannier et al. Interestingly, this is the first problem that is harder in the breakpoint model than in the double cut and join or reversal models.