Article

Using motion planning to map protein folding landscapes and analyze folding kinetics of known native structures

Authors:

Nancy M. Amato,

Guang SongAuthors Info & Claims

RECOMB '02: Proceedings of the sixth annual international conference on Computational biology

Pages 2 - 11

https://doi.org/10.1145/565196.565198

Published: 18 April 2002 Publication History

Abstract

We present a novel approach for studying the kinetics of protein folding. The framework has evolved from robotics motion planning techniques called probabilistic roadmap methods (prms) that have been applied in many diverse fields with great success. In our previous work, we used a Prm-based technique to study protein folding pathways of several small proteins and obtained encouraging results. In this paper, we describe how our motion planning framework can be used to study protein folding kinetics. In particular, we present a refined version of our Prm-based framework and describe how it can be used to produce potential energy landscapes, free energy landscapes, and many folding pathways all from a single roadmap which is computed in a few hours on a desktop PC. Results are presented for 14 proteins. Our ability to produce large sets of unrelated folding pathways may potentially provide crucial insight into some aspects of folding kinetics, such as proteins that exhibit both two-state and three-state kinetics, that are not captured by other theoretical techniques.

References

[1]

E. Alm and D. Baker. Matching theory and experiment in protein folding. Curr. Op. Str. Biol., 9:189--196, 1999.

[2]

E. Alm and D. Baker. Prediction of protein-folding mechanisms from free-energy landscapes derived from native structures. Proc. Natl. Acad. Sci. USA, 96:11305--11310, 1999.

[3]

N. M. Amato, O. B. Bayazit, L. K. Dale, C. V. Jones, and D. Vallejo. OBPRM: An obstacle-based PRM for 3D workspaces. In Proc. Int. Workshop on Algorithmic Foundations of Robotics (WAFR), pages 155--168, 1998.

Digital Library

[4]

N. M. Amato, O. B. Bayazit, L. K. Dale, C. V. Jones, and D. Vallejo. Choosing good distance metrics and local planners for probabilistic roadmap methods. IEEE Trans. Robot. Automat., 16(4):442--447, August 2000. Preliminary version appeared in ICRA 1998, pp. 630--637.

Digital Library

[5]

N. M. Amato and G. Song. Using motion planning to map protein folding landscapes and analyze folding kinetics of known native structures. Technical Report 01-001, PARASOL Lab, Dept. of Computer Science, Texas A&M University, Oct 2001.

Digital Library

[6]

N. M. Amato and G. Song. Using motion planning to study protein folding pathways. Journal of Computational Biology, 2002. To appear. Preliminary version appeared in RECOMB'01.

Digital Library

[7]

D. Baker. A surprising simplicity to protein folding. Nature, 405:39--42, 2000.

[8]

R.L. Baldwin and G.D. Rose. Is protein folding hierarchic? i. local structure and peptide folding. Trends Biochem Sci., 24:26--33, 1999.

[9]

O. B. Bayazit, G. Song, and N. M. Amato. Ligand binding with OBPRM and haptic user input: Enhancing automatic motion planning with virtual touch. In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pages 954--959, 2001. This work was also presented as a poster at RECOMB'01.

[10]

V. Boor, M. H. Overmars, and A. F. van der Stappen. The Gaussian sampling strategy for probabilistic roadmap planners. In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pages 1018--1023, 1999.

[11]

J.D. Bryngelson, J.N. Onuchic, N.D. Socci, and P.G. Wolynes. Is protein folding hierarchic? i. local structure and peptide folding. Protein Struct. Funct. Genet, 21:167--195, 1995.

[12]

C.M.Dobson, A. Sali, and M. Karplus. Protein folding: a perspective from theory and experiment. Angew. Chem. Int. Ed., 37:868--893, 1998.

[13]

T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to algorithms. MIT Press and McGraw-Hill Book Company, 6th edition, 1992.

Digital Library

[14]

K. A. Dill, K. M. Fiebig, and H. S. Chan. Cooperativity in protein-folding kinetics. Proc. Natl. Acad. Sci. USA, 90:1942--6, 1993.

[15]

Y. Duan and P.A. Kollman. Pathways to a protein folding intermediate observed in a 1-microsecond simulation in aqueous solution. Science, 282:740--744, 1998.

[16]

K. M. Fiebig and K. A. Dill. Protein core assembly processes. J. Chem. Phys, 98(4):3475--3487, 1993.

[17]

L. Han and N. M. Amato. A kinematics-based probabilistic roadmap method for closed chain systems. In Algorithmic and Computational Robotics -- New Directions (WAFR 2000), pages 233--246, 2000.

[18]

