title: A new, fast algorithm for detecting protein coevolution using maximum compatible cliques.
abstract: BACKGROUND
  The MatrixMatchMaker algorithm was recently introduced to detect the similarity between phylogenetic trees and thus the coevolution between proteins. MMM finds the largest common submatrices between pairs of phylogenetic distance matrices, and has numerous advantages over existing methods of coevolution detection. However, these advantages came at the cost of a very long execution time.
  
  
  RESULTS
  In this paper, we show that the problem of finding the maximum submatrix reduces to a multiple maximum clique subproblem on a graph of protein pairs. This allowed us to develop a new algorithm and program implementation, MMMvII, which achieved more than 600× speedup with comparable accuracy to the original MMM.
  
  
  CONCLUSIONS
  MMMvII will thus allow for more more extensive and intricate analyses of coevolution.
  
  
  BACKGROUND
  An implementation of the MMMvII algorithm is available at: http://www.uhnresearch.ca/labs/tillier/MMMWEBvII/MMMWEBvII.php.
authors.affiliation: The Edward S, Rogers Sr, Department of Electrical and Computer Engineering, University of Toronto, Toronto, Canada. arod@eecg.toronto.edu.
authors.forename: Alex
authors.initials: A
authors.lastname: Rodionov
authors.forename: Alexandr
authors.initials: A
authors.lastname: Bezginov
authors.forename: Jonathan
authors.initials: J
authors.lastname: Rose
authors.forename: Elisabeth Rm
authors.initials: ER
authors.lastname: Tillier