Aarhus University Seal / Aarhus Universitets segl

Computing the Rooted Triplet Distance Between Phylogenetic Networks

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Jesper Jansson, Hong Kong Polytechnic University
  • ,
  • Konstantinos Mampentzidis
  • Ramesh Rajaby, National University of Singapore
  • ,
  • Wing Kin Sung, National University of Singapore, Agency for Science, Technology and Research

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 N1= (V1, E1) and N2= (V2, E2) are phylogenetic networks over a common leaf label set of size n, that Ni has level ki and maximum in-degree di for i∈ { 1 , 2 } , and that the networks’ out-degrees are unbounded. Write 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 (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 Ω (N6n3) 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 (N2M+ n3) and O (M+ Nk2d2+ n3) , 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 languageEnglish
JournalAlgorithmica
Volume83
Issue6
Pages (from-to)1786-1828
Number of pages43
ISSN0178-4617
DOIs
Publication statusPublished - Jun 2021

Bibliographical note

Publisher Copyright:
© 2021, The Author(s).

    Research areas

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

See relations at Aarhus University Citationformats

ID: 219750550