## Abstract

The rooted triplet distance measures the structural dissimilarity of two phylogenetic trees or phylogenetic networks by counting the number of rooted phylogenetic trees with exactly three leaf labels (called rooted triplets, or triplets for short) 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 phylogenetic networks over a common leaf label set of size n, 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. Write 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 (nlog n) time in the special case k≤ 1. For k> 1 , no efficient algorithms are known; applying a classic method from 1980 by Fortune et al. in a direct way leads to a running time of Ω (N^{6}n^{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 vertices are allowed). In this article, we develop two new algorithms with no such restrictions. Their running times are O (N^{2}M+ n^{3}) and O (M+ Nk^{2}d^{2}+ n^{3}) , respectively. We also provide implementations of our algorithms, evaluate their performance on simulated and real datasets, and make some observations on the limitations of the current definition of the rooted triplet distance in practice. Our prototype implementations have been packaged into the first publicly available software for computing the rooted triplet distance between unrestricted networks of arbitrary levels.

Original language | English |
---|---|

Pages (from-to) | 1786-1828 |

Number of pages | 43 |

Journal | Algorithmica |

Volume | 83 |

Issue number | 6 |

DOIs | |

Publication status | Published - 2021 |

## Keywords

- Block tree
- Contracted block network
- Fan graph
- Implementation
- Phylogenetic network comparison
- Resolved graph
- Rooted triplet distance

## ASJC Scopus subject areas

- General Computer Science
- Computer Science Applications
- Applied Mathematics