A new, fast algorithm for detecting protein coevolution using maximum compatible cliques

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.MMMvII will thus allow for more more extensive and intricate analyses of coevolution.An implementation of the MMMvII algorithm is available at: http://www.uhnresearch.ca/labs/tillier/MMMWEBvII/MMMWEBvII.php webciteAn important problem in evolutionary biology is the comparison of phylogenetic trees [1]. Tree comparisons have been performed to establish the accuracy of phylogeny building methods [2-4], to determine inconsistencies between the phylogenetic history of different genes and thus determine horizontal transfer of genes between species [5,6], to find orthologous genes [4] and to identify genes that coevolve [7,8]. Some classical methods only compare tree topologies and the problem has been to identify an appropriate distance measure which describes the branch rearrangements to transform one tree into another. However most applications, which aim to find correlated rates of evolution, require the comparison measure to also consider differences in branch lengths between the trees compared.In the case of determining coevolution, where it is required that two independent genes have correlated rates of evolution, the consideration of branch lengths is critical. Proteins that interact with one another affect each others' rate of evolution such that these are more likely to evolve with correlated rates -- a process known as coevolution. Proteins that coevolve have similar evolutionary histories, in terms of both the tree topology and correlated branch lengths, and this can be leveraged to predict which proteins interact.The detection of coevolution thus requires gauging the similarity of two phylogenetic histories. A number of methods have been developed to de