An efficient algorithm for the rooted triplet distance between galled trees

Jesper Andreas Jansson, Ramesh Rajaby, Wing Kin Sung

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)


The previous fastest algorithm for computing the rooted triplet distance between two input galled trees (i.e., phylogenetic networks whose cycles are vertex-disjoint) runs in time, where n is the cardinality of the leaf label set. In this article, we present an-Time solution. Our strategy is to transform the input so that the answer can be obtained by applying an existing-Time algorithm for the simpler case of two phylogenetic trees a constant number of times. The new algorithm has been implemented, and applying it to pairs of randomly generated galled trees with up to leaves confirms that it is fast in practice.

Original languageEnglish
Pages (from-to)893-907
Number of pages15
JournalJournal of Computational Biology
Issue number9
Publication statusPublished - Sept 2019


  • algorithm
  • computational complexity
  • galled tree
  • implementation
  • phylogenetic network comparison
  • rooted triplet

ASJC Scopus subject areas

  • Modelling and Simulation
  • Molecular Biology
  • Genetics
  • Computational Mathematics
  • Computational Theory and Mathematics


Dive into the research topics of 'An efficient algorithm for the rooted triplet distance between galled trees'. Together they form a unique fingerprint.

Cite this