################################################################################ rspr ################################################################################ Usage: rspr [OPTIONS] Calculate approximate and exact Subtree Prune and Regraft (rSPR) distances and the associated maximum agreement forests (MAFs) between pairs of rooted binary trees from STDIN in newick format. By default, computes a 3-approximation of the rSPR distance. Supports arbitrary labels. Copyright 2009-2012 Chris Whidden whidden@cs.dal.ca http://kiwi.cs.dal.ca/Software/RSPR July 10, 2012 Version 1.1.0 This file is part of rspr. rspr is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. rspr is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with rspr. If not, see . ******************************************************************************* ALGORITHM ******************************************************************************* These options control what algorithm is used -fpt Calculate the exact rSPR distance with an FPT algorithm -bb Calculate the exact rSPR distance with a branch-and-bound FPT algorithm. This is enabled by default. -approx Calculate just a linear-time 3-approximation of the rSPR distance -split_approx -split_approx x Calculate the exact rSPR distance if it is k or less and otherwise use the exponential-time approximation -cluster_test Use the cluster reduction to speed up the exact algorithm. This is enabled by default. -total Find the total SPR distance from the first input tree to the rest of the list of trees. Uses the other algorithm options as specified (including unrooted options). ******************************************************************************* OPTIMIZATIONS ******************************************************************************* These options control the use of optimized branching. All optimizations are enabled by default. Specifying any subset of -cob, -cab, and -sc will use just that subset of optimizations. -allopt Use -cob -cab -sc and a new set of improvements. This is the default option -noopt Use 3-way branching for all FPT algorithms -cob Use "cut one b" improved branching -cab Use "cut all b" improved branching -sc Use "separate components" improved branching ******************************************************************************* MULTIFURCATING COMPARISON OPTIONS ******************************************************************************* -support x Collapse bipartitions with less than x support ******************************************************************************* UNROOTED COMPARISON OPTIONS ******************************************************************************* -unrooted Compare the first input tree to each other input tree. Output the best found distance and agreement forest -unrooted_min_approx Compare the first input tree to each other input tree. Run the exact algorithms on the pair with the minimum approximate rspr distance -simple_unrooted Root the gene trees using a bipartition balanced accuracy measure (fast but potentially less accurate). Only used with -total. ******************************************************************************* OTHER OPTIONS ******************************************************************************* -cc Calculate a potentially better approximation with a quadratic time algorithm -q Quiet; Do not output the input trees or approximation ******************************************************************************* Example: $ ./rspr.exe -fpt 20 without optimizations and > 50 with optimizations). ################################################################################ REFERENCES For more information on the algorithms see: Whidden, C., Zeh, N., Beiko, R.G. Fixed-Parameter and Approximation Algorithms for Maximum Agreement Forests of Multifurcating Trees. (In Preparation). 2012. Whidden, C., Zeh, N., Beiko, R.G. Subtree Prune-and-Regraft Supertrees. (In Preparation). 2012. Whidden, C., Beiko, R.G., Zeh, N. Fast FPT Algorithms for Computing Rooted Agreement Forests: Theory and Experiments (Extended Abstract) Accepted to SEA 2010. Whidden, C., Zeh, N. A Unifying View on Approximation and FPT of Agreement Forests. In: WABI 2009. LNCS, vol. 5724, pp. 390.401. Springer-Verlag (2009). Available at http://www.springerlink.com/content/n56q2846v645p655/ Whidden, C. A Unifying View on Approximation and FPT of Agreement Forests. Masters Thesis. Dalhousie University, Canada. 2009. Available at www.cs.dal.ca/~whidden ################################################################################ CITING rSPR If you use rSPR in your research, please cite: Whidden, C., Zeh, N., Beiko, R.G. Fixed-Parameter and Approximation Algorithms for Maximum Agreement Forests of Multifurcating Trees. (In Preparation). 2012. Whidden, C., Zeh, N., Beiko, R.G. Subtree Prune-and-Regraft Supertrees. (In Preparation). 2012. Whidden, C., Beiko, R.G., Zeh, N. Fast FPT Algorithms for Computing Rooted Agreement Forests: Theory and Experiments (Extended Abstract) Accepted to SEA 2010. Whidden, C., Zeh, N. A Unifying View on Approximation and FPT of Agreement Forests. In: WABI 2009. LNCS, vol. 5724, pp. 390.401. Springer-Verlag (2009). ################################################################################