论文标题
系统发育网络的最大覆盖子树
Maximum Covering Subtrees for Phylogenetic Networks
论文作者
论文摘要
基于树的系统发育网络可以大致定义为仅在原始树边缘之间添加弧而构建的叶片标记网络，具有用于建模进化历史的优雅特性。我们回答了弗朗西斯（Francis），塞普（Semple）和钢铁（Semple）和钢铁（Semple）和钢铁（Steel）的一个开放性问题，内容涉及确定系统发育网络距离基于树（包括非二元系统发育网络）的复杂性。我们表明，可以通过编码为最低成本最大流量问题来计算系统发育的系统发育树，以在多项式时间内计算系统发育网络中最大的节点数量。
Tree-based phylogenetic networks, which may be roughly defined as leaf-labeled networks built by adding arcs only between the original tree edges, have elegant properties for modeling evolutionary histories. We answer an open question of Francis, Semple, and Steel about the complexity of determining how far a phylogenetic network is from being tree-based, including non-binary phylogenetic networks. We show that finding a phylogenetic tree covering the maximum number of nodes in a phylogenetic network can be be computed in polynomial time via an encoding into a minimum-cost maximum flow problem.
