Research
A new, fast algorithm for detecting protein coevolution using maximum compatible cliques
-
* Corresponding authors: Alex Rodionov arod@eecg.toronto.edu - Elisabeth RM Tillier e.tillier@utoronto.ca
1 The Edward S. Rogers Sr. Department of Electrical and Computer Engineering, University of Toronto, Toronto, Canada
2 Department of Medical Biophysics, University of Toronto, Toronto, Canada
3 Ontario Cancer Institute, University Health Network, 101 College Street., Toronto, M5G 1L7, Canada
Algorithms for Molecular Biology 2011, 6:17 doi:10.1186/1748-7188-6-17
Published: 14 June 2011Abstract
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.
Availability
An implementation of the MMMvII algorithm is available at: http://www.uhnresearch.ca/labs/tillier/MMMWEBvII/MMMWEBvII.php webcite