Divide and Conquer Approach to Contact Map Overlap Problem Using 2D-Pattern Mining of Protein Contact Networks

Area of Science:

• Computational Biology
• Structural Bioinformatics
• Bioinformatics

Background:

• The Contact Map Overlap (CMO) problem is crucial for protein structure alignment.
• Existing methods may face challenges in efficiency and accuracy for complex protein folds.

Purpose of the Study:

• To develop a novel, efficient, and accurate approach for solving the Contact Map Overlap (CMO) problem.
• To improve protein structure alignment by utilizing 2D clusters within contact maps.

Main Methods:

• Representing proteins as sets of non-trivial 2D clusters from their contact maps.
• Employing approximate 2D-pattern matching and dynamic programming for region identification.
• Utilizing a fast heuristic CMO algorithm (MSVNS) in parallel for matched contact map pairs.
• Implementing a merge algorithm for overall alignment and a divide and conquer strategy.

Main Results:

• The proposed method achieves significant time savings compared to traditional approaches.
• Demonstrates improved contact map overlap for specific protein folds.
• Successfully evaluated on benchmark datasets (Skolnick and Ding et al.).

Conclusions:

• The novel divide and conquer approach effectively addresses the CMO problem.
• Offers a parallelizable and efficient strategy for protein structure alignment.
• Provides enhanced accuracy in determining protein fold similarities.