article

Efficient Algorithms to Explore Conformation Spaces of Flexible Protein Loops

Authors:

Henry van den Bedem,

Jean-Claude Latombe,

Inbal Halperin-Landsberg,

Russ B. AltmanAuthors Info & Claims

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), Volume 5, Issue 4

Pages 534 - 545

https://doi.org/10.1109/TCBB.2008.96

Published: 01 October 2008 Publication History

Publisher Site Get Access

Abstract

Several applications in biology - e.g., incorporation of protein flexibility in ligand docking algorithms, interpretation of fuzzy X-ray crystallographic data, and homology modeling - require computing the internal parameters of a flexible fragment (usually, a loop) of a protein in order to connect its termini to the rest of the protein without causing any steric clash. One must often sample many such conformations in order to explore and adequately represent the conformational range of the studied loop. While sampling must be fast, it is made difficult by the fact that two conflicting constraints - kinematic closure and clash avoidance - must be satisfied concurrently. This paper describes two efficient and complementary sampling algorithms to explore the space of closed clash-free conformations of a flexible protein loop. The "seed sampling" algorithm samples broadly from this space, while the "deformation sampling" algorithm uses seed conformations as starting points to explore the conformation space around them at a finer grain. Computational results are presented for various loops ranging from 5 to 25 residues. More specific results also show that the combination of the sampling algorithms with a functional site prediction software (FEATURE) makes it possible to compute and recognize calcium-binding loop conformations. The sampling algorithms are implemented in a toolkit (LoopTK), which is available at https://simtk.org/home/looptk.

References

[1]

M. Babor, H. M. Greenblatt, M. Edelman, and V. Sobolev, "Flexibility of Metal Binding Sites in Proteins on a Database Scale," Proteins: Structure, Function, and Bioinformatics, vol. 59, pp. 221-230, 2005.

[2]

P. I. W. Bakker, M. A. DePristo, D. F. Burke, and T. L. Blundell, "Ab Initio Construction of Polypeptide Fragments: Accuracy of Loop Decoy Discrimination by an All-Atom Statistical Potential and the AMBER Force Field with the Generalized Born Solvation Model," Proteins: Structure, Function, and Genetics, vol. 51, pp. 21-40, 2003.

[3]

H. R. Bosshard, "Molecular Recognition by Induced Fit: How Fit Is the Concept?" News in Physiological Sciences, vol. 16, pp. 171-173, 2001.

[4]

R. E. Bruccoleri and M. Karplus, "Conformational Sampling Using High Temperature Molecular Dynamics," Biopolymers, vol. 29, pp. 1847-1862, 1990.

[5]

A. Canutescu and R. Dunbrack Jr., "Cyclic Coordinate Descent: A Robotics Algorithm for Protein Loop Closure," Protein Science, vol. 12, pp. 963-972, 2003.

[6]

A. Canutescu, A. Shelenkov, and R. Dunbrack Jr., "A Graph Theory Algorithm for Protein Side-Chain Prediction," Protein Science, vol. 12, pp. 2001-2014, 2003.

[7]

M. S. Cates, M. B. Berry, E. L. Ho, Q. Li, J. D. Potter, and G. N. Phillips Jr., "Metal-Ion Affinity and Specificity in EF-Hand Proteins: Coordination Geometry and Domain Plasticity in Parvalbumin," Structure with Folding and Design, vol. 7, pp. 1269-1278, 1999.

[8]

K. S. Chang and O. Khatib, "Operational Space Dynamics: Efficient Algorithm for Modeling and Control of Branching Mechanisms," Proc. IEEE Int'l Conf. Robotics and Automation (ICRA '00), pp. 850-856, 2000.

[9]

J. Cortes, T. Simeon, M. Renaud-Simeon, and V. Tran, "Geometric Algorithms for the Conformational Analysis of Long Protein Loops," J. Computational Chemistry, vol. 25, pp. 956-967, 2004.

[10]

