A generalized Robinson-Foulds distance for labeled trees.

Détails

ID Serval
serval:BIB_2A5CE76C7989
Type
Article: article d'un périodique ou d'un magazine.
Collection
Publications
Institution
Titre
A generalized Robinson-Foulds distance for labeled trees.
Périodique
BMC genomics
Auteur(s)
Briand S., Dessimoz C., El-Mabrouk N., Lafond M., Lobinska G.
ISSN
1471-2164 (Electronic)
ISSN-L
1471-2164
Statut éditorial
Publié
Date de publication
18/11/2020
Peer-reviewed
Oui
Volume
21
Numéro
Suppl 10
Pages
779
Langue
anglais
Notes
Publication types: Journal Article
Publication Status: epublish
Résumé
The Robinson-Foulds (RF) distance is a well-established measure between phylogenetic trees. Despite a lack of biological justification, it has the advantages of being a proper metric and being computable in linear time. For phylogenetic applications involving genes, however, a crucial aspect of the trees ignored by the RF metric is the type of the branching event (e.g. speciation, duplication, transfer, etc).
We extend RF to trees with labeled internal nodes by including a node flip operation, alongside edge contractions and extensions. We explore properties of this extended RF distance in the case of a binary labeling. In particular, we show that contrary to the unlabeled case, an optimal edit path may require contracting "good" edges, i.e. edges shared between the two trees.
We provide a 2-approximation algorithm which is shown to perform well empirically. Looking ahead, computing distances between labeled trees opens up a variety of new algorithmic directions.Implementation and simulations available at https://github.com/DessimozLab/pylabeledrf .
Mots-clé
Edit distance, Labeled trees, Robinson-Foulds, Tree metric
Pubmed
Web of science
Open Access
Oui
Création de la notice
28/11/2020 11:07
Dernière modification de la notice
19/01/2021 7:26
Données d'usage