Research Projects
(Last updated, July 2006. For the earlier “Research Projects” page see here.)

-----

 

The goal of our research is to design and test new algorithms and techniques to represent, sense, plan, and control motions of physical objects. One key underlying issue is to efficiently capture the connectivity of configuration or state spaces that are both high-dimensional and geometrically complex. Current projects aim at extending Probabilistic Road-Map (PRM) motion planners, sensing and manipulating deformable objects, simulating large bio-molecules (proteins), and designing new techniques to enable multi-limbed robots to navigate on severely rough (broken, irregular, steep, non rigid) terrain.

 

Probabilistic roadmaps are a key tool used (and for a large part developed) in our group to represent the connectivity of complex, high-dimensional motion spaces. There is an extensive literature on PRM. For an introduction, see:

-        L.E. Kavraki, P. Svestka, J.C. Latombe, and M. Overmars. Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces. IEEE Transactions on Robotics and Automation, 12(4):566-580, 1996.

-        L.E. Kavraki. Sampling-Based Algorithms. In Principles of Robot Motion: Theory, Algorithms, and Implementation, H. Choset et al. (eds.), Chapter 7, 197-267, MIT Press, 2005.

 

Slides on PRM are also available here:

-        Motion Planning (ppt).

-        Randomized Motion Planning (ppt).

-        SBL Planner (ppt).

-        Sampling and Connection Strategies for PRM Planners (ppt).

-        On the Probabilistic Foundations of Probabilistic Roadmaps (ppt) [Invited talk given at WAFR’06]

 

A downloadable PRM toolkit (MPK: Motion Planning Kit) is available here.

 

 

-----

Recent and current projects:

 

·        Adaptive dynamic collision checking

·        Multi-goal motion planning

·        Small-step retraction in PRM planning

·        Rope manipulation planning

·        3-D Sensing of deformable objects

·        Climbing robots

·        Humanoid robots on rough terrain

·        Study of protein motion

·        Modeling flexible protein loops

 

-----


Adaptive dynamic collision checking

 

Static collision checking amounts to testing a given configuration of objects for overlaps. In contrast, the goal of dynamic checking is to determine whether all configurations along a continuous path are collision-free. While effective methods are available for static collision detection, dynamic checking still lacks methods that are both reliable and efficient. A common approach – frequently used in PRM planners – is to sample paths at some fixed, pre-specified resolution and statically test each sampled configuration. But this approach is not guaranteed to detect collision whenever one occurs, especially when objects are thin (Figure 1). One may increase the reliability of the approach by refining the sampling resolution along the entire path, but a finer resolution increases the running time of the collision checker. We introduce a new method for testing straight path segments in configuration space, or collections of such segments, which is both reliable and efficient. This method locally adjusts the sampling resolution by comparing lower bounds on distances between objects in relative motion with higher bounds on lengths of curves traced by points of these moving objects. Several additional techniques and heuristics further improve the checker’s efficiency in scenarios with many moving objects (e.g., articulated arms and/or multiple robots) and high geometric complexity. Our new method is general, but particularly well suited for use in PRM planners. Extensive tests, in particular on randomly generated path segments and on multi-segment paths produced by PRM planners, show that the new method compares favorably with a fixed-resolution approach at “suitable” resolution, with the enormous advantage that it never fails to detect collision.

 


Figure 1


Video clip (2.59MB)

 

Slides (ppt)

 

Publications:

-          F. Schwarzer, M. Saha, and J.C. Latombe. Exact Collision Checking of Robot Paths. In Algorithmic Foundations of Robotics V, J.D. Boissonnat, J. Burdick, K. Goldberg, and S. Hutchinson (eds.), Springer Tracts in Advanced Robotics, Springer, pp. 25-41, 2004.

-          F. Schwarzer, M. Saha, and J.C. Latombe. Adaptive Dynamic Collision Checking for Single and Multiple Articulated Robots in Complex Environments. IEEE Tr. on Robotics, 21(3):338-353, June 2005.

 

Funding: General Motors, NSF ACI-02-5671.

Any opinions, findings, and conclusions or recommendations expressed in the above material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

 

-----

 

Multi-goal motion planning

 

