MOTIVATION: Biomolecules undergo dynamic transitions among metastable states to carry out their biological functions. Markov State Models (MSMs) effectively capture these metastable states and transitions at a defined temporal scale. However, biomolecular dynamics typically span multiple temporal scales, ranging from fast atomic vibrations to slower conformational changes and folding events. RESULTS: We introduce multiscale Markov State Models (mMSMs), which capture biomolecular dynamics across multiple temporal resolutions simultaneously via a hierarchy of MSMs, and mMSM-explore, an unsupervised algorithm for generating mMSMs through multiscale adaptive sampling with on-the-fly identification of temporally metastable states. We benchmark our method on a toy system with nested energy minima; on alanine dipeptide, first with and then without assuming prior knowledge of its two reaction coordinates; and finally, on a fast-folding 35-residue miniprotein, where we map folding pathways across scales. We demonstrate efficient mapping of energy landscapes, correct representation of multiscale hierarchies and transition states, accurate inference of stationary probabilities and transition kinetics, as well as de novo identification of underlying slow, intermediate, and fast reaction coordinates. mMSMs reveal how dynamic processes at different scales contribute collectively to the functional mechanisms of biomolecular machines. AVAILABILITY AND IMPLEMENTATION: Python code and instructions are available at https://github.com/ravehlab/mMSM.

Sampling-based motion planners are an effective means to generate collision-free motion paths. However, the quality of these motion paths (with respect to quality measures, such as path length, clearance, smoothness, or energy) is often notoriously low, especially in high-dimensional configuration spaces. We introduce a simple algorithm to merge an arbitrary number of input motion paths into a hybrid output path of superior quality, for a broad and general formulation of path quality. Our approach is based on the observation that the quality of certain subpaths within each solution may be higher than the quality of the entire path. A dynamic-programming algorithm, which we recently developed to compare and cluster multiple motion paths, reduces the running time of the merging algorithm significantly. We tested our algorithm in motion-planning problems with up to 12 degrees of freedom (DOFs), where our method is shown to be particularly effective. We show that our algorithm is able to merge a handful of input paths produced by several different motion planners to produce output paths of much higher quality.

Proteins are active, flexible machines that perform a range of different functions. Innovative experimental approaches may now provide limited partial information about conformational changes along motion pathways of proteins. There is therefore a need for computational approaches that can efficiently incorporate prior information into motion prediction schemes. In this paper, we present PathRover, a general setup designed for the integration of prior information into the motion planning algorithm of rapidly exploring random trees (RRT). Each suggested motion pathway comprises a sequence of low-energy clash-free conformations that satisfy an arbitrary number of prior information constraints. These constraints can be derived from experimental data or from expert intuition about the motion. The incorporation of prior information is very straightforward and significantly narrows down the vast search in the typically high-dimensional conformational space, leading to dramatic reduction in running time. To allow the use of state-of-the-art energy functions and conformational sampling, we have integrated this framework into Rosetta, an accurate protocol for diverse types of structural modeling. The suggested framework can serve as an effective complementary tool for molecular dynamics, Normal Mode Analysis, and other prevalent techniques for predicting motion in proteins. We applied our framework to three different model systems. We show that a limited set of experimentally motivated constraints may effectively bias the simulations toward diverse predicates in an outright fashion, from distance constraints to enforcement of loop closure. In particular, our analysis sheds light on mechanisms of protein domain swapping and on the role of different residues in the motion.

A special program for high school has been in operation in Israel whose aim is to expose young students to the field of computing. During their studies the students are required to develop a software project, and thus gain experience in software design. In the past students lacked proper guidance in technologically demanding projects. Here we describe how the work of a student who chose to develop an engine for automatic completion of sentences by the computer was enhanced through cooperation with academia in the innovative "Computer Science, Academia and Industry" educational program. Albeit highly talented, the student lacked necessary formal knowledge in advanced computing technologies. A graduate student who specializes in the field has mentored the high school student throughout design and implementation phase, enabling him to grasp an intuitive understanding of state of the art algorithms, and contribute creative ideas of his own, resulting in an award-winning project of scientific significance.

MOTIVATION: Secondary structures are key descriptors of a protein fold and its topology. In recent years, they facilitated intensive computational tasks for finding structural homologues, fold prediction and protein design. Their popularity stems from an appealing regularity in patterns of geometry and chemistry. However, the definition of secondary structures is of subjective nature. An unsupervised de-novo discovery of these structures would shed light on their nature, and improve the way we use these structures in algorithms of structural bioinformatics. METHODS: We developed a new method for unsupervised partitioning of undirected graphs, based on patterns of small recurring network motifs. Our input was the network of all H-bonds and covalent interactions of protein backbones. This method can be also used for other biological and non-biological networks. RESULTS: In a fully unsupervised manner, and without assuming any explicit prior knowledge, we were able to rediscover the existence of conventional alpha-helices, parallel beta-sheets, anti-parallel sheets and loops, as well as various non-conventional hybrid structures. The relation between connectivity and crystallographic temperature factors establishes the existence of novel secondary structures.