An efficient algorithm for the rooted triplet distance between galled trees

Jesper Andreas Jansson, Ramesh Rajaby, Wing Kin Sung

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

1 Citation (Scopus)

Abstract

The previously fastest algorithm for computing the rooted triplet distance between two input galled trees (i.e., phylogenetic networks whose cycles are vertex-disjoint) runs in O(n2.687) time, where n is the cardinality of the leaf label set. Here, we present an O(n log n)-time solution. Our strategy is to transform the input so that the answer can be obtained by applying an existing O(n log n)-time algorithm for the simpler case of two phylogenetic trees a constant number of times.
Original languageEnglish
Title of host publicationAlgorithms for Computational Biology - 4th International Conference, AlCoB 2017, Proceedings
PublisherSpringer Verlag
Pages115-126
Number of pages12
ISBN (Print)9783319581620
DOIs
Publication statusPublished - 1 Jan 2017
Event4th International Conference on Algorithms for Computational Biology, AlCoB 2017 - Aveiro, Portugal
Duration: 5 Jun 20176 Jun 2017

Publication series

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

Conference

Conference4th International Conference on Algorithms for Computational Biology, AlCoB 2017
Country/TerritoryPortugal
CityAveiro
Period5/06/176/06/17

Keywords

  • Algorithm
  • Computational complexity
  • Galled tree
  • Phylogenetic network comparison
  • Rooted triplet

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this