Fiche du document
18 novembre 2020
- doi: 10.1186/s12864-020-07011-0
- issn: 1471-2164
Ce document est lié à :
info:eu-repo/semantics/altIdentifier/doi/10.1186/s12864-020-07011-0
Ce document est lié à :
info:eu-repo/semantics/altIdentifier/pmid/33208096
Ce document est lié à :
info:eu-repo/semantics/altIdentifier/eissn/1471-2164
Ce document est lié à :
info:eu-repo/semantics/altIdentifier/urn/urn:nbn:ch:serval-BIB_2A5CE76C79897
info:eu-repo/semantics/openAccess , CC BY 4.0 , https://creativecommons.org/licenses/by/4.0/
Sujets proches
DendrologyCiter ce document
S. Briand et al., « A generalized Robinson-Foulds distance for labeled trees. », Serveur académique Lausannois, ID : 10.1186/s12864-020-07011-0
Métriques
Partage / Export
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 .