title: Mirroring co-evolving trees in the light of their topologies.
abstract: BACKGROUND
  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.
  
  
  RESULTS
  Our algorithm is significantly faster than those methods based on distance matrix comparison: 1 min on a single processor versus 730 h on a supercomputer. Furthermore, we outperform the current state-of-the-art exhaustive search approach in terms of precision, while incurring acceptable losses in recall.
  
  
  BACKGROUND
  A C implementation of the method demonstrated in this article is available at http://compbio.cs.sfu.ca/mirrort.htm
authors.affiliation: School of Computing Science, Simon Fraser University, Burnaby, BC, Canada. imanh@sfu.ca
authors.forename: Iman
authors.initials: I
authors.lastname: Hajirasouliha
authors.forename: Alexander
authors.initials: A
authors.lastname: Schönhuth
authors.forename: David
authors.initials: D
authors.lastname: de Juan
authors.forename: Alfonso
authors.initials: A
authors.lastname: Valencia
authors.forename: S Cenk
authors.initials: SC
authors.lastname: Sahinalp
mesh_terms: D000465:Algorithms; D000818:Animals; D006801:Humans; D010802:Phylogeny; D017434:Protein Structure, Tertiary; D011506:Proteins / Q000737:chemistry / Q000235:genetics*; D012984:Software
chemical_list: D011506:Proteins