Search

International audience; This paper addresses the simultaneous design and path planning problem, in which features associated to the bodies of a mobile system have to be selected to find the best design that optimizes its motion between two given configurations. Solving individual path planning problems for all possible designs and selecting the best result would be a straightforward approach for very simple cases. We propose a more efficient approach that combines discrete (design) and continuous (path) optimization in a single stage. It builds on an extension of a sampling-based algorithm, which simultaneously explores the configuration-space costmap of all possible designs aiming to find the best path-design pair. The algorithm filters out unsuitable designs during the path search, which breaks down the combinatorial explosion. Illustrative results are presented for relatively simple (academic) examples. While our work is currently motivated by problems in computational biology, several applications in robotics can also be envisioned.

Motivation Loop portions in proteins are involved in many molecular interaction processes. They often exhibit a high degree of flexibility, which can be essential for their function. However, molecular modeling approaches usually represent loops using a single conformation. Although this conformation may correspond to a (meta-)stable state, it does not always provide a realistic representation. Results In this paper, we propose a method to exhaustively sample the conformational space of protein loops. It exploits structural information encoded in a large library of three-residue fragments, and enforces loop-closure using a closed-form inverse kinematics solver. A novel reinforcement-learning-based approach is applied to accelerate sampling while preserving diversity. The performance of our method is showcased on benchmark datasets involving 9-, 12- and 15-residue loops. In addition, more detailed results presented for streptavidin illustrate the ability of the method to exhaustively sample the conformational space of loops presenting several meta-stable conformations. Availability and implementation We are developing a software package called MoMA (for Molecular Motion Algorithms), which includes modeling tools and algorithms to sample conformations and transition paths of biomolecules, including the application described in this work. The binaries can be provided upon request and a web application will also be implemented in the short future. Supplementary information Supplementary data are available at Bioinformatics online.

Deep learning and neural networks are at the frontier of machine learning and artificial intelligence. The applications of these methods are vast and include many applications within bioscience. Most recently, Google's Deep Mind project stunned the protein structure prediction community with their performance in the last critical assessment of structural prediction (CASP) competition. The objective of this tutorial is three-fold. First, the tutorial will introduce students and researchers that attend to the Keras deep learning framework. This library will be paired with Google's TensorFlow backend and examples will be shown utilizing both the Python and R programming languages. Second, the tutorial will allow attendees to learn the basic concepts of convolutional neural networks, recurrent neural networks, and transfer learning. Hands-on examples and sample code will be provided for each of these separate topics using classic example problems (such as image recognition/classification and text-mining/sentiment analysis). Third, an in class competition to identify antimicrobial peptides will employ multiple concepts collectively. An accompanying web server will allow attendees to upload and evaluate their models on the fly and further see how it ranks and compares to others.

SUMMARYEvidence is emerging that the role of protein structure in disease needs to be rethought. Sequence mutations in proteins are often found to affect the rate at which a protein switches between structures. Modeling structural transitions in wildtype and variant proteins is central to understanding the molecular basis of disease. This paper investigates an efficient algorithmic realization of the stochastic roadmap simulation framework to model structural transitions in wildtype and variants of proteins implicated in human disorders. Our results indicate that the algorithm is able to extract useful information on the impact of mutations on protein structure and function.

International audience; The study of the conformational energy landscape of a molecule is essential for the understanding of its physicochemical properties. This requires the exploration of a continuous, high-dimensional space to identify the most probable conformations and the transition paths between them. The problem is computationally difficult, in particular for highly-flexible biomolecules such as Intrinsically Disordered Proteins (IDPs). In recent years, a robotics-inspired algorithm called Transition-based Rapidly-exploring Random Tree (TRRT) has been proposed to solve this problem, and has been shown to provide good results with small and middle-sized biomolecules. Aiming to treat larger systems, we propose a hybrid strategy for the efficient parallelization of a multi-tree variant of TRRT, called Multi-TRRT, enabling an efficient execution in (possibly large) computer clusters. The parallel algorithm uses OpenMP multi-threading for computation inside each multi-core processor and MPI to perform the communication between processors. Results show a near-linear speedup for a wide range of cluster configurations. Although the paper mainly deals with the application of the proposed parallel algorithm to the investigation of biomolecules, the explanations concerning the methods are general, aiming to inspire future work on the parallelization of related algorithms.

With biomolecular structure recognized as central to understanding mechanisms in the cell, dry laboratories have spent significant efforts on modeling and analyzing structure and dynamics. While significant advances have been made, particularly in the design of sophisticated energetic models and molecular representations, such efforts are experiencing diminishing returns. One of the culprits is the low exploration capability of Molecular Dynamics- and Monte Carlo-based exploration algorithms. The impasse has attracted AI researchers bringing complementary tools, such as randomized search and stochastic optimization. The tutorial introduces students and researchers to stochastic optimization treatments and methodologies for understanding and elucidating the role of biomolecular structure and dynamics in function. In addition, the tutorial allows attendees to connect between structures, motions, and function via analysis tools that take an energy landscape view of the relationship between biomolecular structure, dynamics, and function. The presentation is enhanced via open-source software that permit hands-on exercises, which benefits both students and senior researchers keen to make their own contributions.

