MOTIVATION: Owing to the size and complexity of large multi-component biological assemblies, the most tractable approach to determining their atomic structure is often to fit high-resolution radiographic or nuclear magnetic resonance structures of isolated components into lower resolution electron density maps of the larger assembly obtained using cryo-electron microscopy (cryo-EM). This hybrid approach to structure determination requires that an atomic resolution structure of each component, or a suitable homolog, is available. If neither is available, then the amount of structural information regarding that component is limited by the resolution of the cryo-EM map. However, even if a suitable homolog cannot be identified using sequence analysis, a search for structural homologs should still be performed because structural homology often persists throughout evolution even when sequence homology is undetectable, As macromolecules can often be described as a collection of independently folded domains, one way of searching for structural homologs would be to systematically fit representative domain structures from a protein domain database into the medium/low resolution cryo-EM map and return the best fits. Taken together, the best fitting non-overlapping structures would constitute a 'mosaic' backbone model of the assembly that could aid map interpretation and illuminate biological function. RESULT: Using the computational principles of the Scale-Invariant Feature Transform (SIFT), we have developed FOLD-EM-a computational tool that can identify folded macromolecular domains in medium to low resolution (4-15 Å) electron density maps and return a model of the constituent polypeptides in a fully automated fashion. As a by-product, FOLD-EM can also do flexible multi-domain fitting that may provide insight into conformational changes that occur in macromolecular assemblies.

UNLABELLED: We present a new, first-of-its-kind, fully automated computational tool MOTIF-EM for identifying regions or domains or motifs in cryoEM maps of large macromolecular assemblies (such as chaperonins, viruses, etc.) that remain conformationally conserved. As a by-product, regions in structures that are not conserved are revealed: this can indicate local molecular flexibility related to biological activity. MOTIF-EM takes cryoEM volumetric maps as inputs. The technique used by MOTIF-EM to detect conserved sub-structures is inspired by a recent breakthrough in 2D object recognition. The technique works by constructing rotationally invariant, low-dimensional representations of local regions in the input cryoEM maps. Correspondences are established between the reduced representations (by comparing them using a simple metric) across the input maps. The correspondences are clustered using hash tables and graph theory is used to retrieve conserved structural domains or motifs. MOTIF-EM has been used to extract conserved domains occurring in large macromolecular assembly maps, including as those of viruses P22 and epsilon 15, Ribosome 70S, GroEL, that remain structurally conserved in different functional states. Our method can also been used to build atomic models for some maps. We also used MOTIF-EM to identify the conserved folds shared among dsDNA bacteriophages HK97, Epsilon 15, and ô29, though they have low-sequence similarity. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Research on robotic manipulation has mainly focused on manipulating rigid objects so far. However, many important application domains require manipulating deformable objects, especially deformable linear objects (DLOs), such as ropes, cables, and sutures. Such objects are far more challenging to handle, as they can exhibit a much greater diversity of behaviors, and their manipulation almost inevitably requires two robotic arms, or more, performing well-coordinated motions. This paper describes a new motion planner for manipulating DLOs and tying knots (both self-knots and knots around simple static objects) using two cooperating robotic arms. This planner blends new ideas with preexisting concepts and techniques from knot theory, robot motion planning, and computational modeling. Unlike in traditional motion planning problems, the goal to be achieved by the planner is a topological state of the world, rather than a geometric one. To search for a manipulation path, the planner constructs a topologically biased probabilistic roadmap in the configuration space of the DLO. During roadmap construction, it uses inverse kinematics to determine the successive robot configurations implied by the DLO configurations and tests their feasibility. Also, inspired by the real life, the planner uses static ldquoneedlesrdquo (by analogy to the needles used in knitting) for maintaining the stability of the DLO during manipulation and to make the resulting manipulation plan robust to imperfections in the physical model of the DLO. The implemented planner has been tested both in graphic simulation and on a dual-PUMA-560 hardware platform to achieve various knots, like bowline, neck-tie, bow (shoe-lace), and stun-sail.

