Mirroring co-evolving trees

Determining the interaction partners among
protein/domain families poses hard computational problems,
in particular in the presence of paralogous proteins. Available
approaches aim to identify interaction partners among
protein/domain families through maximizing the similarity between
trimmed versions of their phylogenetic trees. Since maximization
of any natural similarity score is computationally difficult, many
approaches employ heuristics to evaluate the distance matrices
corresponding to the tree topologies in question. In this article, we
devise an efficient deterministic algorithm which directly maximizes
the similarity between two leaf labeled trees with edge lengths,
obtaining a score-optimal alignment of the two trees in question.