Computing the rooted triplet distance between phylogenetic networks

Jesper Andreas Jansson, Konstantinos Mampentzidis, Ramesh Rajaby, Wing Kin Sung

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

Abstract

The rooted triplet distance measures the structural dissimilarity of two phylogenetic trees or networks by counting the number of rooted trees with exactly three leaf labels that occur as embedded subtrees in one, but not both of them. Suppose that N1 = (V1,E1) and N2 = (V2,E2) are rooted phylogenetic networks over a common leaf label set of size λ, that Ni has level ki and maximum in-degree i ϵ {1, 2}, for n = max(|V1|, |V2|), m = max(|E1|, |E2|), k = max(k1, k2), and d = max(d1, d2). Previous work has shown how to compute the rooted triplet distance between N1 and N2 in O(λ log λ) time in the special case k ≤ 1. For k > 1, no efficient algorithms are known; a trivial approach leads to a running time of Ω(n7λ3) and the only existing non-trivial algorithm imposes restrictions on the networks’ in- and out-degrees (in particular, it does not work when non-binary nodes are allowed). In this paper, we develop two new algorithms that have no such restrictions. Their running times are O(n2m + λ3) and O(m + k3d3λ + λ3), respectively. We also provide implementations of our algorithms and evaluate their performance in practice. This is the first publicly available software for computing the rooted triplet distance between unrestricted networks of arbitrary levels.

Original languageEnglish
Title of host publicationCombinatorial Algorithms - 30th International Workshop, IWOCA 2019, Proceedings
EditorsCharles J. Colbourn, Roberto Grossi, Nadia Pisanti
PublisherSpringer-Verlag
Pages290-303
Number of pages14
ISBN (Print)9783030250041
DOIs
Publication statusPublished - 1 Jan 2019
Event30th International Workshop on Combinatorial Algorithms, IWOCA 2019 - Pisa, Italy
Duration: 23 Jul 201925 Jul 2019

Publication series

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

Conference

Conference30th International Workshop on Combinatorial Algorithms, IWOCA 2019
CountryItaly
CityPisa
Period23/07/1925/07/19

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this