Tuyển tập các báo cáo nghiên cứu về sinh học được đăng trên tạp chí y học Molecular Biology cung cấp cho các bạn kiến thức về ngành sinh học đề tài: A new, fast algorithm for detecting protein coevolution using maximum compatible cliques. | Rodionov et al. Algorithms for Molecular Biology 2011 6 17 http content 6 1 17 AMR ALGORITHMS FOR MOLECULAR BIOLOGY RESEARCH Open Access A new fast algorithm for detecting protein coevolution using maximum compatible cliques Alex Rodionov1 Alexandr Bezginov2 Jonathan Rose1 and Elisabeth RM Tillier2 3 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 MMMvIl which achieved more than 600x speedup with comparable accuracy to the original MMM. Conclusions MMMvIl will thus allow for more more extensive and intricate analyses of coevolution. Availability An implementation of the MMMvIl algorithm is available at http labs tillier MMMWEBvII Background An 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