This paper presents a connection strategy for PRM-based motion planning in high-dimensional configuration spaces. The connection strategy identifies components of motion during the roadmap construction and plans the roadmap edges on a sequence of configuration slices approximating the configuration spaces of the components. The goal of the approach is to extend the dimensionality of the problems PRM planners can solve, and the strategy it deploys is dimensional subdivision. We report experimental results on serpentine robots with up to 150 degrees-of-freedom and multi-robot systems with up to 144 degrees-of-freedom. The test problems are beyond the capability of a representative state-of-the-art PRM based planner, and the approach presented in this paper enables the use of motion planning methods in solving new high-dimensional problems

Research on robotic manipulation has mainly focused on manipulating rigid objects so far. However, many important application domains require manipulating deformable objects, especially deformable linear objects (DLOs), such as ropes, cables, and sutures. Such objects are far more challenging to handle, as they can exhibit a much greater diversity of behaviors. This paper describes a new motion planner for manipulating DLOs and tying knots (self-knots and knots around simple static objects) using cooperating robot arms. The planner constructs a topologically-biased probabilistic roadmap in the DLO's configuration space. Unlike in traditional motion planning problems, the goal is a topological state of the world, rather than a geometric one. The implemented planner was tested in simulation to achieve various knots like bowline, neck-tie, bow (shoe-lace), and stun-sail

In a recent study, it was shown that high failure rates in decoupled multi-robot motion planning makes the decoupled planning approach an unsuitable choice, in comparison to the centralized approach, in many practical instances. Motivated by this study, we devised a new multi-robot planning strategy in which we partially merge the two stages of the basic decoupled planning approach. Our experimental results show that this new strategy significantly improves upon the reliability of the decoupled planning approach. Overall in our tests, the new strategy outperforms both the centralized and decoupled planning approach, indicating that in practice it can be a better choice, than both the centralized and decoupled approach, for solving multi-robot planning problems

The efficiency of probabilistic roadmap (PRM) planners drops dramatically in spaces with narrow passages. This paper presents a new method - small-step retraction - that helps PRM planners find paths through such passages. The method consists of slightly fattening the robot's free space, constructing a roadmap in the fattened free space, and repairing colliding portions of this roadmap by retracting them out of collision. The fattened free space is not explicitly computed. Instead, the 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 used. The "optimist" strategy waits until a complete path has been found in fattened free space before repairing it. The "pessimist" strategy repairs the roadmap as it is being built. The former is faster, but the latter is more reliable. A simple combination yields an integrated planner that is both fast and reliable.

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 there exist effective methods for static collision detection, dynamic checking still lacks methods that are both reliable and efficient. A common approach is to sample paths at some fixed, prespecified resolution and statically test each sampled configuration. But this approach is not guaranteed to detect collision whenever one occurs, and trying to increase its reliability by refining the sampling resolution along the entire path results in slow checking. This paper introduces a new method for testing path segments in c-space or collections of such segments, that is both reliable and efficient. This method locally adjusts the sampling resolution by comparing lower bounds on distances between objects in relative motion with upper bounds on lengths of curves traced by points of these moving objects. Several additional techniques and heuristics increase the checker's efficiency in scenarios with many moving objects (e.g., articulated arms and/or multiple robots) and high geometric complexity. The new method is general, but particularly well suited for use in probabilistic roadmap (PRM) planners, where it is critical to determine as quickly as possible whether given path segments collide, or not. Extensive tests, in particular on randomly generated path segments and on multisegment 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.

This paper considers the following multi-goal motion planning problem: a robot arm must reach several goal configurations in some sequence, but this sequence is not given. Instead, the robot's planner must compute an optimal or near-optimal path through the goals. This problem occurs, for instance, in spot-welding, inspection, and measurement tasks. It combines two computationally hard sub-problems: the shortest-path and traveling-salesman problems. This paper describes a greedy algorithm that operates under the assumption that the number of goals is relatively small (a few dozen at most) and the computational cost of finding a good path between two goals dominates that of finding a good tour in a graph with edges of given costs. Although the algorithm computes a quadratic number of goal-to-goal paths in the worst case, it is much faster in practice.