We consider a motion planning problem that occurs in tasks, such as spot welding, car painting, inspection, and measurement, where the end-effector of a robotic arm must reach successive goal placements given as inputs (Figure 1). The problem is to compute a near-optimal path of the arm so that the end-effector visits each goal once. It combines two notoriously hard sub-problems – the collision-free shortest path and the traveling-salesman problems. It is further complicated by the fact that each goal placement of the end-effector may be achieved by several configurations of the arm – typically, distinct solutions of the arm’s inverse kinematics (Figure 2). This leads us to construct a set of goal configurations of the robot that are partitioned into groups. The planner must compute a robot path that visits one configuration in each group and is near optimal over all configurations in every goal group and over all group orderings (Figure 3). Our algorithm operates under the assumption that the computational cost of finding a good path between two goal configuration dominates that of finding a good tour in a graph of with edges of given costs. So, our algorithm tries to minimize the number of times it computes a path between two goal configurations. Although it still computes a quadratic number of such paths in the worst-case, experimental results show that it is much faster in practice. Our algorithm makes use of a recent approximation algorithm for the group Steiner tree problem [C. Chekuri, G. Even, and G. Kortsarz. A Greedy Approximation for the Group Steiner Problem. To appear in Discrete Applied Mathematics].

 

            

Figure 1                               Figure 2                                      Figure 3      

 

Publications:                         

-          M. Saha, G. Sánchez-Ante, and J.C. Latombe. Planning Multi-Goal Tours for Robot Arms. IEEE Int. Conference on Robotics and Automation, Taipei, Taiwan, 2003.

-          M. Saha, G. Sánchez-Ante, J.C. Latombe, and T. Roughgarden. Planning Multi-Goal Tours for Robot Arms. Int. J. Robotics Research, 25(3):207-223, March 2006.

 

Funding: General Motors, ABB, NSF ACI-02-5671.

Any opinions, findings, and conclusions or recommendations expressed in the above material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

 

-----

 

Small-step retraction in PRM planning

 

PRM planners have been successfully used to plan complex robot motions in configuration spaces of various dimensionalities. But their efficiency decreases dramatically in spaces with narrow passages. Here, we investigate a new method – which we call small-step retraction – that helps PRM planners find paths through such passages. The method relies on the empirical observation that widening narrow passages by only a small amount greatly facilitates the task of sampling configurations into them. So, it consists of slightly “fattening” the robot’s free space, constructing a roadmap in the fattened free space, and finally repairing portions of this roadmap by retracting them out of collision into the actual free space. The fattened free space is not explicitly computed. Instead, the geometric models of the workspace objects (robot links and/or obstacles) are “thinned” around their medial axis. A robot configuration lies in fattened free space if the thinned objects do not collide at this configuration. Two repair strategies are proposed. The “optimist” strategy waits until a complete path has been found in fattened free space before repairing it. Instead, the “pessimist” strategy repairs the roadmap as it is being built. The former is usually very fast, but may fail in some pathological cases where the computed path crosses “false” passages. The latter is more reliable, but not as fast. A simple combination of the two strategies yields an integrated planner that is both fast and reliable. This planner was implemented as an extension of a pre-existing single-query PRM planner, SBL (see MPK toolkit). Comparative tests on various examples (Figure 1) show that it is significantly faster (sometimes by several orders of magnitude) than SBL.

 

Figure 1

 


Video clip (3.66MB)

 

Slides (ppt)

 

Publications:

-          M. Saha and J.C. Latombe. Finding Narrow Passages with Probabilistic Roadmaps: The Small Step Retraction Method. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, Edmonton, Canada, 2005.

-          M. Saha, J.C. Latombe, Y.-C. Chang, F. Prinz. Finding Narrow Passages with Probabilistic Roadmaps: The Small-Step Retraction Method. Autonomous Robots, 19(3):301-319, Dec. 2005.

-          H.L. Chen, D. Hsu, J.C. Latombe, G. Sanchez. Multi-Level Free-Space Dilation for Sampling Narrow Passages in PRM Planning. To appear in Proc. IEEE Int. Conf. on Robotics and Automation (ICRA), Orlando, FL, 2006.

 

Funding: General Motors, ABB, NSF ACI-02-5671.

 

-----

 

Rope manipulation planning

 

