TY - GEN

T1 - Faster computation of the Robinson-Foulds distance between phylogenetic networks

AU - Asano, Tetsuo

AU - Jansson, Jesper Andreas

AU - Sadakane, Kunihiko

AU - Uehara, Ryuhei

AU - Valiente, Gabriel

PY - 2010/12/1

Y1 - 2010/12/1

N2 - The Robinson-Foulds distance, which is the most widely used metric for comparing phylogenetic trees, has recently been generalized to phylogenetic networks. Given two networks N1,N2with n leaves, m nodes, and e edges, the Robinson-Foulds distance measures the number of clusters of descendant leaves that are not shared by N1 and N2. The fastest known algorithm for computing the Robinson-Foulds distance between those networks runs in O(m(m + e)) time. In this paper, we improve the time complexity to O(n(m+ e)/ log n) for general networks and O(nm/log n) for general networks with bounded degree, and to optimal O(m + e) time for planar phylogenetic networks and boundedlevel phylogenetic networks.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 phylogenetic network is at most k + 1, which implies that for two level-k phylogenetic networks, our algorithm runs in O((k + 1)(m + e)) time.

AB - The Robinson-Foulds distance, which is the most widely used metric for comparing phylogenetic trees, has recently been generalized to phylogenetic networks. Given two networks N1,N2with n leaves, m nodes, and e edges, the Robinson-Foulds distance measures the number of clusters of descendant leaves that are not shared by N1 and N2. The fastest known algorithm for computing the Robinson-Foulds distance between those networks runs in O(m(m + e)) time. In this paper, we improve the time complexity to O(n(m+ e)/ log n) for general networks and O(nm/log n) for general networks with bounded degree, and to optimal O(m + e) time for planar phylogenetic networks and boundedlevel phylogenetic networks.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 phylogenetic network is at most k + 1, which implies that for two level-k phylogenetic networks, our algorithm runs in O((k + 1)(m + e)) time.

UR - http://www.scopus.com/inward/record.url?scp=79956315151&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-13509-5_18

DO - 10.1007/978-3-642-13509-5_18

M3 - Conference article published in proceeding or book

SN - 3642135080

SN - 9783642135088

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 190

EP - 201

BT - Combinatorial Pattern Matching - 21st Annual Symposium, CPM 2010, Proceedings

T2 - 21st Annual Symposium on Combinatorial Pattern Matching, CPM 2010

Y2 - 21 June 2010 through 23 June 2010

ER -