Journal
ALGORITHMS FOR MOLECULAR BIOLOGY
Volume 6, Issue -, Pages -Publisher
BMC
DOI: 10.1186/1748-7188-6-17
Keywords
-
Categories
Funding
- Ontario Ministry of Health and Long Term Care
Ask authors/readers for more resources
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 600x speedup with comparable accuracy to the original MMM. Conclusions: MMMvII will thus allow for more more extensive and intricate analyses of coevolution.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available