The goal is to design motion planning methods to manipulate a rope (linear deformable object) and to perform tasks such as tying self-knots and/or knots around other objects (Figure 1). One possible application is robotized suturing in medical surgery. The goal configuration of the rope is defined topologically (Figure 2) by the crossings of the rope with itself and with other objects (“crossing configuration”). Our planner operates in two stages. First, assuming one end of the rope is fixed, the planner computes a path of the other end to achieve the successive crossings (Figure 3). Next, a sequence of paths is computed using a PRM planner for two manipulator arms to move the rope (Figure 4). The planner assumes the existence of removable static sliding supports (which we call “tri-fingers”) to provide structural support and keep “loops” wide enough to enable further manipulation (Figure 5, video). The behavior of the rope is defined by a “rope simulator”. The planner is independent of this simulator.

 

r2-12-1

Figure 1

 

bowline2 k12b      cont-inp-seq-1r2

Figure 2                                                                 Figure 3

 

manip-prob-1r2

Figure 4

 

tr3-p

Figure 5

 


Video clip (7.20MB)

 

Slides (ppt)

 

Publications:

-          J. Brown, J.C. Latombe, and K. Montgomery. Real-Time Knot Tying Simulation. The Visual Computer J., 20(2-3):165-179, May 2004.

-          M. Saha and P. Isto. Motion Planning for Robotic Manipulation of Deformable Linear Objects. Proc. IEEE Int. Conf. on Robotics and Automation (ICRA), Orlando, FL, 2006.

-          P. Isto and M. Saha. A Slicing Connection Strategy for Constructing PRMs in High-Dimensional Cspaces. Proc. IEEE Int. Conf. on Robotics and Automation (ICRA), Orlando, FL, 2006.

-          M. Saha, P. Isto, and J.C. Latombe. Motion Planning for Robotic Manipulation of Deformable Linear Objects. Int. Symp. On Experimental Robotics (ISER), Rio de Janeiro, Brazil, July 2006.

 

Funding: General Motors, ABB, NSF ACI-02-5671.

 

-----

 

3-D Sensing of deformable objects

 

In applications like motion capture, high-speed crash tests, and robotic manipulation of deformable objects, there is a critical need for capturing 3-D videos of fast moving and/or deforming objects. A 3-D video is a sequence of 3-D representations at high time and space resolution. Although many 3-D sensing techniques are available, most cannot deal with dynamic scenes (e.g., laser scanning). Others, like stereovision, require that object surfaces be appropriately textured. Few, if any, build high-resolution 3-D models of dynamic scenes. We develop a sensor capable of generating high-resolution range maps from single images of moving and deforming objects. The method is based on observing the deformation of a projected light pattern that combines a set of parallel colored stripes and a perpendicular set of sinusoidal intensity stripes (Figure 1). While the colored stripes allow the sensor to compute absolute depths at coarse resolution, the sinusoidal intensity stripes give dense relative depths (Figure 2). This twofold pattern makes it possible to extract a high-resolution range map from each image in a video sequence (Figure 3). This approach is based on sound mathematical principles, but its implementation requires giving great care to a number of low-level details. In particular, the sensor has been implemented using commercial off the shelf hardware, which distorts sensed and transmitted signals in many ways. A novel method was developed to characterize and compensate for distortions due to chromatic aberrations. The sensor has been implemented and tested on several deforming objects (videos). This work is done in collaboration with Prof. Ken Salisbury (surgical simulation).

 

  
Figure 1                                             Figure 2

 

    
Figure 3

 

Video (2.6 MB) showing a water balloon bouncing around.  It was shot at 100 fps but plays back at 15 fps so you can see what's happening.

Video (1.8 MB) showing a person moving a popcorn tin around.

Video (2.0 MB) showing a flag being waved side to side.

Video (2.0MB) showing sand being pushed with a wood stick.

 

Slides (pdf)

 

Publications:

-          P. Fong and F. Buron. High-Resolution Three-Dimensional Sensing of Fast Deforming Objects. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), August 2005, Edmonton, Alberta, Canada.

-          P. Fong and F. Buron. Sensing Moving and Deforming Objects with Commercial Off the Shelf Hardware, IEEE Int. Workshop on Projector-Camera Systems (PROCAMS), June 2005, San Diego, CA, USA.

 

Funding: NIH grant R33LM07295 and NSF grant ACI-02-5671.

