Article In: dblp, scopus, orcid

Computing RF Tree Distance over succinct representations

Algorithms

Branco, A.P.; Vaz, C.; Francisco, A.P. — 2024 — MDPI

Key information

Authors:

Branco, A.P.; Vaz, C.; Francisco, A.P. (A P Francisco)

Published in

January 1, 2024

Abstract

There are several tools available to infer phylogenetic trees, which depict the evolutionary relationships among biological entities such as viral and bacterial strains in infectious outbreaks or cancerous cells in tumor progression trees. These tools rely on several inference methods available to produce phylogenetic trees, with resulting trees not being unique. Thus, methods for comparing phylogenies that are capable of revealing where two phylogenetic trees agree or differ are required. An approach is then proposed to compute a similarity or dissimilarity measure between trees, with the Robinson–Foulds distance being one of the most used, and which can be computed in linear time and space. Nevertheless, given the large and increasing volume of phylogenetic data, phylogenetic trees are becoming very large with hundreds of thousands of leaves. In this context, space requirements become an issue both while computing tree distances and while storing trees. We propose then an efficient implementation of the Robinson–Foulds distance over tree succinct representations. Our implementation also generalizes the Robinson–Foulds distances to labelled phylogenetic trees, i.e., trees containing labels on all nodes, instead of only on leaves. Experimental results show that we are able to still achieve linear time while requiring less space. Our implementation in C++ is available as an open-source tool.

Publication details

Authors in the community:

Publisher

MDPI

Link to the publisher's version

https://www.mdpi.com/1999-4893/17/1/15

Title of the publication container

Algorithms

First page or article number

15

Last page

15

Volume

17

Issue

1

Fields of Science and Technology (FOS)

computer-and-information-sciences - Computer and information sciences

Keywords

  • tree dissimilarity
  • succinct data structures
  • phylogenetic trees
  • Robinson–Foulds distance

Publication language (ISO code)

eng - English

Rights type:

Open access

Financing entity

Horizon 2020 Framework Programme

Identifier for the funding entity: 951970