Fast algorithms for computing the tripartition-based distance between phylogenetic networks
Fast algorithms for computing the tripartition-based distance between phylogenetic networks
复制标题
DOI：
10.1007/s10878-006-9025-5
复制
发表时间：
2007-04-01
影响因子：
1
通讯作者：
Sung, Wing-Kin
中科院分区：
文献类型：
--
作者：
Nguyen, Nguyen Bao;Nguyen, C. Thach;Sung, Wing-Kin
考虑两个大小为n的系统发育网络N和N'。基于三分区的距离找到不被N和N '共享的三分区的比例。该距离由Moret et al.（2004）提出，是Robinson-Foulds距离的推广，最初用于比较两个系统发育树。本文给出了一个O（min{knlogn，nlogn + hn}）时间的算法来计算这个距离，其中h是N和N'中的混合节点数，k是N和N'中所有双连通分支中的最大混合节点数.注意k
Consider two phylogenetic networks N and N' of size n. The tripartition-based distance finds the proportion of tripartitions which are not shared by N and N'. This distance is proposed by Moret et al. (2004) and is a generalization of Robinson-Foulds distance, which is orginally used to compare two phylogenetic trees. This paper gives an O(min{kn log n, n log n + hn})-time algorithm to compute this distance, where h is the number of hybrid nodes in N and N' while k is the maximum number of hybrid nodes among all biconnected components in N and N'. Note that k