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

• Published in: IEEE/ACM transactions on computational biology and bioinformatics 2015-07, Vol.12 (4), p.729-737
• Main Authors: Koneru, Suvarna Vani, Durga Bhavani, S.
• Format: Article
• Language: English
• Subjects: Algorithms; Alignment; Approximate 2D-pattern matching; Approximation algorithms; Bioinformatics; Clustering algorithms; Clusters; Computation; Computational Biology - methods; Contact; Data Mining - methods; Databases, Protein; Dynamic programming; Heuristic; Heuristic algorithms; Matching; mining contact maps; non-crossing matching; Pattern matching; Pattern Recognition, Automated - methods; Protein Interaction Mapping - methods; Proteins; Proteins - analysis; Proteins - chemistry; Proteins - metabolism
• ISSN: 1545-5963; 1557-9964
• DOI: 10.1109/TCBB.2015.2394402

A novel approach to Contact Map Overlap (CMO) problem is proposed using the two dimensional clusters present in the contact maps. Each protein is represented as a set of the non-trivial clusters of contacts extracted from its contact map. The approach involves finding matching regions between the two contact maps using approximate 2D-pattern matching algorithm and dynamic programming technique. These matched pairs of small contact maps are submitted in parallel to a fast heuristic CMO algorithm. The approach facilitates parallelization at this level since all the pairs of contact maps can be submitted to the algorithm in parallel. Then, a merge algorithm is used in order to obtain the overall alignment. As a proof of concept, MSVNS, a heuristic CMO algorithm is used for global as well as local alignment. The divide and conquer approach is evaluated for two benchmark data sets that of Skolnick and Ding et al. It is interesting to note that along with achieving saving of time, better overlap is also obtained for certain protein folds.