LB3D: a protein three-dimensional substructure search program based on the lower bound of a root mean square...

Area of Science:

• Structural Biology
• Bioinformatics
• Computational Biology

Background:

• Determining protein function often relies on analyzing three-dimensional (3D) structural coordinates.
• Protein structure databases are expanding rapidly, necessitating efficient search methods.
• Identifying similar protein substructures is crucial for understanding protein structure-function relationships.

Purpose of the Study:

• To develop a novel and fast algorithm for searching protein 3D structures.
• To efficiently find substructures with root mean square deviations (RMSDs) below a specified threshold.
• To improve upon existing methods for large-scale protein structure comparisons.

Main Methods:

• A new algorithm for protein 3D structure substructure searching was developed.
• The algorithm achieves a runtime of O(m + N/m(0.5)) after O(N log N) preprocessing.
• Performance was evaluated against existing algorithms using a large database (>20,000,000 C-alpha coordinates).

Main Results:

• The novel algorithm demonstrates significant speed improvements over the best-known O(N) algorithm.
• Speed enhancements ranged from 1.8 to 41.6 times faster in computational experiments.
• The method effectively identifies similar protein substructures within large structural datasets.

Conclusions:

• The developed algorithm offers a substantially faster approach for protein 3D structure searching.
• This advancement aids in the rapid determination of protein structure-function relationships.
• The method is well-suited for analyzing the ever-growing protein structure databases.