Related Experiment Video

Updated: Jun 1, 2026

JUMPn: A Streamlined Application for Protein Co-Expression Clustering and Network Analysis in Proteomics
07:28

JUMPn: A Streamlined Application for Protein Co-Expression Clustering and Network Analysis in Proteomics

Published on: October 19, 2021

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

Alex Rodionov1, Alexandr Bezginov, Jonathan Rose

  • 1The Edward S, Rogers Sr, Department of Electrical and Computer Engineering, University of Toronto, Toronto, Canada. arod@eecg.toronto.edu.

Algorithms for Molecular Biology : AMB
|June 16, 2011
PubMed
Abstract

Insights

The MatrixMatchMaker algorithm (MMM) detects protein coevolution by analyzing phylogenetic trees. A new version, MMMvII, significantly speeds up this process, enabling more detailed coevolutionary analyses.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Evolutionary Biology

Background:

  • The MatrixMatchMaker (MMM) algorithm was developed to detect similarities between phylogenetic trees and infer protein coevolution.
  • MMM identifies common submatrices within phylogenetic distance matrices, offering advantages over prior coevolution detection methods.
  • The original MMM algorithm suffered from excessively long execution times, limiting its practical application.

Purpose of the Study:

  • To address the computational limitations of the original MatrixMatchMaker algorithm.
  • To develop a faster and more efficient method for detecting protein coevolution.
  • To enable more extensive and intricate coevolutionary analyses.

Main Methods:

  • The study reframes the maximum submatrix problem as a multiple maximum clique subproblem on a protein pair graph.
  • A novel algorithm and program implementation, MMMvII, was developed based on this new approach.
  • The performance of MMMvII was evaluated against the original MMM algorithm.

Main Results:

  • The MMMvII algorithm achieved a speedup of over 600 times compared to the original MMM.
  • MMMvII demonstrated comparable accuracy to the original MMM in detecting coevolution.
  • The computational problem was successfully reduced to a multiple maximum clique subproblem.

Conclusions:

  • MMMvII significantly enhances the efficiency of coevolution detection.
  • The improved speed allows for more comprehensive and complex analyses of protein coevolution.
  • MMMvII facilitates deeper insights into evolutionary relationships and protein function.

More Related Videos

Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues07:08

Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues

Published on: July 14, 2015

Genome-wide Protein-protein Interaction Screening by Protein-fragment Complementation Assay (PCA) in Living Cells08:38

Genome-wide Protein-protein Interaction Screening by Protein-fragment Complementation Assay (PCA) in Living Cells

Published on: March 3, 2015

Related Concept Videos

Protein Complexes with Interchangeable Parts01:57

Protein Complexes with Interchangeable Parts

Groups of proteins may form a complex where each protein in this complex has a different role in the overall execution of the complex’s function. Often some of the proteins in the complex can be replaced by a closely related variant to give a complex that contains many of the same components yet is functionally distinct.
The SCF ubiquitin ligase is a protein complex of five individual proteins. This complex attaches ubiquitin to other target proteins to mark them for degradation. In order to...
Protein Complexes with Interchangeable Parts01:57

Protein Complexes with Interchangeable Parts

Groups of proteins may form a complex where each protein in this complex has a different role in the overall execution of the complex’s function. Often some of the proteins in the complex can be replaced by a closely related variant to give a complex that contains many of the same components yet is functionally distinct.
The SCF ubiquitin ligase is a protein complex of five individual proteins. This complex attaches ubiquitin to other target proteins to mark them for degradation. In order to...
Conservation of Protein Domains Over Different Proteins02:26

Conservation of Protein Domains Over Different Proteins

Protein domains are small structurally independent units that are part of a single amino acid chain.  Although these domains are often structurally independent, they may rely on synergistic effects to perform their functions as part of a larger protein. Protein domains may be conserved within the same organism, as well as across different organisms.
A limited set of protein domains often duplicate and recombine during evolution. These domains can be organized in different combinations to form...
Conservation of Protein Domains02:26

Conservation of Protein Domains

Protein domains are small structurally independent units that are part of a single amino acid chain.  Although these domains are often structurally independent, they may rely on synergistic effects to perform their functions as part of a larger protein. Protein domains may be conserved within the same organism, as well as across different organisms.
A limited set of protein domains often duplicate and recombine during evolution. These domains can be organized in different combinations to form...
Protein Networks02:26

Protein Networks

An organism can have thousands of different proteins, and these proteins must cooperate to ensure the health of an organism. Proteins bind to other proteins and form complexes to carry out their functions. Many proteins interact with multiple other proteins creating a complex network of protein interactions.
These interactions can be represented through maps depicting protein-protein interaction networks, represented as nodes and edges. Nodes are circles that are representative of a protein,...
Protein Networks02:26

Protein Networks

An organism can have thousands of different proteins, and these proteins must cooperate to ensure the health of an organism. Proteins bind to other proteins and form complexes to carry out their functions. Many proteins interact with multiple other proteins creating a complex network of protein interactions.
These interactions can be represented through maps depicting protein-protein interaction networks, represented as nodes and edges. Nodes are circles that are representative of a protein,...