Any opinions, findings, and conclusions or recommendations expressed in the above material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation and the National Institute of Health.

 

-----

 

Climbing robots

 

The goal of this research is to enable a multi-limbed robot to climb vertical rock using techniques similar to those developed by human climbers (Figure 1). The robot consists of a small number of articulated limbs. Only the limb end-points can make contact with the environment—a vertical surface with small, arbitrarily distributed features called holds (Figure 2). A path through this environment is a sequence of one-step climbing moves in which the robot brings a limb end-point to a new hold. The robot maintains balance during each move by pushing and/or pulling at other holds, exploiting contact and friction at these holds while adjusting internal degrees of freedom to avoid sliding. The fixed set of robot-hold contacts during a one-step move is called a stance. Our planner combines a multi-step and a one-step planner. The multi-step planner searches a graph representing the adjacency relation between stances to compute a sequence of steps from the initial to the goal stance. The one-step planner (a PRM planner) searches the robot’s configuration space at a given stance for a feasible path between the previous and the next stance in the sequence computed by the multi-step planner. The one-step planner makes use of an efficient test efficient of the quasi-static equilibrium of thee robot. The multi-step planner makes use of lazy search techniques to speed up the exploration of the stance graph. It also makes use of a trained classifier to quickly recognize infeasible transitions between stances. The planner was tested in simulation and on a real four-limbed robot—LEMUR IIB—created by NASA/JPL (Figure 2). A new climbing robot with an increased number of degrees of freedom is currently being developed (Figure 3). In another develop, we adapt and extend the planner to the ATHLETE robot, a six-legged vehicle designed by NASA/JPL to climb steep, irregular, and possibly non-rigid lunar terrain (Figure 4). In such terrain ATHLETE’s wheels are frozen and are used as “feet”. This project is a joint effort with the group of Prof. Steve Rock in the Stanford Aerospace Robotics Lab.

 


Figure 1

 

  
Figure 2

 

 

Figure 3

 

 

Figure 4

 

onthewall 

video clip (6.27MB)

 

ATHLETE video clip (6.85MB)

 

Slides (ppt)

 

Tim Bretl’s webpage

 

Publications:

-          T. Bretl, S.M. Rock, and J.C. Latombe.  Motion Planning for a Three-Limbed Climbing Robot in Vertical Natural Terrain. IEEE Int. Conf. on Robotics and Automation, Taipei, Taiwan, 2003.

-          T. Bretl, T. Miller, S.M. Rock, and J.C. Latombe. Climbing Robots in Natural Terrain.  7th Int. Symp. on Artificial Intelligence, Robotics and Automation in Space, Nara, Japan, May 2003.

-          T. Bretl, J.C. Latombe, and S. Rock. Toward Autonomous Free-Climbing Robots. 11th Int. Symp. on Robotics Research, Siena, Italy, Oct. 19-22, 2003. Published in P. Dario and R. Chatila (eds.), Robotics Research, Springer, pp. 6-15, 2005.

-          T. Bretl, S.M. Rock, J.C. Latombe, B. Kennedy, and H. Aghazarian. Free-Climbing with a Multi-Use Robot. 9th Int. Symp. on Experimental Robotics, Singapore, 18-21 June 2004.

-          T. Bretl, S. Lall, J.C. Latombe, S.M. Rock. Multi-Step Motion Planning for Free-Climbing Robots. 6th International Workshop on the Algorithmic Foundations of Robotics (WAFR’04), Utrecht/Zeist, The Netherlands, July 11-13, 2004.

-          K. Hauser, T. Bretl, J.C. Latombe. Learning-Assisted Multi-Step Planning. IEEE Int. Conf. on Robotics and Automation, Barcelona, 2005.

-          T. Bretl and S. Lall. A Fast and Adaptive Test of Static Equilibrium for Legged Robots. To appear in Proc. IEEE Int. Conf. on Robotics and Automation (ICRA), Orlando, FL, 2006.

-          T. Bretl. Motion Planning of Multi-Limbed Robots Subject to Equilibrium Constraints: The Free-Climbing Robot Problem. Int. J. of Robotics Research, 25(4):317-342, Apr 2006.

 

Funding: NSF grant IIS-0412884, NASA.

Any opinions, findings, and conclusions or recommendations expressed in the above material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation and NASA.