The rapid accumulation of protein structures presents a unique set of challenges and opportunities in the analysis, comparison, modeling, and prediction of macromolecular structures and their interactions. This workshop brought together researchers with expertise in bioinformatics, structural computational biology, machine learning, optimization, and high performance computing, to disseminate new results, and discuss techniques and research problems.

International audience; This paper addresses the simultaneous design and path planning problem, in which features associated to the bodies of a mobile system have to be selected to find the best design that optimizes its motion between two given configurations. Solving individual path planning problems for all possible designs and selecting the best result would be a straightforward approach for very simple cases. We propose a more efficient approach that combines discrete (design) and continuous (path) optimization in a single stage. It builds on an extension of a sampling-based algorithm, which simultaneously explores the configuration-space costmap of all possible designs aiming to find the best path-design pair. The algorithm filters out unsuitable designs during the path search, which breaks down the combinatorial explosion. Illustrative results are presented for relatively simple (academic) robotic examples, showing that even in these simple cases, the computational cost can be reduced by two orders of magnitude with respect to the na¨ıvena¨ıve approach. A preliminary application to challenging problems in computational biology related to protein design is also discussed at the end of the paper.

The rapid accumulation of macromolecular structures presents a unique set of challenges and opportunities in the analysis, comparison, modeling, and prediction of macromolecular structures and interactions. This workshop aims to bring together researchers with expertise in bioinformatics, computational biology, structural biology, data mining, optimization and high performance computing to discuss new results, techniques, and research problems in computational structural bioinformatics.

With biomolecular structure recognized as central to understanding mechanisms in the cell, computational chemists and biophysicists have spent significant efforts on modeling structure and dynamics. While significant advances have been made, particularly in the design of sophisticated energetic models and molecular representations, such efforts are experiencing diminishing returns. One of the culprits is low exploration capability. The impasse has attracted AI researchers to offer adaptations of robot motion planning algorithms for modeling biomolecular structures and motions. This tutorial introduces students and researchers to robotics-inspired treatments and methodologies for understanding and elucidating the role of structure and dynamics in the function of biomolecules. The presentation is enhanced via an open-source software developed in the Shehu Computational Biology laboratory. The software allows researchers to integrate themselves in a new research domain and drive further research via plug-and-play capabilities. The hands-on approach in the the tutorial benefits both students and senior researchers keen to make contributions in computational structural biology.

Adequate sampling of the conformational space is a central challenge in ab initio protein structure prediction. In the absence of a template structure, a conformational search procedure guided by an energy function explores the conformational space, gathering an ensemble of low-energy decoy conformations. If the sampling is inadequate, the native structure may be missed altogether. Even if reproduced, a subsequent stage that selects a subset of decoys for further structural detail and energetic refinement may discard near-native decoys if they are high energy or insufficiently represented in the ensemble. Sampling should produce a decoy ensemble that facilitates the subsequent selection of near-native decoys. In this paper, we investigate a robotics-inspired framework that allows directly measuring the role of energy in guiding sampling. Testing demonstrates that a soft energy bias steers sampling toward a diverse decoy ensemble less prone to exploiting energetic artifacts and thus more likely to facilitate retainment of near-native conformations by selection techniques. We employ two different energy functions, the associative memory Hamiltonian with water and Rosetta. Results show that enhanced sampling provides a rigorous testing of energy functions and exposes different deficiencies in them, thus promising to guide development of more accurate representations and energy functions.

Precious information on protein function can be extracted from a detailed characterization of protein equilibrium dynamics. This remains elusive in wet and dry laboratories, as function-modulating transitions of a protein between functionally-relevant, thermodynamically-stable and meta-stable structural states often span disparate time scales. In this paper we propose a novel, robotics-inspired algorithm that circumvents time-scale challenges by drawing analogies between protein motion and robot motion. The algorithm adapts the popular roadmap-based framework in robot motion computation to handle the more complex protein conformation space and its underlying rugged energy surface. Given known structures representing stable and meta-stable states of a protein, the algorithm yields a time- and energy-prioritized list of transition paths between the structures, with each path represented as a series of conformations. The algorithm balances computational resources between a global search aimed at obtaining a global view of the network of protein conformations and their connectivity and a detailed local search focused on realizing such connections with physically-realistic models. Promising results are presented on a variety of proteins that demonstrate the general utility of the algorithm and its capability to improve the state of the art without employing system-specific insight.