D. Hsu, L. Kavraki, J-C. Latombe, R. Motwani, and S. Sorkin. On finding narrow passages with probabilistic roadmap planners. In Proc. Int. Workshop on Algorithmic Foundations of Robotics (WAFR), 1998.

Digital Library

[19]

W. Kabsch and C. Sander. Biopolymers, 22:2577--2637, 1983.

[20]

L. Kavraki. Random Networks in Configuration Space for Fast Path Planning. PhD thesis, Stanford Univ, Computer Science Dept., 1995.

Digital Library

[21]

L. Kavraki, P. Svestka, J. C. Latombe, and M. Overmars. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Automat., 12(4):566--580, August 1996.

[22]

P.T. Lansbury. Evolution of amyloid: What normal protein folding may tell us about fibrillogenesis and disease. Proc. Natl. Acad. Sci. USA, 96:3342--3344, 1999.

[23]

J. C. Latombe. Robot Motion Planning. Kluwer Academic Publishers, Boston, MA, 1991.

Digital Library

[24]

S.M. LaValle, J.H. Yakey, and L.E. Kavraki. A probabilistic roadmap approach for systems with closed kinematic chains. In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), 1999.

[25]

M. Levitt. Protein folding by restrained energy minimization and molecular dynamics. J. Mol. Biol., 170:723--764, 1983.

[26]

M. Levitt, M. Gerstein, E. Huang, S. Subbiah, and J. Tsai. Protein folding: the endgame. Annu. Rev. Biochem., 66:549--579, 1997.

[27]

R. Li and C. Woodward. The hydrogen exchange core and protein folding. Protein Sci., 8:1571--1591, 1999.

[28]

L. Lu and S. Akella. Folding cartons with fixtures: A motion planning approach. In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pages 1570--1576, 1999.

[29]

V. Muñoz and W. A. Eaton. A simple model for calculating the kinetics of protein folding from three dimensional structures. Proc. Natl. Acad. Sci. USA, 96:11311--11316, 1999.

[30]

V. Muñoz, E. R. Henry, J. Hoferichter, and W. A. Eaton. A statistical mechanical model for ß-hairpin kinetics. Proc. Natl. Acad. Sci. USA, 95:5872--5879, 1998.

[31]

J. O'Rourke. Folding and unfolding in computational geometry. In Proc. Japan Conf. Discrete Comput. Geom. '98, pages 142--147, December 1998. Revised version submitted to LLNCS.

Digital Library

[32]

S. E. Radford and C. M. Dobson. Insights into protein folding using physical techiniques: studies of lysozyme and α-lactalbumin. Phil. Trans. R. Soc. Lond., B348:17, 1995.

[33]

G. N. Reeke, Jr. Protein folding: Computational approaches to an exponential-time problem. Ann. Rev. Comput. Sci., 3:59--84, 1988.

Digital Library

[34]

A.P. Singh, J.C. Latombe, and D.L. Brutlag. A motion planning approach to flexible ligand binding. In 7th Int. Conf. on Intelligent Systems for Molecular Biology (ISMB), pages 252--261, 1999.

Digital Library

[35]

G. Song and N. M. Amato. A motion planning approach to folding: From paper craft to protein folding. In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pages 948--953, 2001.

[36]

G. Song and N. M. Amato. Using motion planning to study protein folding pathways. In Proc. Int. Conf. Comput. Molecular Biology (RECOMB), pages 287--296, 2001.

Digital Library

[37]

M. J. Sternberg. Protein Structure Prediction. OIRL Press at Oxford University Press, 1996.

Digital Library

[38]

S. A. Wilmarth, N. M. Amato, and P. F. Stiller. MAPRM: A probabilistic roadmap planner with sampling on the medial axis of the free space. In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pages 1024--1031, 1999.

Digital Library

Cited By

Maximova TPlaku EShehu A(2018)Structure-Guided Protein Transition Modeling with a Probabilistic Roadmap AlgorithmIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2016.258604415:6(1783-1796)Online publication date: 1-Nov-2018
https://doi.org/10.1109/TCBB.2016.2586044
Molloy KShehu A(2016)A General, Adaptive, Roadmap-Based Algorithm for Protein Motion ComputationIEEE Transactions on NanoBioscience10.1109/TNB.2016.251924615:2(158-165)Online publication date: Mar-2016
https://doi.org/10.1109/TNB.2016.2519246
Roudaut AKrusteva DMcCoy MKarnik ARamani KSubramanian S(2016)Cubimorph: Designing modular interactive devices2016 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA.2016.7487508(3339-3345)Online publication date: May-2016
https://doi.org/10.1109/ICRA.2016.7487508
Show More Cited By

Index Terms

