Motion planning algorithms for molecular simulations: A survey

Rapaport, 2007 Landau, 2005 Woolfson, 1997 Cavanagh, 2006 Robustelli, 2010, Using NMR chemical shifts as structural restraints in molecular dynamics simulations of proteins, Structure, 18, 923, 10.1016/j.str.2010.04.016 Bonneau, 2001, Ab initio protein structure prediction: progress and prospects, Annual Review of Biophysics and Biomolecular Structure, 30, 173, 10.1146/annurev.biophys.30.1.173 Lengauer, 1996, Computational methods for biomolecular docking, Current Opinion in Structural Biology, 6, 402, 10.1016/S0959-440X(96)80061-3 Pain, 2000 Muñoz, 2008 Sugita, 1999, Replica-exchange molecular dynamics method for protein folding, Chemical Physics Letters, 314, 141, 10.1016/S0009-2614(99)01123-9 Marinari, 1992, Simulated tempering: a new Monte Carlo scheme, Europhysics Letters, 19, 451, 10.1209/0295-5075/19/6/002 Laio, 2002, Escaping free-energy minima, Proceedings of the National Academy of Sciences of the United States of America, 99, 12562, 10.1073/pnas.202427399 Shaw, 2010, Atomic-level characterization of the structural dynamics of proteins, Science, 330, 341, 10.1126/science.1187409 LaValle, 2006 Choset, 2005 Tsianos, 2007, Sampling-based robot motion planning: towards realistic applications, Computer Science Review, 1, 2, 10.1016/j.cosrev.2007.08.002 D. Parsons, J.F. Canny, Geometric problems in molecular biology and robotics, in: Proceedings of the International Conference on Intelligent Systems for Molecular Biology, 1994, pp. 322–330. Selkoe, 2003, Folding proteins in fatal ways, Nature, 426, 900, 10.1038/nature02264 Moll, 2007 L.E. Kavraki, Geometric methods in structural computational biology. URL: http://cnx.org/content/col10344/1.6/. Gipson, 2012, Computational models of protein kinematics and dynamics: beyond simulation, Annual Review of Analytical Chemistry, 5, 273, 10.1146/annurev-anchem-062011-143024 Kavraki, 1996, Probabilistic roadmaps for path planning in high-dimensional configuration spaces, IEEE Transactions on Robotics and Automation, 12, 566, 10.1109/70.508439 S.M. LaValle, J.J. Kuffner, Rapidly-exploring random trees: progress and prospects, in: Algorithmic and Computational Robotics: New Directions: The Fourth Workshop on the Algorithmic Foundations of Robotics, 2001, pp. 293–308. Latombe, 1990 Schwartz, 1983, On the piano movers’ problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers, Communications on Pure and Applied Mathematics, 36, 345, 10.1002/cpa.3160360305 Lozano-Peréz, 1983, Spatial planning: a configuration space approach, IEEE Transactions on Computers, 32, 108, 10.1109/TC.1983.1676196 Goldberg, 1995, Completeness in robot motion planning, 419 Reif, 1979, Complexity of the mover’s problem and generalizations, 421 Canny, 1988 Lindemann, 2005, Current issues in sampling-based motion planning, Robotics Research, 36 Geraerts, 2004, A comparative study of probabilistic roadmap planners, 43 LaValle, 2001, Randomized kinodynamic planning, The International Journal of Robotics Research, 20, 378, 10.1177/02783640122067453 Dijkstra, 1959, A note on two problems in connection with graphs, Numerische Mathematik, 1, 269, 10.1007/BF01386390 Hart, 1972, Correction to “A formal basis for the heuristic determination of minimum cost paths”, ACM SIGART Bulletin, 28, 10.1145/1056777.1056779 N.M. Amato, O.B. Bayazit, L.K. Dale, C. Jones, D. Vallejo, OBPRM: an obstacle-based PRM for 3D workspaces, in: Robotics: The Algorithmic Perspective: 1998 Workshop on the Algorithmic Foundations of Robotics, 1998, pp. 155–168. Simeon, 2000, Visibility-based probabilistic roadmaps for motion planning, Advanced Robotics, 14, 477, 10.1163/156855300741960 S.A. Wilmarth, N.M. Amato, P.F. Stiller, MAPRM: a probabilistic roadmap planner with sampling on the medial axis of the free space, in: Proceedings of the IEEE International Conference on Robotics and Automation, vol. 2, 2002, pp. 1024–1031. Sánchez, 2003, A single-query bi-directional probabilistic roadmap planner with lazy collision checking, Robotics Research, 403, 10.1007/3-540-36460-9_27 J.J. Kuffner, S.M. LaValle, RRT-connect: an efficient approach to single-query path planning, in: Proceedings of the IEEE International Conference on Robotics and Automation, vol. 2, 2000, pp. 995–1001. J. Bruce, M. Veloso, Real-time randomized path planning for robot navigation, in: IEEE/RSJ International Conference on Intelligent Robots and Systems, vol. 3, 2002, pp. 2383–2388. P. Cheng, S.M. LaValle, Resolution complete rapidly-exploring random trees, in: Proceedings of the IEEE International Conference on Robotics and Automation, vol. 1, 2002, pp. 267–272. S. Rodriguez, X. Tang, J.M. Lien, N.M. Amato, An obstacle-based rapidly-exploring random tree, in: Proceedings of the IEEE International Conference on Robotics and Automation, 2006, pp. 895–900. D. Hsu, J.-C. Latombe, R. Motwani, Path planning in expansive configuration spaces, in: Proceedings of the IEEE International Conference on Robotics and Automation, vol. 3, 1997, pp. 2719–2726. Ladd, 2005, 297 Şucan, 2009, Kinodynamic motion planning by interior–exterior cell exploration, vol. 57, 449 Leach, 2001 Koliński, 2010 Berman, 2002, The protein data bank, Acta Crystallographica Section D: Biological Crystallography, 58, 899, 10.1107/S0907444902003451 Schlick, 2010, vol. 21 Scott, 1966, Conformational analysis of macromolecules. II. The rotational isomeric states of the normal hydrocarbons, Journal of Chemical Physics, 44, 3054, 10.1063/1.1727180 Manocha, 1995, Conformational analysis of molecular chains using nano-kinematics, Computer Applications in the Biosciences: CABIOS, 11, 71 LaValle, 2000, A randomized kinematics-based approach to pharmacophore-constrained conformational search and database screening, Journal of Computational Chemistry, 21, 731, 10.1002/(SICI)1096-987X(20000715)21:9<731::AID-JCC3>3.0.CO;2-R Zhang, 2002, A new method for fast and accurate derivation of molecular conformations, Journal of Chemical Information and Computer Sciences, 42, 64, 10.1021/ci010327z Noonan, 2005, Probik: protein backbone motion by inverse kinematics, The International Journal of Robotics Research, 24, 971, 10.1177/0278364905059108 Xie, 2003 Angeles, 2007 Sciavicco, 2001 Spong, 2006 M.L. Teodoro, G.N. Phillips Jr., L.E. Kavraki, Molecular docking: a problem with thousands of degrees of freedom, in: Proceedings of the IEEE International Conference on Robotics and Automation, vol. 1, 2001, pp. 960–965. Cavasotto, 2005, The challenge of considering receptor flexibility in ligand docking and virtual screening, Current Computer-Aided Drug Design, 1, 423, 10.2174/157340905774330291 Jones, 1997, Development and validation of a genetic algorithm for flexible docking, Journal of Molecular Biology, 267, 727, 10.1006/jmbi.1996.0897 Apostolakis, 1998, Docking small ligands in flexible binding sites, Journal of Computational Chemistry, 19, 21, 10.1002/(SICI)1096-987X(19980115)19:1<21::AID-JCC2>3.0.CO;2-0 Pak, 2000, Application of a molecular dynamics simulation method with a generalized effective potential to the flexible molecular docking problems, The Journal of Physical Chemistry B, 104, 354, 10.1021/jp993073h Thomas, 2007, Simulating protein motions with rigidity analysis, Journal of Computational Biology, 14, 839, 10.1089/cmb.2007.R019 Thorpe, 1999 Wells, 2005, Constrained geometric simulation of diffusive motion in proteins, Physical Biology, 2, 127, 10.1088/1478-3975/2/4/S07 Cortés, 2010, Simulating ligand-induced conformational changes in proteins using a mechanical disassembly method, Physical Chemistry Chemical Physics, 12, 8268, 10.1039/c002811h I.K. Fodor, A survey of dimension reduction techniques, Tech. Rep. UCRL-ID-148494, Lawrence Livermore National Lab, June 2002. L.J.P. van der Maaten, E.O. Postma, H.J. van den Herik, Dimensionality reduction: a comparative review, Tech. Rep. TiCC-TR 2009-005, Tilburg University, 2009. Jolliffe, 2002 Das, 2006, Low-dimensional, free-energy landscapes of protein-folding reactions by nonlinear dimensionality reduction, Proceedings of the National Academy of Sciences, 103, 9885, 10.1073/pnas.0603553103 Altis, 2007, Dihedral angle principal component analysis of molecular dynamics simulations, The Journal of Chemical Physics, 126, 244111, 10.1063/1.2746330 Mu, 2005, Energy landscape of a small peptide revealed by dihedral angle principal component analysis, Proteins: Structure, Function, and Bioinformatics, 58, 45, 10.1002/prot.20310 Tenenbaum, 2000, A global geometric framework for nonlinear dimensionality reduction, Science, 290, 2319, 10.1126/science.290.5500.2319 Plaku, 2007, Fast and reliable analysis of molecular motion using proximity relations and dimensionality reduction, Proteins: Structure, Function, and Bioinformatics, 67, 897, 10.1002/prot.21337 Cui, 2006 Hinsen, 1998, Analysis of domain motions by approximate normal mode calculations, Proteins: Structure, Function, and Bioinformatics, 33, 417, 10.1002/(SICI)1097-0134(19981115)33:3<417::AID-PROT10>3.0.CO;2-8 Tama, 2001, Conformational change of proteins arising from normal mode calculations, Protein Engineering, 14, 1, 10.1093/protein/14.1.1 Kirillova, 2008, An NMA-guided path planning approach for computing large-amplitude conformational changes in proteins, Proteins: Structure, Function, and Bioinformatics, 70, 131, 10.1002/prot.21570 Rao, 1973, Comparison of super-secondary structures in proteins, Journal of Molecular Biology, 76, 241, 10.1016/0022-2836(73)90388-4 Rossmann, 1976, Exploring structural homology of proteins, Journal of Molecular Biology, 105, 75, 10.1016/0022-2836(76)90195-9 Falicov, 1996, A surface of minimum area metric for the structural comparison of proteins, Journal of Molecular Biology, 258, 871, 10.1006/jmbi.1996.0294 Holm, 1993, Protein structure comparison by alignment of distance matrices, Journal of Molecular Biology, 233, 123, 10.1006/jmbi.1993.1489 Wallin, 2003, Testing similarity measures with continuous and discrete protein models, Proteins: Structure, Function, and Bioinformatics, 50, 144, 10.1002/prot.10271 Lotan, 2004, Approximation of protein structure for fast similarity measures, Journal of Computational Biology, 11, 299, 10.1089/1066527041410355 Shehu, 2010, Guiding the search for native-like protein conformations with an ab-initio tree-based exploration, International Journal of Robotics Research, 29, 1106, 10.1177/0278364910371527 J. Cortés, L. Jaillet, T. Siméon, Molecular disassembly with RRT-like algorithms, in: IEEE International Conference on Robotics and Automation, 2007, pp. 3301–3306. Jiménez, 2001, 3D collision detection: a survey, Computers & Graphics, 25, 269, 10.1016/S0097-8493(00)00130-8 Lin, 2003, Collision and proximity queries Gottschalk, 1996, OBBTree: a hierarchical structure for rapid interference detection, 171 van den Bergen, 1998, Efficient collision detection of complex deformable models using AABB trees, Journal of Graphics Tools, 2, 1, 10.1080/10867651.1997.10487480 Cohen, 1995, I-COLLIDE: an interactive and exact collision detection system for large-scale environments, 189 Soss, 2003, Preprocessing chains for fast dihedral rotations is hard or even impossible, Computational Geometry, 26, 235, 10.1016/S0925-7721(02)00156-6 Agarwal, 2004, Collision detection for deforming necklaces, Computational Geometry, 28, 137, 10.1016/j.comgeo.2004.03.008 Lotan, 2002, Efficient maintenance and self-collision testing for kinematic chains, 43 Ruiz de Angulo, 2005, BioCD: an efficient algorithm for self-collision and distance computation between highly articulated molecular models, 241 Rangwala, 2010, vol. 14 Coutsias, 2004, A kinematic view of loop closure, Journal of Computational Chemistry, 25, 510, 10.1002/jcc.10416 Kolodny, 2005, Inverse kinematics in biology: the protein loop closure problem, International Journal of Robotics Research, 24, 151, 10.1177/0278364905050352 Cortés, 2005, Sampling-based motion planning under kinematic loop-closure constraints, 75 Cortés, 2005, A path planning approach for computing large-amplitude motions of flexible molecules, Bioinformatics, 21, i116, 10.1093/bioinformatics/bti1017 Yao, 2008, Efficient algorithms to explore conformation spaces of flexible protein loops, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 5, 534, 10.1109/TCBB.2008.96 Canutescu, 2003, Cyclic coordinate descent: a robotics algorithm for protein loop closure, Protein Science, 12, 963, 10.1110/ps.0242703 Griffiths, 2005 Burkert, 1982 Ponder, 2003, Force fields for protein simulations, Advances in Protein Chemistry, 66, 27, 10.1016/S0065-3233(03)66002-X Mackerell, 2004, Empirical force fields for biological macromolecules: overview and issues, Journal of Computational Chemistry, 25, 1584, 10.1002/jcc.20082 Tozzini, 2005, Coarse-grained models for proteins, Current Opinion in Structural Biology, 15, 144, 10.1016/j.sbi.2005.02.005 Monticelli, 2008, The MARTINI coarse-grained force field: extension to proteins, Journal of Chemical Theory and Computation, 4, 819, 10.1021/ct700324x Derreumaux, 1999, From polypeptide sequences to structures using Monte Carlo simulations and an optimized potential, Journal of Chemical Physics, 111, 2301, 10.1063/1.479501 Singh, 1999, A motion planning approach to flexible ligand binding, 252 M.S. Apaydin, A.P. Singh, D.L. Brutlag, J.-C. Latombe, Capturing molecular energy landscapes with probabilistic conformational roadmaps, in: Proceedings of the IEEE International Conference on Robotics and Automation, vol. 1, 2001, pp. 932–939. Apaydin, 2002, Stochastic roadmap simulation for the study of ligand–protein interactions, Bioinformatics, 18, S18, 10.1093/bioinformatics/18.suppl_2.S18 Apaydin, 2003, Stochastic roadmap simulation: an efficient representation and algorithm for analyzing molecular motion, Journal of Computational Biology, 10, 257, 10.1089/10665270360688011 Apaydin, 2004, Stochastic conformational roadmaps for computing ensemble properties of molecular motion, 131 Chiang, 2006, Predicting experimental quantities in protein folding kinetics using stochastic roadmap simulation, 410 Chiang, 2007, Using stochastic roadmap simulation to predict experimental quantities in protein folding kinetics: folding rates and phi-values, Journal of Computational Biology, 14, 578, 10.1089/cmb.2007.R004 Metropolis, 1953, Equation of state calculations by fast computing machines, Journal of Chemical Physics, 21, 1087, 10.1063/1.1699114 Frenkel, 2002 Amato, 2002, Using motion planning to study protein folding pathways, Journal of Computational Biology, 9, 149, 10.1089/10665270252935395 G. Song, S. Thomas, K.A. Dill, J.M. Scholtz, N.M. Amato, A path planning-based study of protein folding with a case study of hairpin formation in protein G and L, in: Pacific Symposium on Biocomputing, 2003, pp. 240–251. Amato, 2003, Using motion planning to map protein folding landscapes and analyze folding kinetics of known native structures, Journal of Computational Biology, 10, 239, 10.1089/10665270360688002 Thomas, 2005, Protein folding by motion planning, Physical Biology, 2, 148, 10.1088/1478-3975/2/4/S09 Tang, 2005, Using motion planning to study RNA folding kinetics, Journal of Computational Biology, 12, 862, 10.1089/cmb.2005.12.862 Tapia, 2007, Kinetics analysis methods for approximate folding landscapes, Bioinformatics, 23, 539, 10.1093/bioinformatics/btm199 Tang, 2008, Simulating RNA folding kinetics on approximated energy landscapes, Journal of Molecular Biology, 381, 1055, 10.1016/j.jmb.2008.02.007 Tapia, 2010, A motion planning approach to studying molecular motions, Communications and Information Systems, 10, 53, 10.4310/CIS.2010.v10.n1.a4 Yang, 2007, Temperature-dependent probabilistic roadmap algorithm for calculating variationally optimized conformational transition pathways, Journal of Chemical Theory and Computation, 3, 17, 10.1021/ct0502054 Li, 2008, Predicting the folding pathway of engrailed homeodomain with a probabilistic roadmap enhanced reaction-path algorithm, Biophysical Journal, 94, 1622, 10.1529/biophysj.107.119214 Cortés, 2004, Geometric algorithms for the conformational analysis of long protein loops, Journal of Computational Chemistry, 25, 956, 10.1002/jcc.20021 Enosh, 2008, Generation, comparison, and merging of pathways between protein conformations: gating in K-channels, Biophysical Journal, 95, 3850, 10.1529/biophysj.108.135285 Raveh, 2009, Rapid sampling of molecular motions with prior information constraints, PLoS Computational Biology, 5, e1000295, 10.1371/journal.pcbi.1000295 Cortés, 2008, Disassembly path planning for complex articulated objects, IEEE Transactions on Robotics, 24, 475, 10.1109/TRO.2008.915464 Jaillet, 2010, Sampling-based path planning on configuration-space costmaps, IEEE Transactions on Robotics, 26, 635, 10.1109/TRO.2010.2049527 Jaillet, 2011, Randomized tree construction algorithm to explore energy landscapes, Journal of Computational Chemistry, 32, 3464, 10.1002/jcc.21931 R. Iehl, J. Cortés, T. Siméon, Costmap planning in high dimensional configuration spaces, in: Proceedings of the IEEE/ASME International Conference on Advanced Intelligent Mechatronics, August 2012 (in press). Haspel, 2010, Tracing conformational changes in proteins, BMC Structural Biology, 10, S1, 10.1186/1472-6807-10-S1-S1 Barbe, 2011, A mixed molecular modelling—robotics approach to investigate lipase large molecular motions, Proteins: Structure, Function, and Bioinformatics, 79, 2517, 10.1002/prot.23075 Maragakis, 2005, Large amplitude conformational change in proteins explored with a plastic network model: adenylate kinase, Journal of Molecular Biology, 352, 807, 10.1016/j.jmb.2005.07.031 Kirkpatrick, 1983, Optimization by simulated annealing, Science, 220, 671, 10.1126/science.220.4598.671 Dobson, 2003, Protein folding and misfolding, Nature, 426, 884, 10.1038/nature02261 Zaki, 2008 Balbach, 1995, Following protein folding in real time using NMR spectroscopy, Nature Structural & Molecular Biology, 2, 865, 10.1038/nsb1095-865 Dyson, 2004, Unfolded proteins and protein folding studied by NMR, Chemical Reviews, 104, 3607, 10.1021/cr030403s Chan, 1997, Submillisecond protein folding kinetics studied by ultrarapid mixing, Proceedings of the National Academy of Sciences of the United States of America, 94, 1779, 10.1073/pnas.94.5.1779 Jones, 1993, Fast events in protein folding initiated by nanosecond laser photolysis, Proceedings of the National Academy of Sciences of the United States of America, 90, 11860, 10.1073/pnas.90.24.11860 Unger, 1993, Genetic algorithms for protein folding simulations, Journal of Molecular Biology, 231, 75, 10.1006/jmbi.1993.1258 Onuchic, 2004, Theory of protein folding, Current Opinion in Structural Biology, 14, 70, 10.1016/j.sbi.2004.01.009 Dill, 2008, The protein folding problem, Annual Review of Biophysics, 37, 289, 10.1146/annurev.biophys.37.092707.153558 Bryngelson, 1995, Funnels, pathways, and the energy landscape of protein folding: a synthesis, Proteins: Structure, Function, and Bioinformatics, 21, 167, 10.1002/prot.340210302 Goodsell, 1996, Automated docking of flexible ligands: applications of autodock, Journal of Molecular Recognition, 9, 1, 10.1002/(SICI)1099-1352(199601)9:1<1::AID-JMR241>3.0.CO;2-6 Lang, 2009, DOCK 6: combining techniques to model RNA—small molecule complexes, RNA, 15, 1219, 10.1261/rna.1563609 Rarey, 1996, A fast flexible docking method using an incremental construction algorithm, Journal of Molecular Biology, 261, 470, 10.1006/jmbi.1996.0477 Jones, 1997, Development and validation of a genetic algorithm for flexible docking, Journal of Molecular Biology, 267, 727, 10.1006/jmbi.1996.0897 Abagyan, 1994, ICM—a new method for protein modeling and design: applications to docking and structure prediction from the distorted native conformation, Journal of Computational Chemistry, 15, 488, 10.1002/jcc.540150503 Goldberg, 1989 Hajduk, 2007, A decade of fragment-based drug design: strategic advances and lessons learned, Nature Reviews Drug Discovery, 6, 211, 10.1038/nrd2220 Sousa, 2006, Protein–ligand docking: current status and future challenges, Proteins: Structure, Function, and Bioinformatics, 65, 15, 10.1002/prot.21082 Guieysse, 2008, A structure-controlled investigation of lipase enantioselectivity by a path-planning approach, ChemBioChem, 9, 1308, 10.1002/cbic.200700548 Lafaquière, 2009, Control of lipase enantioselectivity by engineering the substrate binding site and access channel, ChemBioChem, 10, 2760, 10.1002/cbic.200900439