Rapid advances in high-throughout genome sequencing technologies have resulted in millions of protein-encoding gene sequences with no functional characterization. Automated protein function annotation or prediction is a prime problem for computational methods to tackle in the post-genomic era of big molecular data. While recent community-driven experiments demonstrate that the accuracy of function prediction methods has significantly improved, challenges remain. The latter are related to the different sources of data exploited to predict function, as well as different choices in representing and integrating heterogeneous data. Current methods predict function from a protein’s sequence, often in the context of evolutionary relationships, from a protein’s three-dimensional structure or specific patterns in the structure, from neighbors in a protein–protein interaction network, from microarray data, or a combination of these different types of data. Here we review these methods and the state of protein function prediction, emphasizing recent algorithmic developments, remaining challenges, and prospects for future research.

International audience; Obtaining accurate representations of energy landscapes of biomolecules such as proteins and peptides is central to the study of their physicochemical properties and biological functions. Peptides are particularly interesting, as they exploit structural flexibility to modulate their biological function. Despite their small size, peptide modeling remains challenging due to the complexity of the energy landscape of such highly-flexible dynamic systems. Currently, only stochastic sampling-based methods can efficiently explore the conformational space of a peptide. In this paper, we suggest to combine two such methods to obtain a full characterization of energy landscapes of small yet flexible peptides. First, we propose a simplified version of the classical Basin Hopping algorithm to reveal low-energy regions in the landscape, and thus to identify the corresponding meta-stable structural states of a peptide. Then, we present several variants of a robotics-inspired algorithm, the Transition-based Rapidly-exploring Random Tree, to quickly determine transition path ensembles, as well as transition probabilities between meta-stable states. We demonstrate this combined approach on met-enkephalin.

A central challenge in ab-initio structure prediction is the attainment of a large diverse ensemble of decoy conformations at low resolution so that subsequent refinement of selected decoys at higher resolution can identify the native structure among them [1]. The focus on the size and diversity is due to the weak discriminatory power of potential energy. Even state-of-the-art coarse grained energy functions are often weakly funneled, i.e., incapable of energetically distinguishing structurally dissimilar conformations [2]. While obtaining low-energy decoys increases the chance that a percentage of them are near-native, lowest energies are not necessarily associated with the native structure. Instead, the most effective selection techniques use redundancy, often in the form of the most populous conformational clusters identified, to identify the native structure. While redundancy is useful in this context, it is also a reason for the computational inefficiency of many conformational search algorithms.

Understanding and elucidating the conformational rearrangements that protein systems undergo to transition between different functional states is an important but challenging problem in computational biology [1]. Wet-lab techniques allow resolving representative structures of a protein's functional states but rarely provide the microscopic picture of transition trajectories connecting these states. While computational methods based on Molecular Dynamics in principle offer to incorporate dynamics and obtain transition trajectories, the computational complexity of the problem results in impractical running times. Foregoing dynamics allows computing conformational paths in an efficient manner. MD-based techniques can be employed to map conformational paths to actual transition trajectories [1].

Since its introduction, the basin hopping (BH) framework has proven useful for hard nonlinear optimization problems with multiple variables and modalities. Applications span a wide range, from packing problems in geometry to characterization of molecular states in statistical physics. BH is seeing a reemergence in computational structural biology due to its ability to obtain a coarse-grained representation of the protein energy surface in terms of local minima. In this paper, we show that the BH framework is general and versatile, allowing to address problems related to the characterization of protein structure, assembly, and motion due to its fundamental ability to sample minima in a high-dimensional variable space. We show how specific implementations of the main components in BH yield algorithmic realizations that attain state-of-the-art results in the context of ab initio protein structure prediction and rigid protein-protein docking. We also show that BH can map intermediate minima related with motions connecting diverse stable functionally relevant states in a protein molecule, thus serving as a first step towards the characterization of transition trajectories connecting these states.

A protein molecule assumes specific conformations under native conditions to fit and interact with other molecules. Due to the role that three-dimensional structure plays in protein function, significant efforts are devoted to elucidating native conformations. Many search algorithms are proposed to navigate the high-dimensional protein conformational space and its underlying energy surface in search of low-energy conformations that comprise the native state. In this work, we identify two strategies to enhance the sampling of native conformations. We show that employing an enhanced fragment library with greater structural diversity to assemble low-energy conformations allows sampling more native conformations. To efficiently handle the ensuing vast conformational space, only a representative subset of the sampled conformations are maintained and employed to further guide the search for native conformations. Our results show that these two strategies greatly enhance the sampling of the conformational space near the native state.

The three-dimensional structure of a protein is a key determinant of its biological function. Given the cost and time required to acquire this structure through experimental means, computational models are necessary to complement wet-lab efforts. Many computational techniques exist for navigating the high-dimensional protein conformational search space, which is explored for low-energy conformations that comprise a protein's native states. This work proposes two strategies to enhance the sampling of conformations near the native state. An enhanced fragment library with greater structural diversity is used to expand the search space in the context of fragment-based assembly. To manage the increased complexity of the search space, only a representative subset of the sampled conformations is retained to further guide the search towards the native state. Our results make the case that these two strategies greatly enhance the sampling of the conformational space near the native state. A detailed comparative analysis shows that our approach performs as well as state-of-the-art ab initio structure prediction protocols.