Faster computation of the Robinson-Foulds distance between phylogenetic networks

详细信息	查看全文 | 推荐本文 |

• 作者：Tetsuo Asano^a ; ^{t-asano@jaist.ac.jp} ; Jesper Jansson^b ; ^{jesper.jansson@ocha.ac.jp} ; Kunihiko Sadakane^c ; ^{sada@nii.ac.jp} ; Ryuhei Uehara^a ; ^{uehara@jaist.ac.jp} ; Gabriel Valiente^d ; ^{valiente@lsi.upc.edu}
• 关键词：Algorithm ; Phylogenetic network ; Robinson&ndash ; Foulds distance ; Cluster representation ; Minimum spread ; Leaf-outerplanar phylogenetic network
• 刊名：Information Sciences
• 出版年：2012
• 期刊代码：62_00200255
• 类别：cp
• 出版时间：15 August, 2012
• 卷：197
• 期：Complete
• 页码：77-90
• 文件大小：388 K

摘要

The Robinson-Foulds distance, a widely used metric for comparing phylogenetic trees, has recently been generalized to phylogenetic networks. Given two phylogenetic networks N₁, N₂ with 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 N₁ and N₂. The fastest known algorithm for computing the Robinson-Foulds distance between N₁ and N₂ runs in O(me) time. In this paper, we improve the time complexity to O(ne/log n) for general phylogenetic networks and O(nm/log n) for general phylogenetic networks with bounded degree (assuming the word RAM model with a word length of 鈱坙ogn鈱?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.