################################################################################ spr_supertree ################################################################################ Usage: spr_supertree [OPTIONS] spr_supertree-omp [OPTIONS] Calculate supertrees that minimize the SPR distance from the input trees. By default calculates a rooted SPR supertree from a list of rooted binary trees from STDIN in newick format. An initial tree is built by greedily adding taxa in decreasing order of ocurrence. The tree is then improved by SPR rearrangements. Additional options allow for unrooted and/or multifurcating input trees. Copyright 2013 Chris Whidden whidden@cs.dal.ca http://kiwi.cs.dal.ca/Software/SPR_Supertrees April 26, 2013 Version 1.2.0 This file is part of spr_supertrees. spr_supertrees 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. spr_supertrees 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 spr_supertrees. If not, see . ******************************************************************************* ALGORITHM ******************************************************************************* These options control what algorithm is used to determine the SPR distance from the supertree to the input trees. By default -bb 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 the default option. -approx Calculate just a linear -time 3-approximation of the rSPR distance -max k Calculate the exact rSPR distance if it is k or less and otherwise use the 3-approximation -split_approx -split_approx x Calculate the exact rSPR distance if it is k or less and otherwise use the exponential-time approximation ******************************************************************************* 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. See the README for more information. -allopt Use -cob -cab -sc and a new set of optimizations. 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 -bipartition_cluster x Do not consider supertree rearrangements that violate biparitions supported by x% of gene trees containing at least two members from each side of the bipartition. Enabled by default with x=0.5 ******************************************************************************* MULTIFURCATING COMPARISON OPTIONS ******************************************************************************* -allow_multi Allow multifurcating gene trees -support x Collapse bipartitions with less than x support ******************************************************************************* UNROOTED COMPARISON OPTIONS ******************************************************************************* -unrooted Compare the supertree to each rooting of the input trees. Use the best found distance -unrooted_min_approx Compare the supertree to each rooting of the input trees. Run the exact algorithm on the rooting with the minimum approximate rspr distance -simple_unrooted Root the gene trees at each iteration using a bipartition balanced accuracy measure (fast but potentially less accurate) Reports an unrooted SPR distance comparison at the end of each iteration for comparable iteration scores -simple_unrooted x Root the gene trees at the first x iterations -simple_unrooted_fast The same as -simple_unrooted but does not use an unrooted comparison at the end of each iteration -outgroup FILE Root the gene trees with the outgroup taxa listed in FILE, one per line. Trees with a polyphyletic outgroup are considered invalid. -reroot Reroot the super tree at each iteration using a bipartition balanced accuracy measure -rspr_reroot Root trees using the SPR distance instead of the bipartition balanced accuracy ******************************************************************************* SEARCH STRATEGY OPTIONS ******************************************************************************* -i x Run for x iterations of the global rearrangement search -r x Only consider transfers of length x in the global rearrangement search. Default is infinite (All SPRs). For NNI search use -r 1 -include_only Build the supertree only from taxa included in , one per line -initial_tree Begin the search with the tree in -num_leaves x Build the supertree from the x taxa that are found in the largest number of trees -random_insert_order Insert taxa in random order when building the greedy addition tree. The default order is descending occurence -rf_ties Break SPR distance ties with the RF distance ******************************************************************************* LGT ANALYSIS ******************************************************************************* -lgt_analysis Conduct an LGT analysis with the initial user-specified or greedy addition tree -lgt_csv Output the LGT analysis seperated by commas rather than spaces. -lgt_groups FILE Specify a set of groups (e.g. genus or class) to analyze with -lgt_analysis. The group FILE contains a set of groups consisting of a group name on one line, group members one per line, and a blank line to seperate each group. ******************************************************************************* OTHER OPTIONS ******************************************************************************* -time Print iteration and total CPU time used at each iteration -cc Calculate a potentially better approximation with a quadratic time algorithm -valid_trees Output the set of trees that appear valid -valid_trees_rooted Output the set of trees that appear valid after applying any rooting options. -multi_trees Output the set of multifurcating or invalid trees ################################################################################ CONTACT INFORMATION Chris Whidden whidden@cs.dal.ca http://kiwi.cs.dal.ca/Software/SPR_Supertrees ################################################################################ FILES ClusterForest.h Cluster Decomposition ClusterInstance.h Cluster Decomposition Forest.h Forest data structure gen_rooted_trees.pl Generate all rootings of an unrooted binary tree gpl.txt The GPL license LCA.h Compute LCAs of tree leaves lgt.h LGT Analysis Makefile Makefile Node.h Node data structure README.txt This README rspr.h Calculate rSPR distances between pairs of trees SiblingPair.h Sibling pair data structure spr_supertree.cpp Main file spr_supertree Compute supertrees that minimize spr distance UndoMachine.h Structure to record and undo tree alterations ################################################################################ INSTALLATION SPR Supertrees is a command-line program written in C++. To use it, simply compile spr_supertree.cpp and execute the resulting program. On systems with the g++ compiler and make program, the included make file will compile spr_supertree; simply run `make'. SPR Supertrees can also use multiple cores on SMP machines through OpenMP. Compile with the -fopenmp flag or run `make omp'. The multicore executable will be called spr_supertree-omp ################################################################################ INPUT SPR Supertrees requires a list of Newick format trees with arbitrary labels as input. A sample Newick tree is shown below: ((1,2),(3,4),(5,6)); By default the trees must be rooted and binary. If you wish to allow multifurcating input trees use the -allow_multi option. Bipartitions with less than x% support can be collapsed with -support x. SPR Supertrees can also construct a rooted tree from unrooted gene trees. Use the -unrooted, -unrooted_min_approx, -simple_unrooted, or -simple_unrooted_fast options rSPR will find the best rooting of each input tree with respect to the current supertree using the -unrooted option, guess the best rooting based on the approximation algorithm with the -unrooted_min_approx option, and guess the best rooting based on a bipartition balanced accuracy measure with the -simple_unrooted or -simple_unrooted_fast options. These are much faster but may be less accurate. The -outgroup option roots gene trees based on a list of outgroup taxa. This option ignores gene trees with a polyphyletic outgroup or no outgroup members. To root these trees, one can construct a supertree from just the trees where the outgroup is monophyletic and then root the remainder of the trees with the -simple_unrooted 1 option. With the -lgt_analysis option, the program conducts an LGT analysis of an initial or greedy addition supertree. The gene trees should be rooted, either as input or using -simple_unrooted_fast. This analysis considers a single minimal reconciliation scenario between the supertree and each gene tree. The output is a series of matrices (comma-seperated with the -lgt_csv option) showing the number of inferred SPR moves, transfers, and transfers ignoring direction between groups of taxa or to "mixed" portions of the tree. The -lgt_groups option is required and specifys taxonomic groups or individual taxa. ################################################################################ OUTPUT rspr writes to standard output. A sample command line and output are shown below: ///////////////////// \$ ./spr_supertree -i 1 < test_trees/trees2.txt NUM_ITERATIONS=1 skipped 0 lines with no opening bracket skipped 0 multifurcating or invalid trees skipped 0 trees with less than 4 leaves 2 gene trees remaining Initial Supertree: ((15,14),(13,12)) Adding leaf 11 (5/16) (((16,15),(14,13)),12) Adding leaf 10 (6/16) (((16,15),(14,13)),(12,11)) Adding leaf 9 (7/16) (((16,15),(14,13)),((12,11),10)) Adding leaf 8 (8/16) ((((16,15),(14,13)),9),((12,11),10)) Adding leaf 7 (9/16) (((((16,15),(14,13)),9),((12,11),10)),8) Adding leaf 6 (10/16) (((((16,15),(14,13)),9),((12,11),10)),(8,7)) Adding leaf 5 (11/16) (((((16,15),(14,13)),9),((12,11),10)),((8,7),6)) Adding leaf 4 (12/16) (((((16,15),(14,13)),9),((12,11),10)),((8,7),(6,5))) Adding leaf 3 (13/16) (((((16,15),(14,13)),9),((12,11),10)),((8,7),((6,4),5))) Adding leaf 2 (14/16) (((((16,15),(14,13)),9),((12,11),10)),((8,7),((6,(4,3)),5))) Adding leaf 1 (15/16) (((((16,15),(14,13)),9),((12,11),10)),((8,7),((6,(4,3)),(5,2)))) Adding leaf 0 (16/16) (((((16,15),(14,13)),9),((12,11),10)),((8,7),((6,(4,3)),((5,2),1)))) Initial Supertree: (((((16,15),(14,13)),9),((12,11),10)),((8,7),((6,(4,3)),((5,2),1)))) Total Distance: 5 Current Supertree: (((((16,15),(14,13)),9),((12,11),10)),((6,(8,7)),((4,3),((5,2),1)))) Total Distance: 4 Final Supertree: (((((16,15),(14,13)),9),((12,11),10)),((6,(8,7)),((4,3),((5,2),1)))) Final Distance: 4 ///////////////////// The first set of lines indicate the options chosen, the number of invalid trees and the number of valid trees. The program then builds a supertree greedily by placing the most frequent taxa first. Finally, the program applies 25 iterations of global SPR rearrangements (or a user-specified number using the -i option as shown here ) and outputs the best tree and distance found at the end of each iteration. To build larger trees the -r x option will limit the SPR rearrangements to transfers of length at most x. For example, -r 1 uses only NNI rearrangements. ################################################################################ EFFICIENCY The 3-approximation algorithm runs in O(n) time, where n is the number of leaves in the trees. the exact algorithms run in O(2.42^k n) time, where \$k\$ is the computed SPR distance. Using a set of new optimizations we conjecture that the running time has been improved to O(2^k n) time. When using the -unrooted option, the exact algorithms run in O(2.42^k n^2) time. (conjectured O(2^k n^2)). The -simple_unrooted option has the same worst case performance as the regular exact algorithms. When using the -max x option, the exact algorithms will run up to a distance of x and then the approximation is used. This provides a running time of O(n + 2^x n) or O(n + 2^x n^2) for rooted trees and allows for a trade-off between space and efficiency. The -split_approx x option works similarly but is both much more accurate and slower. -split_approx is recommended over -max. Since there are O(n^2) possible SPR rearrangements, the total running time is O(i * n^2 * X), where i is the number of iterations and X is the running time of the chosen SPR computation method. NOTE: The exact algorithms are exponential algorithms that exactly solve an NP-hard problem. Thus the algorithms may not finish in a reasonable amount of time for very large rSPR distances without the -split_approx or -max options. For very large supertrees, it may also be necessary to limit the scope of the search with the -r option. The -bipartition_cluster x option ignores SPR rearrangments that violate any bipartition that agrees with x% of the gene trees that contain at least two taxa from each side of the bipartition. This is enabled by default with x=0.5 and grealy accelerates tree searches at the expense of some searching power. This option can be disabled with -bipartition_cluster 1, requiring total agreement. ################################################################################ REFERENCES For more information on the algorithms see: Whidden, C., Zeh, N., Beiko, R. G. Subtree Prune-and-Regraft Supertrees. (In preparation) Whidden, C., Beiko, R. G., Zeh, N. 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 SPR Supertrees If you use SPR Supertrees in your research, please cite: Whidden, C., Zeh, N., Beiko R. G. Subtree Prune-and-Regraft Supertrees. (In Preparation). ################################################################################