Premium
Calculating SPR distances between trees
Author(s) -
Goloboff Pablo A.
Publication year - 2008
Publication title -
cladistics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 2.323
H-Index - 92
eISSN - 1096-0031
pISSN - 0748-3007
DOI - 10.1111/j.1096-0031.2007.00189.x
Subject(s) - heuristics , similarity (geometry) , mathematics , measure (data warehouse) , heuristic , tree (set theory) , combinatorics , similarity measure , algorithm , computer science , artificial intelligence , mathematical optimization , data mining , image (mathematics)
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 with other existing heuristics, RIATA‐HGT and EEEP. Compared with 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). © The Willi Hennig Society 2007.