Tetsuo Asano,
Jesper Jansson,
Kunihiko Sadakane,
Ryuhei Uehara and
Gabriel Valiente. Faster Computation of the RobinsonFoulds Distance between Phylogenetic Networks. In CPM10, Vol. 6129:190201 of LNCS, springer, 2010. Keywords: distance between networks, explicit network, level k phylogenetic network, phylogenetic network, polynomial, spread. Note: http://hdl.handle.net/10119/9859, slides available at http://cs.nyu.edu/parida/CPM2010/MainPage_files/18.pdf.
Toggle abstract
"The RobinsonFoulds distance, which is the most widely used metric for comparing phylogenetic trees, has recently been generalized to phylogenetic networks. Given two networks N1,N2 with n leaves, m nodes, and e edges, the RobinsonFoulds distance measures the number of clusters of descendant leaves that are not shared by N1 and N2. The fastest known algorithm for computing the RobinsonFoulds 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 levelk phylogenetic network is at most k + 1, which implies that for two levelk phylogenetic networks, our algorithm runs in O((k + 1)(m + e)) time. © SpringerVerlag Berlin Heidelberg 2010."
