We consider the NP-hard TREE CONTAINMENT problem that has important applications in phylogenetics. The problem asks if a given single-rooted leaf-labeled network ("phylogenetic network") N "contains" a given leaf-labeled tree ("phylogenetic tree") T. We develop a fast algorithm for the case that N is a phylogenetic tree in which multiple leaves might share a label. Generalizing a previously known decomposition scheme lets us leverage this algorithm, yielding linear-time algorithms for so-called "reticulation visible" networks and "nearly stable" networks. While these are special classes of networks, they rank among the most general of the previously considered cases. We also present a dynamic programming algorithm that solves the general problem in O(3~(t~*)·|N|·|T|) time, where the parameter t~* is the maximum number of "tree components with unstable roots" in any block of the input network. Notably, t~* is stronger (that is, smaller on all networks) than the previously considered parameter "number of reticulations" and even the popular parameter "level" of the input network.
展开▼
机译：我们认为，在系统发育重要的应用NP难TREE遏制问题。这道题如果给定的单根叶标记的网络（“演化网络”）N“包含”一个给定叶标记的树（“进化树”）T.我们开发的情况下的快速算法，N是一个系统发育树，其中多个叶片可以共享的标签。归纳之前已知的分解方案使我们能够充分利用这种算法，产生线性时间的算法所谓的“网状可见的”网络和“近稳定”的网络。虽然这些都是网络的特殊班，他们的排名中最普遍的以前认为的案件。我们还提出一种动态编程算法，解决了在O普遍问题（3〜（T〜*）·| N |·| T |）时间，其中，所述参数t〜*是“树组分不稳定的根的最大数目“在输入网络的任何块。值得注意的是，吨〜*更强（即，在所有网络上小于）预先考虑参数“网眼数”和输入网络的连流行参数“电平”。
展开▼
