Algorithms for Reticulate Networks of Multiple Phylogenetic Trees
Algorithms for Reticulate Networks of Multiple Phylogenetic Trees
复制标题
DOI：
10.1109/tcbb.2011.137
复制
发表时间：
2012-03-01
影响因子：
4.5
通讯作者：
Wang, Lusheng
中科院分区：
文献类型：
--
作者：
Chen, Zhi-Zhong;Wang, Lusheng
由多个系统发育树组成的网状网络N可能具有具有两个或更多亲本的节点（称为网状节点）。N的网状数有两种定义方法，一种定义为N的网状节点数[13]；在这种情况下，网状数最小的网状网络称为树的最优i型网状网络。更好的方法是将其定义为N内的网状节点的父节点总数减去N内的网状节点数[18]；在这种情况下，网状数最小的网状网络称为树的最优ii型网状网络。本文首先提出了一种快速的固定参数算法，用于构造一个或所有最优的多系统发育树的i型网络。然后，我们将该算法与其他思想结合使用，得到了一种估计输入树的最优ii型网状网络的网状数下界的算法。据我们所知，这些是解决这些问题的第一个固定参数算法。我们在ANSI C语言中实现了这些算法，得到了CMPT和MaafB程序。我们的实验数据表明，CMPT可以快速构建最优的i型网状网络，MaafB可以在更短的时间内计算出比Wu[18]设计的最优方案PIRN更好的最优ii型网状网络下界。
A reticulate network N of multiple phylogenetic trees may have nodes with two or more parents (called reticulation nodes). There are two ways to define the reticulation number of N. One way is to define it as the number of reticulation nodes in N [13]; in this case, a reticulate network with the smallest reticulation number is called an optimal type-I reticulate network of the trees. The better way is to define it as the total number of parents of reticulation nodes in N minus the number of reticulation nodes in N [18]; in this case, a reticulate network with the smallest reticulation number is called an optimal type-II reticulate network of the trees. In this paper, we first present a fast fixed-parameter algorithm for constructing one or all optimal type-I reticulate networks of multiple phylogenetic trees. We then use the algorithm together with other ideas to obtain an algorithm for estimating a lower bound on the reticulation number of an optimal type-II reticulate network of the input trees. To our knowledge, these are the first fixed-parameter algorithms for the problems. We have implemented the algorithms in ANSI C, obtaining programs CMPT and MaafB. Our experimental data show that CMPT can construct optimal type-I reticulate networks rapidly and MaafB can compute better lower bounds for optimal type-II reticulate networks within shorter time than the previously best program PIRN designed by Wu [18].