RF+ software (version 0.2)
RF+ is a prototype program for computing RF(+) distances between phylogenetic trees. RF(+) distance is designed to more meaningfully compute the Robinson-Foulds distance between two trees that only have a partially overlapping leaf set. The traditional approach for computing Robinson-Foulds distance between two trees that only have a partially overlapping leaf set is to first restrict the two trees to their shared leaf set and then compute their Robinson-Foulds distance. We refer to distances computed in this way as RF(-) distances. In contrast, the RF(+) distance between two arbitrary trees is computed by first optimally completing each tree on the union of the leaf sets of both trees so as to minimize the Robinson-Foulds distance between them, and then reporting the Robinson-Foulds distance between the two completed trees.
The current prototype implements the algorithms described in the manuscript cited below and can (i) compute the RF(+) distance between a pair of trees where the leaf set of one of the trees is a subset of the leaf set of the other, and (ii) compute the Extraneous-Clade-Free-RF(+) (EF-RF(+)) distance between two trees with arbitrary leaf sets. All trees must be rooted and binary.
This version of RF+ was implemented by Ashim Ranjeet under the supervision of Mukul Bansal and is freely available open source under GNU GPL.
This software can be cited as follows:
- Linear-Time Algorithms for Phylogenetic Tree Completion Under Robinson-Foulds Distance
Mukul S. Bansal.
Algorithms for Molecular Biology, 15:6, 2020.
A preliminary version of the above paper appeared in RECOMB-CG 2018 and can be cited as follows.
- Linear-Time Algorithms for some Phylogenetic Tree Completion Problems under Robinson-Foulds Distance
Mukul S. Bansal.
RECOMB Comparative Genomics Conference (RECOMB-CG) 2018; LNCS 11183: 209-226.
Funding: Development of the software resource(s) available from this webpage was funded in part by U.S. National Science Foundation awards IIS 1553421 and MCB 1616514.