E. A. Coutsias, C. Soek, M. P. Jacobson, and K. A. Dill, "A Kinematic View of Loop Closure," J. Computational Chemistry, vol. 25, pp. 510-528, 2004.

[11]

C. M. Deane and T. L. Blundell, "A Novel Exhaustive Search Algorithm for Predicting the Conformation of Polypeptide Segments in Proteins," Proteins: Structure, Function, and Genetics, vol. 40, pp. 135-144, 2000.

[12]

M. A. DePristo, P. I. W. de Bakker, S. C. Lovell, and T. L. Blundell, "Ab Initio Construction of Polypeptide Fragments: Efficient Generation of Accurate, Representative Ensembles," Proteins: Structure, Function, and Genetics, vol. 51, pp. 41-55, 2003.

[13]

A. Fiser, R. K. G. Do, and A. Sali, "Modeling of Loops in Protein Structures," Protein Science, vol. 9, pp. 1753-1773, 2000.

[14]

N. Furnham, T. L. Blundell, M. A. DePristo, and T. C. Terwilliger, "Is One Solution Good Enough?" Nature Structure Molecular Biology, vol. 13, pp. 184-185, 2006.

[15]

D. S. Glazer, R. J. Radmer, and R. B. Altman, "Combining Molecular Dynamics and Machine Learning to Improve Protein Function Recognition," Proc. Pacific Symp. Biocomputing (PSB '08), vol. 13, pp. 332-343, 2008.

[16]

G. Golub and C. van Loan, Matrix Computations, third ed. John Hopkins Univ. Press, 1996.

Digital Library

[17]

D. Halperin and M.H. Overmars, "Spheres, Molecules and Hidden Surface Removal," Computational Geometry: Theory and Applications, vol. 11, pp. 83-102, 1998.

Digital Library

[18]

M. P. Jacobson, D. L. Pincus, C. S. Rapp, T. J. F. Day, B. Honig, D. E. Shaw, and R. A. Friesner, "A Hierarchical Approach to All-Atom Protein Loop Prediction," Proteins: Structure, Function, and Bioinformatics, vol. 55, pp. 351-367, 2004.

[19]

J. Jia, N. Borregaard, K. Lollike, and M. Cygler, "Structure of Ca²⁺-Loaded Human Grancalcin," Acta Crystallographica, vol. D57, pp. 1843-1849, 2001.

[20]

H. Kawasaki and R.H. Kretsinger, "Calcium-Binding Proteins 1: EF-Hands," Protein Profile, vol. 2, pp. 305-490, 1995.

[21]

R. Kolodny, L. Guibas, M. Levitt, and P. Koehl, "Inverse Kinematics in Biology: The Protein Loop Closure Problem," Int'l J. Robotics Research, vol. 24, pp. 151-163, 2005.

[22]

E. Levin, D. Kondrashov, and G. Wesenberg, "Ensemble Refinement of Protein Crystal Structures: Validation and Application," Structure, vol. 15, pp. 1040-1052, 2007.

[23]

K. Okazaki, N. Koga, S. Takada, J. N. Onuchic, and P. G. Wolynes, "Multiple-Basin Energy Landscapes for Large-Amplitude Conformational Motions of Proteins: Structure-Based Molecular Dynamics Simulations," Proc. Nat'l Academy of Sciences USA, vol. 103, pp. 11844-11849, 2006.

[24]

J. M. Sauder and R. Dunbrack Jr., "Beyond Genomic Fold Assignment: Rational Modeling of Proteins in Biological Systems," J. Molecular Biology, vol. 8, pp. 296-306, 2000.

[25]

A. Shehu, C. Clementi, and L. E. Kavraki, "Modeling Protein Conformation Ensembles: From Missing Loops to Equilibrium Fluctuations," Proteins: Structure, Function, and Bioinformatics, vol. 65, pp. 164-179, 2006.

[26]

S. F. Sousa, P. A. Fernandes, and M. J. Ramos, "Protein-Ligand Docking: Current Status and Future Challenges," Proteins: Structure, Function, and Bioinformatics, vol. 65, pp. 15-26, 2006.

[27]

C. E. Tossato, E. Bindewald, J. Hesser, and R. Manner, "A Divide and Conquer Approach to Fast Loop Modeling," Protein Eng., vol. 15, pp. 279-286, 2002.

[28]

H. van den Bedem, I. Lotan, J. C. Latombe, and A. Deacon, "Real-Space Protein-Model Completion: An Inverse-Kinematic Approach," Acta Crystallographica, vol. D61, pp. 2-13, 2005.

[29]

H. W. T. van Vlijmen and M. Karplus, "PDB-Based Protein Loop Prediction: Parameters for Selection and Methods for Optimization," J. Molecular Biology, vol. 267, pp. 975-1001, 1997.

[30]

W. J. Wedemeyer and H. A. Scheraga, "Exact Analytical Loop Closure in Proteins Using Polynomial Equations," J. Computational Chemistry, vol. 20, pp. 819-844, 1999.

[31]

L. Wei and R. B. Altman, "Recognizing Protein Binding Sites Using Statistical Descriptions of Their 3D Environments," Proc. Pacific Symp. Biocomputing (PSB '98), pp. 497-508, 1998.

Cited By

Shehu APlaku E(2018)A survey of computational treatments of biomolecules by robotics-inspired methods modeling equilibrium structure and dynamicsJournal of Artificial Intelligence Research10.5555/3176748.317676057:1(509-572)Online publication date: 20-Dec-2018
https://dl.acm.org/doi/10.5555/3176748.3176760
Al-Bluwi ISiméon TCortés J(2018)SurveyComputer Science Review10.1016/j.cosrev.2012.07.0026:4(125-143)Online publication date: 13-Dec-2018
https://dl.acm.org/doi/10.1016/j.cosrev.2012.07.002

Index Terms

Efficient Algorithms to Explore Conformation Spaces of Flexible Protein Loops

Recommendations

Efficient algorithms to explore conformation spaces of flexible protein loops
WABI'07: Proceedings of the 7th international conference on Algorithms in Bioinformatics

Two efficient and complementary sampling algorithms are presented to explore the space of closed clash-free conformations of a flexible protein loop. The "seed sampling" algorithm samples conformations broadly distributed over this space, while the "...
Detecting protein complexes from noisy protein interaction data
BIOKDD '12: Proceedings of the 11th International Workshop on Data Mining in Bioinformatics

High-throughput experimental techniques have made available large datasets of experimentally detected protein-protein interactions. However, experimentally determined protein complexes datasets are not exhaustive nor reliable. A protein complex plays a ...
Efficient Peak-Labeling Algorithms for Whole-Sample Mass Spectrometry Proteomics

Whole-sample mass spectrometry (MS) proteomics allows for a parallel measurement of hundreds of proteins present in a variety of biospecimens. Unfortunately, the association between MS signals and these proteins is not straightforward. The need to ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Computational Biology and Bioinformatics

IEEE/ACM Transactions on Computational Biology and Bioinformatics Volume 5, Issue 4

October 2008

158 pages

ISSN:1545-5963

Issue’s Table of Contents

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 October 2008

Published in TCBB Volume 5, Issue 4

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
231
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Shehu APlaku E(2018)A survey of computational treatments of biomolecules by robotics-inspired methods modeling equilibrium structure and dynamicsJournal of Artificial Intelligence Research10.5555/3176748.317676057:1(509-572)Online publication date: 20-Dec-2018
https://dl.acm.org/doi/10.5555/3176748.3176760
Al-Bluwi ISiméon TCortés J(2018)SurveyComputer Science Review10.1016/j.cosrev.2012.07.0026:4(125-143)Online publication date: 13-Dec-2018
https://dl.acm.org/doi/10.1016/j.cosrev.2012.07.002

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents