TY - GEN
T1 - Computing the rooted triplet distance between phylogenetic networks
AU - Jansson, Jesper Andreas
AU - Mampentzidis, Konstantinos
AU - Rajaby, Ramesh
AU - Sung, Wing Kin
PY - 2019/1/1
Y1 - 2019/1/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85069690271&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-25005-8_24
DO - 10.1007/978-3-030-25005-8_24
M3 - Conference article published in proceeding or book
AN - SCOPUS:85069690271
SN - 9783030250041
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 290
EP - 303
BT - Combinatorial Algorithms - 30th International Workshop, IWOCA 2019, Proceedings
A2 - Colbourn, Charles J.
A2 - Grossi, Roberto
A2 - Pisanti, Nadia
PB - Springer-Verlag
T2 - 30th International Workshop on Combinatorial Algorithms, IWOCA 2019
Y2 - 23 July 2019 through 25 July 2019
ER -