Faster Computation of the Robinson-Foulds Distance between Phylogenetic Networks
Faster Computation of the Robinson-Foulds Distance between Phylogenetic Networks
复制标题
系统发育网络之间 Robinson-Foulds 距离的更快计算
DOI：
10.1016/j.ins.2012.01.038
复制
发表时间：
2012
影响因子：
8.1
通讯作者：
Gabriel Valiente
中科院分区：
文献类型：
--
作者：
Tetsuo Asano;Jesper Jansson;Kunihiko Sadakane;Ryuhei Uehara;Gabriel Valiente
Robinson-Foulds距离是一种广泛用于比较系统发育树的度量，最近已被推广到系统发育网络。给定两个系统发育网络N1和N2，每个网络具有n个叶标签和至多m个节点和e条边，Robinson-Foulds距离测量N1和N2不共享的后代叶的聚类数。计算N1和N2之间的Robinson-Foulds距离的最快算法是O（me）时间。在本文中，我们改进的时间复杂度为O（ne/logn）的一般系统发育网络和O（nm/logn）的一般系统发育网络的有界度（假设字RAM模型的字长为10 logn位），最优的O（m）时间的叶外平面网络和最优的O（n）时间的1级系统发育网络（即galled-trees）。我们还介绍了一个系统发育网络的最小蔓延的自然概念，并显示我们的新算法的运行时间取决于这个参数。作为一个例子，我们证明了一个level-k网络的最小传播最多为k+1，这意味着对于一个level-1和一个level-k系统发生网络，我们的算法运行时间为O（（k+1）e）.
The Robinson–Foulds distance, a widely used metric for comparing phylogenetic trees, has recently been generalized to phylogenetic networks. Given two phylogenetic networks N1, N2with n leaf labels and at most m nodes and e edges each, the Robinson–Foulds distance measures the number of clusters of descendant leaves not shared by N1and N2. The fastest known algorithm for computing the Robinson–Foulds distance between N1and N2runs in O(me) time. In this paper, we improve the time complexity to O(ne/logn) for general phylogenetic networks and O(nm/logn) for general phylogenetic networks with bounded degree (assuming the word RAM model with a word length of ⌈logn⌉ bits), and to optimal O(m) time for leaf-outerplanar networks as well as optimal O(n) time for level-1 phylogenetic networks (that is, galled-trees). We also introduce the natural concept of the minimum spread of a phylogenetic network and show how the running time of our new algorithm depends on this parameter. As an example, we prove that the minimum spread of a level-k network is at most k+1, which implies that for one level-1 and one level-k phylogenetic network, our algorithm runs in O((k+1)e) time.