Computational Biology, Chemistry & Neuroscience | Algorithms & Applications Group

Algorithms & Applications Group
Computational Biology, Chemistry & Neuroscience

Applictions of Motion Planning to Computational Biology, Chemistry & Neuroscience
supported by NSF
Marco A. Morales A., Xinyu Tang, Lydia Tapia, Shawna Thomas, Nancy Amato, Ken Dill (UCSF), Lawrence Rauchwerger, Marty Scholtz (Medical Biochemistry & Genetics)
Project Alumni: O. Burchan Bayazit, Luke Hunter, Bonnie Kirkpatrick, Jyh-Ming Lien, Kasia Leyk, Guang Song, Annette Stowasser

Motion planning, as its name suggests, plans a path (motion) for a movable object. Even though it originated in, and has mainly been applied to, robotics problems, motion planning as a concept is abstract enough to be applied to any motion related application, ranging from robotics to animation, and most recently to computational biology, chemistry and neuroscience. Our group is investigating applications of probabilistic roadmap (PRM) motion planning methods to protein folding, ligand binding (i.e., drug docking, which arises in drug design), RNA folding, and neuroscience. We also have a Protein Folding Server available where you can submit your proteins for analysis by our motion planning technique.

Protein Folding and Motions

In this research, we study protein folding pathways and protein motions. It is critical that we better understand protein motion and the folding process for several reasons: understanding the folding process can give insight into how to develop better structure prediction algorithms, treatments for diseases such as Alzheimer's and Mad Cow disease can be found by studying protein misfolding, and many biochemical processes are regulated by protein motion.

We propose a technique for computing protein folding pathways and motions based on the successful probabilistic roadmap (PRM) method for robotics motion planning. Our technique can compute thousands of pathways in just a few hours on a single desktop PC. We validated our approach against known experimental results for several small proteins. We have also been able to study protein folding rates and population kinetics extracted from our protein folding landscapes.

Please submit your proteins to our Protein Folding Server for analysis by our motion planning technique. Visit our Protein Folding and Motions Homepage for more information.

Protein Folding and Motions Publications

Ligand Binding

In this project, we present a framework for studying ligand binding which is based on techniques recently developed in the robotics motion planning community. We are especially interested in locating binding sites on the protein for a ligand molecule. Our work investigates the performance of a fully automated motion planner, as well improvements obtained when supplementary user input is collected using a haptic device.

Our results applying an obstacle-based probabilistic roadmap motion planning algorithm (OBPRM) to some known protein-ligand pairs are very encouraging. In particular, we were able to automatically generate configurations close to, and correctly identify, the true binding site in the three protein-ligand complexes we tested. We find that user input helps the planner, and a haptic device helps the user to understand the protein structure by enabling them to feel the forces which are hard to visualize.

Visit our Ligand Binding Homepage for more information.

Ligand Binding Publications

RNA Folding

In this research, we explore a novel motion planning based approach to approximately map the energy landscape of an RNA molecule. Our method is based on the probabilistic roadmap (PRM) motion planners we have successfully applied to study protein folding. The key advantage of our method is that it provides a sparse map that captures the main features of the landscape.

In this work, we also present new computational tools that can be used to study kinetics-based functions for RNA such as population kinetics, folding rates, and the folding of particular subsequences. We provide several different simulation results to validate our method against known experimental data. We also show how our method can study kinetics-based functions for two different case studies.

Visit our RNA Folding Homepage for more information.

RNA Folding Publications

Neuron PRM
The brain has extraordinary computational power to represent and interpret complex natural environments. These natural computations are essentially determined by the topology and geometry of the brain's architectures.

