Maximum Covering Subtrees for Phylogenetic Networks
Maximum Covering Subtrees for Phylogenetic Networks
复制标题
系统发育网络的最大覆盖子树
DOI：
10.1109/tcbb.2020.3040910
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
St.John, Katherine
中科院分区：
文献类型：
--
作者：
Davidov, Nathan;Hernandez, Amanda;Mckenna, Patrick;Medlin, Karen;Jian, Justin;Mojumder, Roadra;Owen, Megan;Quijano, Andrew;Rodriguez, Amanda;St.John, Katherine
基于树的系统发育网络，可以粗略地定义为通过仅在原始树边缘之间添加弧而构建的叶标记网络，具有用于建模进化历史的优雅特性。我们回答了弗朗西斯，森普尔和钢的一个开放的问题，关于确定系统发育网络的复杂性有多远是基于树的，包括非二进制系统发育网络。我们发现，找到一个系统发育树，覆盖最大数量的节点在系统发育网络可以计算在多项式时间内通过编码成一个最小成本流问题。
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 computed in polynomial time via an encoding into a minimum-cost flow problem.
登录
查看更多内容
DOI：
10.1016/j.tcs.2013.10.015
发表时间：
2013
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
S. Linz;K. S. John;C. Semple
通讯作者：
C. Semple
在有向无环图上查找不相交路径
DOI：
10.1007/11604686_28
发表时间：
2005
期刊：
--
影响因子：
--
作者：
Torsten Tholey
通讯作者：
Torsten Tholey
DOI：
10.1145/3357713.3384247
发表时间：
2019-10
期刊：
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Yang P. Liu;Aaron Sidford
通讯作者：
Yang P. Liu;Aaron Sidford
单位容量网络中的最小成本流
影响因子：
0.5
作者：
A. Goldberg;Sagi Hed;Haim Kaplan;R. Tarjan
通讯作者：
R. Tarjan
Õ (m10/7 log W) 时间内的负权最短路径和单位容量最小成本流（扩展摘要）
DOI：
10.1137/1.9781611974782.48
发表时间：
2016
期刊：
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Michael B. Cohen;A. Madry;P. Sankowski;Adrian Vladu
通讯作者：
Adrian Vladu