Accelerating screening of 3D protein data with a graph theoretical approach

Area of Science:

• Structural Biology
• Bioinformatics
• Computational Biology

Background:

• The Dictionary of Interfaces in Proteins (DIP) database stores 3D structures of protein interacting surfaces (patches).
• Current methods for finding similar patches in DIP are computationally intensive, requiring hours for a full scan.
• Efficiently identifying similar protein patches is crucial for understanding protein interactions.

Purpose of the Study:

• To develop a method for rapidly identifying protein patches similar to a query patch within the DIP database.
• To investigate the distribution of patch similarity scores to optimize search strategies.
• To reduce the computational time required for similarity searches in large protein structure databases.

Main Methods:

• Analyzed the distribution of similarity scores between protein patches in the DIP database.
• Identified key score ranges corresponding to different levels of spatial similarity.
• Applied concepts from random graph theory to understand the structural properties of the DIP data.

Main Results:

• Patch similarity scores naturally fall into three distinct ranges, indicating different levels of spatial congruence.
• Two distinct approaches were found to define the boundaries between these similarity classes.
• Searches for highly similar patches were accelerated over 25-fold; medium similarity searches were 10-fold faster than brute-force.

Conclusions:

• The structural properties of protein interfaces in DIP, revealed by random graph theory, enable efficient similarity searching.
• The developed method significantly accelerates the discovery of similar protein patches, reducing computational burden.
• This approach enhances the utility of the DIP database for structural bioinformatics research.