RSPR version history

From Bioinformatics Software
Revision as of 13:34, 11 July 2012 by Whidden (talk | contribs)
Jump to navigationJump to search


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