Gunawan Andreas D M, Lu Bingxin, Zhang Louxin
Department of Mathematics.
Department of Computer Science, National University of Singapore, Singapore 117417, Singapore.
Bioinformatics. 2016 Sep 1;32(17):i503-i510. doi: 10.1093/bioinformatics/btw467.
Genetic material is transferred in a non-reproductive manner across species more frequently than commonly thought, particularly in the bacteria kingdom. On one hand, extant genomes are thus more properly considered as a fusion product of both reproductive and non-reproductive genetic transfers. This has motivated researchers to adopt phylogenetic networks to study genome evolution. On the other hand, a gene's evolution is usually tree-like and has been studied for over half a century. Accordingly, the relationships between phylogenetic trees and networks are the basis for the reconstruction and verification of phylogenetic networks. One important problem in verifying a network model is determining whether or not certain existing phylogenetic trees are displayed in a phylogenetic network. This problem is formally called the tree containment problem. It is NP-complete even for binary phylogenetic networks.
We design an exponential time but efficient method for determining whether or not a phylogenetic tree is displayed in an arbitrary phylogenetic network. It is developed on the basis of the so-called reticulation-visible property of phylogenetic networks.
A C-program is available for download on http://www.math.nus.edu.sg/∼matzlx/tcp_package
Supplementary data are available at Bioinformatics online.
遗传物质以非生殖方式在物种间转移的频率比通常认为的更高，尤其是在细菌界。一方面，现存基因组因此更应被视为生殖性和非生殖性基因转移的融合产物。这促使研究人员采用系统发育网络来研究基因组进化。另一方面，一个基因的进化通常呈树状，并且已经被研究了半个多世纪。因此，系统发育树和网络之间的关系是系统发育网络重建和验证的基础。验证网络模型中的一个重要问题是确定某些现有的系统发育树是否能在系统发育网络中展示出来。这个问题被正式称为树包含问题。即使对于二元系统发育网络，它也是NP完全问题。
我们设计了一种指数时间但高效的方法来确定一棵系统发育树是否能在任意系统发育网络中展示出来。它是基于系统发育网络的所谓网状可见属性开发的。
可在http://www.math.nus.edu.sg/∼matzlx/tcp_package下载一个C程序。
补充数据可在《生物信息学》在线获取。
