Computing the Rooted Triplet Distance Between Phylogenetic Networks

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₁= (V₁, E₁) and N₂= (V₂, E₂) 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₁| , | V₂|) , M= max (| E₁| , | E₂|) , k= max (k₁, k₂) , and d= max (d₁, d₂). Previous work has shown how to compute the rooted triplet distance between N₁ and N₂ 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⁶n³) 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²M+ n³) and O (M+ Nk²d²+ n³) , 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.