Faster computation of the Robinson-Foulds distance between phylogenetic networks

Tetsuo Asano, Jesper Andreas Jansson, Kunihiko Sadakane, Ryuhei Uehara, Gabriel Valiente

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

2 Citations (Scopus)

Abstract

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.
Original languageEnglish
Title of host publicationCombinatorial Pattern Matching - 21st Annual Symposium, CPM 2010, Proceedings
Pages190-201
Number of pages12
DOIs
Publication statusPublished - 1 Dec 2010
Externally publishedYes
Event21st Annual Symposium on Combinatorial Pattern Matching, CPM 2010 - New York, NY, United States
Duration: 21 Jun 201023 Jun 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6129 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st Annual Symposium on Combinatorial Pattern Matching, CPM 2010
Country/TerritoryUnited States
CityNew York, NY
Period21/06/1023/06/10

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this