RF+ software (version 1.0)
RF+ is a 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 RF+ software implements the algorithms described in the two manuscripts cited below and can (i) compute the RF(+) distance between two trees with arbitrary leaf sets, and (ii) compute the Extraneous-Clade-Free-RF(+) (EF-RF(+)) distance between two trees with arbitrary leaf sets. Trees can be rooted or unrooted, but must be binary.
This version of RF+ was implemented by Keegan Yao and Ashim Ranjeet under the supervision of Mukul Bansal, and is freely available open source under GNU GPL.
- GitHub repository: https://github.com/kty1/RFplus (includes Python 3 code, user manual, test data)
This software can be cited as follows:
- Optimal Completion and Comparison of Incomplete Phylogenetic Trees Under Robinson-Foulds Distance
Keegan Yao, Mukul S. Bansal
Combinatorial Pattern Matching (CPM) 2021; Leibniz International Proceedings in Informatics (LIPIcs), Vol. 191, No. 25.
- Linear-Time Algorithms for Phylogenetic Tree Completion Under Robinson-Foulds Distance
Mukul S. Bansal.
Algorithms for Molecular Biology, 15:6, 2020.
An older version of this software (version 0.2), implemented by Ashim Ranjeet, is also available below. This previous version has limited functionality. It only works for rooted trees and can only: (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.
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.