################################################################################
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-2013 Chris Whidden
whidden@cs.dal.ca
http://kiwi.cs.dal.ca/Software/RSPR
July 26, 2013
Version 1.2.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 <http://www.gnu.org/licenses/>.

*******************************************************************************
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 <test_trees/trees2.txt
T1: ((((1,2),(3,4)),((5,6),(7,8))),(((9,10),(11,12)),((13,14),(15,16))))
T2: (((7,8),((1,(2,(14,5))),(3,4))),(((11,(6,12)),10),((13,(15,16)),9)))

F1: (((1,2),(3,4)),(7,8)) 14 13 5 12 11 6 9 10 (15,16)
F2: ((7,8),((1,2),(3,4))) 14 5 13 12 6 11 9 (15,16) 10
approx drSPR=9

3 4
F1: ((((1,2),(3,4)),(7,8)),((10,(11,12)),(13,(15,16)))) 14 6 9 5
F2: (((7,8),((1,2),(3,4))),(((11,12),10),(13,(15,16)))) 14 6 9 5
exact drSPR=4

################################################################################

CONTACT INFORMATION

Chris Whidden
whidden@cs.dal.ca
http://kiwi.cs.dal.ca/Software/RSPR

################################################################################

FILES


ClusterForest.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
Makefile			  	Makefile
Node.h				  	Node data structure
README.txt				This README
rspr.h			    	Library to calculate rSPR distances between pairs of trees
rspr.cpp					Calculate rSPR distances between pairs or sets of trees
test_trees/				Folder of test tree pairs
SiblingPair.h      Sibling Pair class

################################################################################

INSTALLATION

rSPR is a command-line program written in C++. To use it, simply
compile rspr.cpp and execute the resulting program. On systems with
the g++ compiler and make program, the included make file will
compile rspr; simply run `make'.

################################################################################

INPUT

rSPR requires pairs of Newick format trees with arbitrary labels
as input. The first tree must be binary and rooted. The second tree
may be multifurcating and rooted. A sample Newick tree is shown below:

((1,2),(3,4),(5,6));

rSPR can also compare a rooted reference tree to an unrooted test tree.
First use gen_rooted_trees.pl to generate all rootings of the unrooted
test tree. Then use the -unrooted or -unrooted_min_approx options and
input the test tree and the set of rootings. rSPR will find the best
rooting of the test tree with the -unrooted option and guess the best 
rooting based on the approximation algorithm with the
-unrooted_min_approx option. Alternatively, the -total option with
the -unrooted or -unrooted_min_approx options will provide just the
distance. The -total option with -simple_unrooted will use a faster
biparition based measure to approximate the optimal rooting.

The -support x option can be used to collapse poorly supported branches
of the second tree.

################################################################################

OUTPUT

rspr writes to standard output.

A sample command line and output are shown below:

/////////////////////

$ ./rspr < test_trees/trees2.txt
T1: ((((1,2),(3,4)),((5,6),(7,8))),(((9,10),(11,12)),((13,14),(15,16))))
T2: ((((3,4),(8,(2,((11,12),1)))),((15,16),(7,(6,5)))),(14,((10,13),9)))

F1: ((3,4),(5,6)) 13 14 10 (11,12) 9 1 8 7 2 (15,16)
F2: ((3,4),(6,5)) 13 10 14 (11,12) 1 9 8 2 7 (15,16)
approx drSPR=12

4
F1: ((((1,2),(3,4)),((5,6),7)),((9,10),14)) 13 (11,12) 8 (15,16)
F2: ((((3,4),(2,1)),(7,(6,5))),(14,(10,9))) 13 (11,12) 8 (15,16)
exact BB drSPR=4

/////////////////////

The first set of lines show the input trees. The second set of lines are the
approximate agreement forests and the corresponding approximate rSPR distance.
The third set of lines are the maximum agreement forests and the corresponding
exact rSPR distance. When calculating exact distances, the distance
currently being considered is printed on the first line of this section.

Each component of an agreement forest corresponds to an rSPR operation. 
The set of rSPR operations required to turn one tree into the other can
be found by applying rSPR operations that move these components to their
correct place in the other tree.

An agreement forest may contain p (rho) as a component. This represents
the root of the trees and indicates that an extra rSPR operation is
required to correctly root the tree.

################################################################################

OUTPUT WITH CLUSTERING

/////////////////////

$ rspr < test_trees/cluster_test 
T1: (((x,((b1,b3),b2)),y),(f,(a,c)))
T2: (((x,y),f),((a,((b1,b2),b3)),c))

F1: (((0,((1,2),3)),4),(5,(6,7))) 
F2: (((0,4),5),((6,((1,3),2)),7)) 
approx drSPR=9


CLUSTERS
C1_1: ((1,2),3) 
C1_2: ((1,3),2) 
cluster approx drSPR=3

1 
F1_1: (1,2) 3 
F1_2: (1,2) 3 
cluster exact drSPR=1

C2_1: (((0,(1,2)),4),(5,(6,7))) 
C2_2: (((0,4),5),((6,(1,2)),7)) 
cluster approx drSPR=6

2 
F2_1: (5,(6,7)) (1,2) (0,4) 
F2_2: (5,(6,7)) (1,2) (0,4) 
cluster exact drSPR=2

F1: (f,(a,c)) b2 (b1,b3) (x,y) 
F2: (f,(a,c)) b2 (b1,b3) (x,y) 
total exact drSPR=3

/////////////////////

When clustering is enabled (as it is by default), each solved
cluster is displayed along with its approximate and exact distance in
an intermediate representation with labels mapped from 0-(N-1) where
N is the number of labels. The final agreement forest and distance
are output last.

################################################################################

EFFICIENCY

The 3-approximation algorithm runs in O(n) time, where n is the number of
leaves in the trees.

The unoptimized FPT and branch-and-bound algorithms run in O(3^k n) time, where
k is the rSPR distance and n is the number of leaves in the trees. The
branch-and-bound algorithm should be significantly faster in practice.

Using all 3 of the -cob -cab and -sc optimizations improves the running times of
the algorithms to O(2.42^k n) time. This provides a significant improvement in
practice and is provably correct, thus this is the default.

In addition, this version contains new improvements that
give a bound of O(2^k n). This provides another significant improvement
and is provably correct so these options are also enabled by default.

For much larger trees, the -split_approx option will compute an
exponential time approximation of the distance that is exact for
small distances and generally within a few percent of the optimal 
distance otherwise.

When using the -unrooted option, the exact algorithms run in O(3^k n^2) time.

The new cluster reduction implementation improves the running time of
the
algorithm to O(2.42^k n) time where k is the largest rSPR distance of
any cluster. This provides a large speedup when the trees are clusterable.

NOTE: This is an exponential algorithm that exactly solves an NP-hard problem.
Thus the algorithms may not finish in a reasonable amount of time for large
rSPR distances (> 20 without optimizations and > 70 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). 2013. Preprint available at
http://arxiv.org/abs/1305.0512

Whidden, C., Beiko, R.G., Zeh, N. Fixed-Parameter Algorithms for Maximum
Agreement Forests. SIAM Journal on Computing 42.4 (2013), pp. 1431-1466.
Available at http://epubs.siam.org/doi/abs/10.1137/110845045

Whidden, C., Zeh, N., Beiko, R.G.  Supertrees based on the subtree
prune-and-regraft distance.  (In Preparation). 2012. Preprint
available at https://peerj.com/preprints/18/

Whidden, C., Beiko, R.G., Zeh, N. Fast FPT Algorithms for Computing
Rooted Agreement Forests: Theory and Experiments. Experimental Algorithms.
Ed. by P. Festa. Vol. 6049. Lecture Notes in Computer Science. Springer
Berlin Heidelberg, 2010, pp. 141-153. Available at
http://link.springer.com/chapter/10.1007/978-3-642-13193-6_13

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.  Computing the SPR Distance of Binary
Rooted Trees in O(2^k n) Time. (In Preparation). 2013.

Whidden, C., Zeh, N., Beiko, R.G.  Fixed-Parameter and Approximation
Algorithms for Maximum Agreement Forests of Multifurcating Trees.
(In Preparation). 2013.

Whidden, C., Zeh, N., Beiko, R.G.  Supertrees based on the subtree
prune-and-regraft distance.  (In Preparation). 2013.

Whidden, C., Beiko, R.G., Zeh, N. Fixed-Parameter Algorithms for Maximum
Agreement Forests. SIAM Journal on Computing 42.4 (2013), pp. 1431-1466.
Available at http://epubs.siam.org/doi/abs/10.1137/110845045

Whidden, C., Beiko, R.G., Zeh, N. Fast FPT Algorithms for Computing
Rooted Agreement Forests: Theory and Experiments. Experimental Algorithms.
Ed. by P. Festa. Vol. 6049. Lecture Notes in Computer Science. Springer
Berlin Heidelberg, 2010, pp. 141-153. Available at
http://link.springer.com/chapter/10.1007/978-3-642-13193-6_13

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

################################################################################