Aarhus University Seal / Aarhus Universitets segl

Konstantinos Mampentzidis

Computing the Rooted Triplet Distance between Phylogenetic Networks

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer review

  • Jesper Jansson, Department of Computing, The Hong Kong Polytechnic University, Hong Kong
  • Konstantinos Mampentzidis
  • Ramesh Rajaby, School of Computing, National University of Singapore, Singapore
  • Wing-Kin Sung, School of Computing, National University of Singapore, Singapore
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 N_1 = (V_1,E_1) and N_2 = (V_2,E_2) are rooted phylogenetic networks over a common leaf label set of size λ, that N_i has level k_i and maximum in-degree d_i for i ∈ {1,2}, and that the networks' out-degrees are unbounded. Denote n = max(|V_1|,|V_2|), m = max(|E_1|,|E_2|), k = max(k_1,k_2), and d = max(d_1, d_2). Previous work has shown how to compute the rooted triplet distance between N_1 and N_2 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 Ω(n^7λ^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(n^2m + λ^3) and O(m + k^3d^3λ + λ^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.
OriginalsprogEngelsk
TitelComputing the Rooted Triplet Distance between Phylogenetic Networks
RedaktørerCharles J. Colbourn, Roberto Grossi, Nadia Pisanti
Antal sider14
ForlagSpringer
Udgivelsesår2019
Sider290-303
ISBN (Elektronisk)978-3-030-25005-8
StatusUdgivet - 2019
Begivenhed30th International Workshop on Combinatorial Algorithms - Computer Science department of the University of Pisa, Pisa, Italien
Varighed: 23 jul. 201925 jul. 2019
http://iwoca2019.di.unipi.it/

Konference

Konference30th International Workshop on Combinatorial Algorithms
LokationComputer Science department of the University of Pisa
LandItalien
ByPisa
Periode23/07/201925/07/2019
Internetadresse
SerietitelTheoretical Computer Science and General Issues

Se relationer på Aarhus Universitet Citationsformater

ID: 160363221