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

Abstract

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
Volume26
Issue number9
DOIs
Publication statusPublished - Sep 2019

Keywords

  • 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

Cite this