Aarhus University Seal / Aarhus Universitets segl

Computing the Rooted Triplet Distance between Phylogenetic Networks

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

Standard

Computing the Rooted Triplet Distance between Phylogenetic Networks. / Jansson, Jesper; Mampentzidis, Konstantinos; Rajaby, Ramesh; Sung, Wing-Kin.

Computing the Rooted Triplet Distance between Phylogenetic Networks. red. / Charles J. Colbourn; Roberto Grossi; Nadia Pisanti. Springer, 2019. s. 290-303 (Theoretical Computer Science and General Issues).

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

Harvard

Jansson, J, Mampentzidis, K, Rajaby, R & Sung, W-K 2019, Computing the Rooted Triplet Distance between Phylogenetic Networks. i CJ Colbourn, R Grossi & N Pisanti (red), Computing the Rooted Triplet Distance between Phylogenetic Networks. Springer, Theoretical Computer Science and General Issues, s. 290-303, 30th International Workshop on Combinatorial Algorithms, Pisa, Italien, 23/07/2019.

APA

Jansson, J., Mampentzidis, K., Rajaby, R., & Sung, W-K. (2019). Computing the Rooted Triplet Distance between Phylogenetic Networks. I C. J. Colbourn, R. Grossi, & N. Pisanti (red.), Computing the Rooted Triplet Distance between Phylogenetic Networks (s. 290-303). Springer. Theoretical Computer Science and General Issues

CBE

Jansson J, Mampentzidis K, Rajaby R, Sung W-K. 2019. Computing the Rooted Triplet Distance between Phylogenetic Networks. Colbourn CJ, Grossi R, Pisanti N, red. I Computing the Rooted Triplet Distance between Phylogenetic Networks. Springer. s. 290-303. (Theoretical Computer Science and General Issues).

MLA

Jansson, Jesper o.a.. "Computing the Rooted Triplet Distance between Phylogenetic Networks"., Colbourn, Charles J. Grossi, Roberto Pisanti, Nadia (red.). Computing the Rooted Triplet Distance between Phylogenetic Networks. Springer. (Theoretical Computer Science and General Issues). 2019, 290-303.

Vancouver

Jansson J, Mampentzidis K, Rajaby R, Sung W-K. Computing the Rooted Triplet Distance between Phylogenetic Networks. I Colbourn CJ, Grossi R, Pisanti N, red., Computing the Rooted Triplet Distance between Phylogenetic Networks. Springer. 2019. s. 290-303. (Theoretical Computer Science and General Issues).

Author

Jansson, Jesper ; Mampentzidis, Konstantinos ; Rajaby, Ramesh ; Sung, Wing-Kin. / Computing the Rooted Triplet Distance between Phylogenetic Networks. Computing the Rooted Triplet Distance between Phylogenetic Networks. red. / Charles J. Colbourn ; Roberto Grossi ; Nadia Pisanti. Springer, 2019. s. 290-303 (Theoretical Computer Science and General Issues).

Bibtex

@inproceedings{feb5322c0630454bbf111c79afb1efdb,
title = "Computing the Rooted Triplet Distance between Phylogenetic Networks",
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 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. ",
keywords = "phylogenetic network comparison, rooted triplet distance, rooted triplet",
author = "Jesper Jansson and Konstantinos Mampentzidis and Ramesh Rajaby and Wing-Kin Sung",
year = "2019",
language = "English",
series = "Theoretical Computer Science and General Issues",
publisher = "Springer",
pages = "290--303",
editor = "Colbourn, {Charles J.} and Roberto Grossi and Nadia Pisanti",
booktitle = "Computing the Rooted Triplet Distance between Phylogenetic Networks",
note = "30th International Workshop on Combinatorial Algorithms ; Conference date: 23-07-2019 Through 25-07-2019",
url = "http://iwoca2019.di.unipi.it/",

}

RIS

TY - GEN

T1 - Computing the Rooted Triplet Distance between Phylogenetic Networks

AU - Jansson, Jesper

AU - Mampentzidis, Konstantinos

AU - Rajaby, Ramesh

AU - Sung, Wing-Kin

PY - 2019

Y1 - 2019

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 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.

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 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.

KW - phylogenetic network comparison

KW - rooted triplet distance

KW - rooted triplet

M3 - Article in proceedings

T3 - Theoretical Computer Science and General Issues

SP - 290

EP - 303

BT - Computing the Rooted Triplet Distance between Phylogenetic Networks

A2 - Colbourn, Charles J.

A2 - Grossi, Roberto

A2 - Pisanti, Nadia

PB - Springer

T2 - 30th International Workshop on Combinatorial Algorithms

Y2 - 23 July 2019 through 25 July 2019

ER -