Using motion planning to map protein folding landscapes and analyze folding kinetics of known native structures
1. Applied computing
  1. Life and medical sciences
2. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Image and video acquisition
        Motion capture
  2. Computer graphics
    1. Animation
      1. Motion capture
      2. Motion processing

Recommendations

Using motion planning to study protein folding pathways
RECOMB '01: Proceedings of the fifth annual international conference on Computational biology

We present a framework for studying protein folding pathways and potential landscapes which is based on techniques recently developed in the robotics motion planning community. In particular, our work uses Probabilistic Roadmap (PRM) motion planning ...
A motion planning approach to protein folding
Computational studies of protein stability and folding kinetics

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

RECOMB '02: Proceedings of the sixth annual international conference on Computational biology

April 2002

341 pages

ISBN:1581134983

DOI:10.1145/565196

Editors:
Gene Myers
Celera, USA
,
Sridhar Hannenhalli
Celera, USA
,
David Sankoff
University of Montréal, Canada
,
Sorin Istrail
Celera, USA
,
Pavel Pevzner
University of California at San Diego, USA
,
Michael Waterman
University of California, USA

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 April 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

RECOMB02

Sponsor:

RECOMB02: 6th Annual International Conference on Computational Molecular Biology

April 18 - 21, 2002

DC, Washington, USA

Acceptance Rates

RECOMB '02 Paper Acceptance Rate 35 of 118 submissions, 30%;

Overall Acceptance Rate 148 of 538 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
670
Total Downloads

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

Reflects downloads up to 25 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Maximova TPlaku EShehu A(2018)Structure-Guided Protein Transition Modeling with a Probabilistic Roadmap AlgorithmIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2016.258604415:6(1783-1796)Online publication date: 1-Nov-2018
https://doi.org/10.1109/TCBB.2016.2586044
Molloy KShehu A(2016)A General, Adaptive, Roadmap-Based Algorithm for Protein Motion ComputationIEEE Transactions on NanoBioscience10.1109/TNB.2016.251924615:2(158-165)Online publication date: Mar-2016
https://doi.org/10.1109/TNB.2016.2519246
Roudaut AKrusteva DMcCoy MKarnik ARamani KSubramanian S(2016)Cubimorph: Designing modular interactive devices2016 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA.2016.7487508(3339-3345)Online publication date: May-2016
https://doi.org/10.1109/ICRA.2016.7487508
Lindsey AYeh HWu CThomas SAmato NBaldi PWang W(2014)Improving decoy databases for protein folding algorithmsProceedings of the 5th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics10.1145/2649387.2660839(717-724)Online publication date: 20-Sep-2014
https://dl.acm.org/doi/10.1145/2649387.2660839
Manavi KWilson BTapia LRanka SKahveci TSingh M(2012)Simulation and analysis of antibody aggregation on cell surfaces using motion planning and graph analysisProceedings of the ACM Conference on Bioinformatics, Computational Biology and Biomedicine10.1145/2382936.2382995(458-465)Online publication date: 7-Oct-2012
https://dl.acm.org/doi/10.1145/2382936.2382995
Tang XThomas STapia LAmato N(2007)Tools for simulating and analyzing RNA folding kineticsProceedings of the 11th annual international conference on Research in computational molecular biology10.5555/1758222.1758241(268-282)Online publication date: 21-Apr-2007
https://dl.acm.org/doi/10.5555/1758222.1758241
Chiang TApaydin MBrutlag DHsu DLatombe J(2007)Using Stochastic Roadmap Simulation to Predict Experimental Quantities in Protein Folding Kinetics: Folding Rates and Phi-ValuesJournal of Computational Biology10.1089/cmb.2007.R00414:5(578-593)Online publication date: Jun-2007
https://doi.org/10.1089/cmb.2007.R004
Carpin S(2006)Algorithmic motion planningGeneral Theory of Information Transfer and Combinatorics10.5555/2168005.2168059(740-768)Online publication date: 1-Jan-2006
https://dl.acm.org/doi/10.5555/2168005.2168059
Carpin S(2006)Algorithmic Motion Planning: The Randomized ApproachGeneral Theory of Information Transfer and Combinatorics10.1007/11889342_48(740-768)Online publication date: 2006
https://doi.org/10.1007/11889342_48
Chiang TApaydin MBrutlag DHsu DLatombe J(2006)Predicting experimental quantities in protein folding kinetics using stochastic roadmap simulationProceedings of the 10th annual international conference on Research in Computational Molecular Biology10.1007/11732990_34(410-424)Online publication date: 2-Apr-2006
https://dl.acm.org/doi/10.1007/11732990_34
Show More Cited By

View Options

Get Access

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents