# Difference between revisions of "RSPR version history"

From Bioinformatics Software

Line 1: | Line 1: | ||

__NOTOC__ | __NOTOC__ | ||

+ | |||

+ | ==1.1.0== | ||

+ | |||

+ | * Significant speed improvements that we believe improve the complexity to O(2^k n). | ||

+ | * The second tree can now be multifurcating. | ||

+ | * Added -simple_unrooted option that can be used with -total to quickly compute a good rooting of the second tree based on a bipartition balanced accuracy measure. | ||

==1.03== | ==1.03== |

## Revision as of 13:34, 11 July 2012

## 1.1.0

- Significant speed improvements that we believe improve the complexity to O(2^k n).
- The second tree can now be multifurcating.
- Added -simple_unrooted option that can be used with -total to quickly compute a good rooting of the second tree based on a bipartition balanced accuracy measure.

## 1.03

- Bugfix release
- The approximate distance is now output when the cluster reduction is enabled.
- The correct approximate distance is output.
- The -fpt option (without the -cluster_test cluster reduction option) now correctly outputs "exact drSPR=X" instead of "exact BB drSPR=x".

## 1.02

- Includes a cluster reduction step that greatly improves performance in many cases.
- Provides an option to find the total rooted SPR distance between the first input tree and each of the remaining input trees.
- Stand-alone version of the calculations used in
*"Subtree Prune-and-Regraft Supertrees."*

## 1.01

- Optimized branching cases, improving the complexity to O(2.42^k n), where k is the rooted SPR distance and n is the number of leaves.
- Version used in
*"Fast FPT Algorithms for Computing Rooted Agreement Forests: Theory and Experiments."*

## 1.00

- initial program version.
- Computes a 3-approximation of the rooted SPR distance between each pair of input trees.
- Computes the exact rooted SPR distance with complexity O(3^k n), where k is the rooted SPR distance and n is the number of leaves.
- Option to compute the smallest rooted SPR distance between the first input tree and each of the remaining input trees, to approximate the unrooted SPR distance.
- Version used in
*"A Unifying View on Approximation and FPT of Agreement Forests."*