‘TBRDist’ is an R package that calculates SPR, TBR and Replug distances between unrooted phylogenetic trees, using algorithms written in C++ by Chris Whidden. Whidden and Matsen (2017) provide more information on the motivation behind this project, the algorithms used and their expected performance.
The uSPR distance is a natural distance metric with respect to phylogenetic tree search, as common tree search and sampling software mainly use SPR operations (or NNI operations, a subset of SPR operations). The uSPR distance is also a lower bound on the number of lateral gene transfer events required to explain the difference between a reference/species tree and a gene tree.
Note that the uSPR distance is NP-hard to compute (as are the TBR and replug distances) and the running time of most of the algorithms used in this software scales exponentially with the distance computed. This version of TBRDist is aimed at trees with up to 50 leaves and uSPR distances up to 14.
If you are interested in comparing rooted trees in terms of SPR operations, you should use rspr instead. rspr is also much more efficient and can easily handle pairs of binary rooted trees with 200+ leaves and distances > 50. rspr is not yet incorporated in this R package; please contact the maintainer if this would be useful to you.
Installation
Install and load the library from CRAN as follows:
install.packages('TBRDist')
library('TBRDist')You can install the development version thus:
if(!require(devtools)) install.packages("devtools") devtools::install_github('ms609/TBRDist')
Advanced users wishing to access the source code should note that the project contains submodules. To download the contents of these subdirectories, clone the project using git clone --recursive https://github.com/ms609/TBRDist, or if you’ve already cloned the project, run git submodule update --init --recursive.
Usage
If you use ‘uspr’ in your research, please cite:
Chris Whidden and Frederick A. Matsen IV. Calculating the Unrooted Subtree-Prune-and-Regraft Distance. eprint arXiv:1511.07529. https://arxiv.org/abs/1511.07529
Notes
Some text in this README file originates from the ‘uspr’ readme.
Please note that the ‘TBRDist’ project is released with a Contributor Code of Conduct. By contributing to this project, you agree to abide by its terms.
