Cophenetic Median Trees Under the Manhattan Distance

Computing median trees from gene trees using path-difference metrics has provided several credible species tree estimates. Similar to these metrics is the cophenetic family of metrics that originates from a dendrogram comparison metric introduced more than 50 years ago. Despite the tradition and appeal of the cophenetic metrics, the problem of computing median trees under this family of metrics has not been analyzed. Like other standard median tree problems relevant in practice, as we show here, this problem is also NP-hard. NP-hard median tree problems have been successfully addressed by local search heuristics that are solving thousands of instances of a corresponding local search problem. For the local search problem under a cophenetic metric the best known (naive) algorithm has a time complexity that is typically prohibitive for effective heuristic searches. Focusing on the Manhattan norm (Manhattan cophenetic metric), we describe an efficient algorithm for this problem that improves on the naive solution by a factor of n, where n is the size of the input trees. We demonstrate the performance of our local search algorithm in a comparative study using published empirical data sets.