-----

 

Humanoid and legged robots on rough terrain

 

This work extends the motion planner developed for climbing robots to humanoid robots moving on very uneven and sloped terrain. In particular, we consider the HRP-2 robot developed by AIST. The extended planner allows contact with any pre-designated part of the robot’s body, since the use of hands or knees (in addition to feet) may be required to achieve equilibrium. As it uses a PRM approach to compute each step, one challenge is that most randomly sampled configurations do not satisfy all motion constraints (closed-chain, equilibrium, collision). To address this problem, a method of iterative constraint enforcement has been developed that samples feasible configurations much more quickly than pure rejection sampling. So far, the planner has only been tested in simulation (Figure 1).

 

Figure 1

 

Video clips: 1 (3.4MB) and 2 (9.89MB)

 

Publications:

-     K. Hauser, T. Bretl, and J.C. Latombe.  Non-Gaited Humanoid Locomotion Planning. Humanoids 2005, Tsukuba, Japan, Dec. 2005.

-     K. Hauser, T. Bretl, K. Harada, J.C. Latombe. Using Motion Primitives in Probabilistic Sample-Based Planning for Humanoid Robots. Workshop on Algorithmic Foundations of Robotics (WAFR), New-York, NY, July 2006. Published in Algorithmic Foundation of Robotics VII, Springer Tracts in Advanced Robotics, Vol. 47, pp. 507-522, 2008. Motion Planning for Legged Robots on Varied Terrain. K. Hauser, T. Bretl, J.C. Latombe, K. Harada, and B. Wilcox. To appear in International J. of Robotics Research.

-     Motion Planning for Legged Robots on Varied Terrain. K. Hauser, T. Bretl, J.C. Latombe, K. Harada, and B. Wilcox. To appear in International J. of Robotics Research.

-          K. Hauser, T. Bretl, J.C. Latombe, and B. Wilcox. Motion Planning for a Six-Legged Lunar Robot. Workshop on Algorithmic Foundations of Robotics (WAFR), New-York, NY, July 2006. Published in Algorithmic Foundation of Robotics VII, Springer Tracts in Advanced Robotics, Vol. 47, pp. 301-316, 2008.

-          Motion Planning for Legged Robots on Varied Terrain. K. Hauser, T. Bretl, J.C. Latombe, K. Harada, and B. Wilcox. International J. of Robotics Research, 27(11-12):1325-1349, 2008.

-          K. Hauser and J.C. Latombe. Multi-Modal Motion Planning in Non-Expansive Spaces. Proc 8th Workshop on Algorithmic Foundations of Robotics (WAFR), Guanajuato, Mexico, Dec. 7-9, 2008.

-          K. Hauser and J.C. Latombe. Multi-Modal Motion Planning in Non-Expansive Spaces. International J. of Robotics Research, 2009 (to appear).

-          B. Morisset, R. Bogdan Rusu, A. Sundaresan, K. Hauser, M. Agrawal, J.C. Latombe, and M. Beetz. Leaving Flatland: Toward Real-Time 3D Navigation. Proc. IEEE Int. Conf. on Robotics and Automation, Kobe, Japan, May 12-17, 2009.

-          R. Bogdan Rusu, A. Sundaresan, B. Morisset, K. Hauser, M. Agrawal1, J.C. Latombe, and M. Beetz. Leaving Flatland: Efficient Real-Time 3D Perception and Motion Planning. Int. J. of Field Robotics, 26(10):841-862, 2009.

 

Funding: NSF grant IIS-0412884, DARPA contract #FA8650-04-C-7136.

Any opinions, findings, and conclusions or recommendations expressed in the above material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. 

 

-----

 

Study of protein motion

 

Proteins are the workhorses of all living organisms. They perform many vital functions, such as storage of energy, transmission of signals, transport of molecules, and defense against intruders. They are large molecules made up of hundreds to thousands of atoms. Each protein is a bonded sequence of smaller molecules (picked from a collection of twenty amino-acids) that determines its distinctive kinematics – a long kinematic backbone with small protruding side-chains. In robotics, this backbone would be called a highly redundant serial linkage. Key problems in structural biology include conformation sampling and kinetic analysis. Our research has investigated computational techniques to help solve these problems. In particular, Monte Carlo simulation is a widely used technique to sample protein conformations and simulate folding trajectories. The bottleneck is to maintain the value of the energy function, as this function is made up of many elementary terms and a simulation run consists of many steps. We have developed a new method – called the ChainTree – to speed up Monte Carlo simulation runs without affecting their outcomes. The ChainTree is based on hierarchical distance computation techniques originally developed in robotics and computer graphics (Figure 1). It makes it possible to quickly identify new pairs of interacting atoms during simulation and to retrieve unchanged partial energy sums from the previous simulation step. Along another line, we have developed a new approach, called SRS (for Stochastic Roadmap Simulation) to efficiently generate and analyze huge collections of protein trajectories. This approach is based on probabilistic roadmaps and tools from Markov theory (Figure 2).

 

Figure 1

 

 

 

Figure 2

 

Slides on ChainTree

Slides on Probabilistic Roadmaps

 

Publications:

-          I. Lotan, F. Schwarzer, J.C. Latombe. Efficient Energy Computation for Monte Carlo Simulation of Proteins. 3rd Workshop on Algorithms in Bioinformatics (WABI), Budapest, Hungary, Sept., 2003.

-          I. Lotan, F. Schwarzer, D. Halperin, J.C. Latombe. Algorithm and Data Structures for Efficient Energy Maintenance During Monte Carlo Simulation of Proteins.  J. Computational Biology, 11(5):902-932, 2004.

-          I. Lotan, F. Schwarzer, D. Halperin, and J.C. Latombe. Efficient Maintenance and Self-Collision Testing for Kinematic Chains. Proc. 18th ACM Symp. on Computational Geometry, Barcelona, Spain, June 2002.

-          M.S. Apaydin, D.L. Brutlag, C. Guestrin, D. Hsu. and J.C. Latombe. Stochastic Roadmap Simulation: An Efficient Representation and Algorithm for Analyzing Molecular Motion. Proc. RECOMB'02, Washington D.C., pp. 12-21, 2002.

-          M.S. Apaydin, C. Guestrin, C. Varma, D.L. Brutlag, and J.C. Latombe. Studying Protein-Ligand Interactions with Stochastic Roadmap Simulaton.. Bioinformatics, Vol. 18, Suppl. 2, pp. 18-26, Oct. 2002. (Proc. European Conf. on Computational Biology, ECCB 2002, Saarbrucken, Germany.)

-          M.S. Apaydin, D.L. Brutlag, C. Guestrin, D. Hsu, J.C. Latombe. Stochastic Conformational Roadmaps for Computing Ensemble Properties of Molecular Motion. In Algorithmic Foundations of Robotics V, J.D. Boissonnat, J. Burdick, K. Goldberg, and S. Hutchinson (eds.), Springer Tracts in Advanced Robotics, Springer, pp. 131-147, 2004.  

-          M.S. Apaydin, D.L. Brutlag, C. Guestrin, D. Hsu, J.C. Latombe, and C. Varma. Stochastic Roadmap Simulation: An Efficient Representation and Algorithm for Analyzing Molecular Motion. J. Computational Biology, 10(3-4):257-281, 2003.

-          T.H. Chiang, M.S. Apaydin, D.L. Brutlag, D. Hsu, and J.C. Latombe. Predicting Experimental Quantities in Protein Folding Kinetics using Stochastic Roadmap Simulation. Proc. 10th ACM Annual Int. Conf. on Research in Computational Molecular Biology (RECOMB), Venice, April 2-5, 2006.

-          T.H. Chiang, M.S. Apaydin, D.L. Brutlag, D. Hsu, and J.C. Latombe. Using Stochastic Roadmap Simulation to Predict Experimental Quantities in Protein Folding Kinetics: Folding Rates and Phi-Values.  J. Computational Biology, 14(5): 578-593, June 2007.

 

Funding: NSF ITR grant CCR-0086013, Stanford BioX Initiative grant, KAUST.

Any opinions, findings, and conclusions or recommendations expressed in the above material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

 

-----

 

Modeling flexible protein loops

 

