Manhattan Path-Difference Median Trees

Median tree problems are a powerful tool for inferring large-scale phylogenetic trees that hold enormous promise for society at large. Such problems seek a median tree for a given collection of input trees under some problem-specific distance. Here, we introduce this problem for the classic Manhattan path-difference distance and show that this problem is NP-hard. To address this inherent time complexity we devise an ILP formulation, and an effective local search heuristic that is based on solving a local search problem exactly. Our algorithm for the local search problem improves asymptotically by a factor of n/log n on the best-known (naive) solution, where n is the size of the input trees. Finally, we demonstrate the ability of our heuristic in a comparative study using large-scale published empirical data sets, and showing its accuracy for small phylogenetic studies by using exact ILP solutions.