Calculating SPR distances between trees

GOLOBOFF, PABLO A.

CLADISTICS (PRINT)

Blackwell Publishing

Lugar: Londres; Año: 2007 vol. 23

0748-3007

  The SPR-distance between two trees is the minimum number of SPR moves required to convert one tree into the other.  It has been proven as an NP-complete problem.  A heuristic to calculate SPR-distances between trees is described.  It performs favorably when compared to other existing heuristics, RIATA-HGT and EEEP.  Compared to RIATA-HGT, the new method tends to produce better estimations when the trees are relatively similar, and worse estimations when the trees are very different (e.g. random trees); it produces results rather similar to those of EEEP, but orders of magnitude faster.  A measure of tree-similarity based on SPR-distances is proposed, obtained by calculating the minimum number of weighted SPR moves (with moves to closer nodes being less costly).  The resulting measure of similarity is symmetric (i.e. Dij = Dji, for any two trees i,j).