We present a framework to construct a 3D model of a cortical network using probabilistic roadmap methods. Although not the usual motion planning problem, our objective of building a network that encodes the pathways of the cortical network is analogous to the PRM objective of constructing roadmaps that contain a representative sample of feasible paths. We represent the network as a large-scale directed graph, and use L-systems and statistics data to `grow' neurons that are morphologically indistinguishable from real neurons.

Visit our Neuron PRM Homepage for more information.

Neuron PRM Publications

Papers

Protein Folding and Motions

Intelligent Motion Planning and Analysis with Probabilistic Roadmap Methods for the Study of Complex and High-Dimensional Motions, Lydia Tapia, Ph.D. Thesis, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, Texas, Dec 2009.
Ph.D. Thesis(pdf, abstract)

A Motion Planning Approach to Studying Molecular Motions, Lydia Tapia, Shawna Thomas, Nancy M. Amato, Technical Report, TR08-006, Parasol Laboratory, Department of Computer Science, Texas A&M University, Nov 2008.
Technical Report(abstract)

Protein Folding Core Identification from Rigidity Analysis and Motion Planning, Shawna Thomas, Lydia Tapia, Nancy M. Amato, Technical Report, TR08-001, Parasol Laboratory, Department of Computer Science, Texas A&M University, Oct 2008.
Technical Report(ps, pdf, abstract)

Using Dimensionality Reduction to Better Capture RNA and Protein Folding Motions, Lydia Tapia, Shawna Thomas, Nancy M. Amato, Technical Report, TR08-005, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, Texas, U.S.A., Oct 2008.
Technical Report(ps, pdf, abstract)

Techniques for Modeling and Analyzing RNA and Protein Folding Energy Landscapes, Xinyu Tang, Ph.D. Thesis, Department of Computer Science and Engineering, Texas A&M University, Dec 2007.
Ph.D. Thesis(ps, pdf, abstract)

Kinetics Analysis Methods For Approximate Folding Landscapes, Lydia Tapia, Xinyu Tang, Shawna Thomas, Nancy M. Amato, In Int. Conf. on Int. Sys. for Mol. Bio. (ISMB)/European Conf. on Comp. Bio.(ECCB), Vienna, Austria, Jul 2007. Also, Bioinformatics, 23(13):i539-i548, Jul 2007. Also, Technical Report, TR07-002, Parasol Laboratory, Department of Computer Science, Texas A&M University, Feb 2007.
Journal(pdf, abstract) Technical Report(ps, pdf, abstract)

Simulating Protein Motions with Rigidity Analysis, Shawna Thomas, Xinyu Tang, Lydia Tapia, Nancy M. Amato, Journal of Computational Biology, 14(6):839-855, Jul 2007. Also, In Proc. Int. Conf. Comput. Molecular Biology (RECOMB), pp. 394-409, Apr 2006. Also, Technical Report, TR05-008, Parasol Laboratory, Department of Computer Science, Texas A&M University, Sep 2005.
Journal(ps, pdf, abstract) Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)

Roadmap-Based Methods for Studying Protein Folding Kinetics, Lydia Tapia, Xinyu Tang, Shawna Thomas, Nancy M. Amato, Technical Report, TR06-011, Parasol Laboratory, Department of Computer Science, Texas A&M University, Oct 2006.
Technical Report(ps, pdf, abstract)

Parallel Protein Folding with STAPL, Shawna Thomas, Gabriel Tanase, Lucia K. Dale, Jose M. Moreira, Lawrence Rauchwerger, Nancy M. Amato, Concurrency and Computation: Practice and Experience, 17(14):1643-1656, Dec 2005.
Journal(ps, pdf, abstract)

Protein Folding by Motion Planning, Shawna Thomas, Guang Song, Nancy M. Amato, Physical Biology, 2:S148-S155, Nov 2005.
Journal(ps, pdf, abstract)

Parallel Protein Folding with STAPL, Shawna Thomas, Nancy M. Amato, In Proc. IEEE Int. Wkshp. on High Performance Computational Biology, Santa Fe, NM, Apr 2004.
Proceedings(ps, pdf, abstract)

A Motion Planning Approach to Folding: From Paper Craft to Protein Folding, Guang Song, Nancy M. Amato, IEEE Transactions on Robotics and Automation, 20(1):60-71, Feb 2004. Also, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 948-953, Seoul, Korea, May 2001. Also, Technical Report, TR00-017, Department of Computer Science and Engineering, Texas A&M University, Jul 2000.
Journal(ps, pdf, abstract) Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)

A Motion Planning Approach to Protein Folding, Guang Song, Ph.D. Thesis, Parasol Laboratory, Department of Computer Science, Texas A&M University, Dec 2003.
Ph.D. Thesis(ps, abstract)

Using Motion Planning to Map Protein Folding Landscapes and Analyze Folding Kinetics of Known Native Structures, Nancy M. Amato, Ken Dill, Guang Song, Journal of Computational Biology, 10(3-4):239-255, Jun 2003. Also, In Proc. Int. Conf. Comput. Molecular Biology (RECOMB), pp. 2-11, Apr 2002.
Journal(ps, pdf, abstract) Proceedings(pdf, abstract)

A Path Planning-based Study of Protein Folding With a Case Study of Hairpin Formation in Protein G and L, Guang Song, Shawna Thomas, Ken A. Dill, J. Martin Scholtz, Nancy M. Amato, In Proc. Pac. Symp. of Biocomputing (PSB), pp. 240-251, Lihue, HI, Jan 2003.
Proceedings(ps, pdf, abstract)

Using Motion Planning to Study Protein Folding Pathways, Guang Song, Nancy M. Amato, Journal of Computational Biology, 9(2):149-168, Nov 2002. Also, In Proc. Int. Conf. Comput. Molecular Biology (RECOMB), pp. 287-296, Apr 2001. Also, Technical Report, TR00-026, Parasol Laboratory, Department of Computer Science, Texas A&M University, Oct 2000.
Journal(ps, pdf, abstract) Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)

Using Motion Planning to Map Protein Folding Landscapes and Analyze Folding Kinetics of Known Native Structures, Nancy M. Amato, Guang Song, Technical Report, TR01-001, Parasol Laboratory, Department of Computer Science, Texas A&M University, Oct 2001.
Technical Report(ps, pdf, abstract)

A Motion Planning Approach to Folding: From Paper Craft to Protein Structure Prediction, Guang Song, Nancy M. Amato, Technical Report, TR00-001, Department of Computer Science and Engineering, Texas A&M University, Jan 2000.
Technical Report(ps)

Ligand Binding

Solving Motion Planning Problems by Iterative Relaxation of Constraints, Osman Bur�han Bayazit, Ph.D. Thesis, Department of Computer Science and Engineering, Texas A&M University, College Station, Texas, U.S.A., May 2003.
Ph.D. Thesis(ps, pdf, abstract)

Ligand Binding with OBPRM and Haptic User Input, O. Burchan Bayazit, Guang Song, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 954-959, May 2001.
Proceedings(ps, pdf, abstract)

Ligand Binding with OBPRM and Haptic User Input: Enhancing Automatic Motion Planning with Virtual Touch, O. Burchan Bayazit, Guang Song, Nancy M. Amato, Technical Report, TR00-025, Department of Computer Science and Engineering, Texas A&M University, Oct 2000.
Technical Report(ps, pdf, abstract)

RNA Folding

Neuron PRM

Neuron PRM: A Framework for Constructing Cortical Networks, Jyh-Ming Lien, Marco Morales, Nancy M. Amato, Neurocomputing, 52-54(28):191-197, Jun 2003. Also, Technical Report, TR01-002, Parasol Laboratory, Department of Computer Science, Texas A&M University, Oct 2001.
Journal(ps, pdf, abstract) Technical Report(ps, pdf, abstract)

Department of Computer Science and Engineering | Dwight Look College of Engineering | Texas A&M University
Privacy statement: Computer Science and Engineering Engineering TAMU