In a previous post I commented that, for a broad range of trees and simulated NNIs, the minimum number of NNIs to get between two topologies seemed to be equal to (one half) the Robinson-Foulds distance. I asked readers of this blog if they were aware of any citations for this general property.
Well, it turns out that a reader responded, and RF distance does not give us (two times) the minimum number of NNIs to get between topologies - and, furthermore, computing the actual NNI distance is NP-hard. Rather, RF distance could be said to be a lower bound on the minimum number of NNIs to get between topologies. In other words, it cannot take fewer than (one half) the RF distance NNIs to get between two topologies - but it can take more. The commenter (Leonardo de Oliveira Martins from the University of Vigo, Spain) even wrote a very nice post on his own blog explaining why this is the case.
Very cool.
Thank you!
ReplyDelete