################################################################################
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.1.1
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).
################################################################################