Related Experiment Videos
Global optimum protein threading with gapped alignment and empirical pair score functions
1Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge 02139, USA.
Journal of Molecular Biology
|February 2, 1996
Summary
A new branch-and-bound algorithm precisely finds the best protein sequence-structure alignment (threading). This method efficiently searches vast, complex protein structure spaces for accurate predictions.
Area of Science:
- Computational Biology
- Bioinformatics
- Structural Biology
Background:
- Protein structure prediction is crucial for understanding protein function.
- Accurate protein sequence-structure alignment (threading) is computationally challenging.
- Existing methods often rely on heuristics or simplified scoring functions.
Purpose of the Study:
- To develop an exact global optimum algorithm for protein sequence-structure alignment.
- To create a flexible search method applicable to various scoring functions and threading methodologies.
- To enable efficient exploration of large protein search spaces.
Main Methods:
- Implementation of a branch-and-bound search algorithm.
- Application of arbitrary amino acid pair score functions and sequence-specific loop/active site scoring.
- Testing on NP-hard search spaces up to 9.6 x 10^31.
Main Results:
- Achieved exact global optimum gapped sequence-structure alignments.
- Demonstrated high search rates (up to 6.8 x 10^28 equivalent threadings/sec) on large search spaces.
- Developed efficient algorithms for search space analysis (size, sampling, statistics).
Conclusions:
- The branch-and-bound algorithm provides an exact solution for protein threading.
- The method's flexibility supports diverse scoring functions and threading approaches.
- This approach is valuable for protein structure prediction and scoring function evaluation.