X-ray crystallography is the workhorse of experimental techniques to obtain the 3-D structures of proteins. It requires well-ordered protein crystals to produce diffraction images (Figure 1). Deformable fragments in the protein, especially loops ranging in length from 5 to 20 amino-acids, often lead to disorder in the crystal that makes interpretation of the electron density map difficult (Figure 2). At the same time, such mobile fragments can be critical to a protein’s ability to bind to other molecules and thus achieve its function. In this project we investigate mathematical models for a redundant, closed, protein-like kinematic chain, and study the topology and geometry of its conformational manifold (the “self-motion” manifold). This structure, in particular its connectivity, is currently not well-understood. A further complication is added when collision-avoidance between atoms (self-collision in the fragment, as well as collision with the rest of the protein) is considered. Using these mathematical insights, we expect to design efficient algorithms capable of calculating a probability measure on the self-motion manifold, using not only the electron density map, but also an energetic model of the molecule. One objective is to enable crystallographers to retrieve and study important, dynamic properties of the protein. In a multimodal disordered case, where a fragment achieves s small number of preferred states, our goal is to automatically identify these states, along with their probabilities, and to reconstruct energetically plausible conformational pathways connecting them. This project is a joint effort with Prof. Jim Milgram in the Department of Mathematics and with  Drs. Henry van den Bedem and Asley Deacon in the Joint Center for Structural Genomics (JCSG,) at the Stanford Synchrotron Radiation Laboratory. The ability to infer the most probable conformations of a deformable protein fragment, that is known to be of functional significance, may eventually enhance structure-based drug design capabilities. It will also contribute substantially to the JCSG’s (an NIGMS funded center of the Protein Structure Initiative) mission of developing methods for automating crystallographic analysis.

 

   tm0423

Figure 1

 

        

Figure 2

 

Slides (ppt)

 

Software:

- LoopTK: Toolkit to acquire protein models, manipulate protein fragments, and sample fragment conformations.
- Xpleo: a web server to model missing fragments in X-ray protein structures.
 

 

Publications:

-          I. Lotan, H. van den Bedem, A. Deacon, J.C. Latombe. Computing Protein Structures from Electron Density Maps: The Missing Loop Problem. 6th International Workshop on the Algorithmic Foundations of Robotics (WAFR’04), Utrecht/Zeist, The Netherlands, July 11-13, 2004.

-          H. van den Bedem, I. Lotan, J.C. Latombe and A. M. Deacon. Real-space protein-model completion: an inverse-kinematics approach. Acta Crystallographica, D61:2-13, 2005.

-          Guanfeng Liu, R.J. Milgram, A. Dhanik, and J.C. Latombe. On the Inverse Kinematics of a Fragment of Protein Backbone. Proc. Advances in Robot Kinematics, Ljubljana, Slovenia, June 2006, pp. 201-208.

-          J. Milgram, G. Liu, J.C. Latombe. On the structure of the inverse kinematics map of a fragment of protein backbone. J. of Computational Chemistry, published online: 24 May 2007, 29(1):50-68, January 2008.

-          A. Dhanik, P. Yao, N. Marz, R. Propper, C. Kou, G. Liu, H. van den Bedem, J.C. Latombe. Efficient Algorithms to Explore Conformation Spaces of Flexible Protein Loops. 7th Workshop on Algorithms in Bioinformatics (WABI 2007), Philadelphia, September 2007, pp. 265-276.

-          P. Yao, A. Dhanik, N. Marz, R. Propper, C. Kou, G. Liu, H. van den Bedem, J.C. Latombe, I. Halperin Landsbergz, R.B. Altman. Efficient Algorithms to Explore Conformation Spaces of Flexible Protein Loops.  IEEE/ACM Trans. on Computational Biology and Bioinformatics, 5(4):534-545, Oct.-Dec. 2008.

-          A. Dhanik, H. van den Bedem, A. Deacon, and J.C. Latombe. Modeling Structural Heterogeneity in Proteins from X-Ray Data. Proc 8th Workshop on Algorithmic Foundations of Robotics (WAFR), Guanajuato, Mexico, Dec. 7-9, 2008.

-          H. van den Bedem, A. Dhanik, J.C. Latombe and A.M. Deacon. Modeling Discrete Heterogeneity in X-ray Diffraction Data by Fitting Multi-Conformers. Acta Crystallographica, D65:1107-1117, 2009.

 

Funding: NSF grants CCR-0086013, DMS-0443939, KAUST.

Any opinions, findings, and conclusions or recommendations expressed in the above material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.