CONSTANT TIME CLASH DETECTION IN PROTEIN FOLDING
See where this sits in the topic map →Summary AI-generated
- TL;DR
- Molecular structure manipulation tasks, such as protein docking and ab-initio protein folding, are computationally intensive and require frequent collision checks between atoms.
- Problem
- Molecular applications must frequently determine whether two atoms collide, a process known as clash detection. A naive approach calculates the distance between every pair of atoms, taking linear time relative to the number of atoms.
- Method
- We propose an efficient data structure that uses a three-dimensional array to store atom positions, reducing the time required to verify clashes with previously set atoms.
- Results
- The proposed data structure achieves constant-time verification, outperforming the logarithmic-time SAT tree and the linear-time naive approach across all protein sizes. For larger proteins, it takes about half the time of the SAT data structure and roughly one-fifth the time of the naive approach.
- Contributions
- An efficient 3D-array-based data structure for constant-time clash detection in protein folding and molecular structure manipulation.
- Limitations
- Not specified in the abstract.
- Takeaways
- This data structure improves existing molecular structure applications by significantly reducing the computational cost of clash detection, especially when manipulating large sets of atoms.
- Applications
- Can be used for any protein structure clash verification where atoms are kept in the 3D array, making it particularly useful for loop prediction, structure refinement of large proteins, and protein docking.
- Topics
- Bioinformatics, computational biology, protein folding, clash detection, data structures
- For industry
- Not specified in the abstract.
- Why it matters
- Not specified in the abstract.
Abstract
Applications for the manipulation of molecular structures are usually computationally intensive. Problems like protein docking or ab-initio protein folding need to frequently determine if two atoms in the structure collide. Therefore, an efficient algorithm for this problem, usually referred as clash detection, can greatly improve the application efficiency. This work focus mainly on the ab-initio protein folding problem. A naive approach for the clash problem, the most commonly-used by molecular structure programs, consists in calculating the distance between every pair of atoms. We propose an efficient data structure that uses a three-dimensional array to store the atoms' position. We compare the proposed data structure with one of the best known general data structures for this type of problems (SAT tree) and with the naive approach. While the naive approach takes linear time to the number of atoms to verify if a new atom clashes with any previously-set atoms, the proposed data structure takes constant time to perform the same verification. The SAT tree takes logarithmic time for the same task. The results show that the proposed data structure surpasses the other techniques for any protein size. The proposed data structure takes near half of the time of the SAT data structure and close to a fifth of the time of the naive approach for the larger proteins. We believe that this data structure can improve the existing molecular structure applications by decreasing the computational cost needed for clash detection. The data structure presented in this work can be used for any protein structure clash verification, as long as the atoms that need to be checked are kept in the 3D array. This data structure is particulary useful when manipulating large sets of atoms, for example, in applications like loop prediction, structure refinement of large proteins, and protein docking.