Probabilistic Adaptive Tree-based Search

We have proposed a novel robotics-inspired method to enhance the sampling of native-like protein conformations when employing online amino-acid sequence information for the protein at hand. The method is named FeLTr for Fragment Monte CarLo Tree Exploration. The novelty of FeLTr lies in a two-layered exploration of the conformational space that allows to rapidly obtain geometrically-distinct low energy conformations at a coarse-grained level of detail.

FeLTr grows a tree in conformational space reconciling two goals: (i) guiding the tree towards lower energies and (ii) not oversampling geometrically-similar conformations. Discretizations of the energy surface and a low-dimensional projection space are employed to select more often for expansion low-energy conformations in under-explored regions of the conformational space. The tree is expanded with low-energy conformations through a Metropolis Monte Carlo framework that uses a move set of physical fragment configurations.

Z-axis illustrates the 1d grid of energy values. The axis is color-coded in a red-to-blue scheme to denote energy levels that reach lower values with the native state. The grid on the xy-plane discretizes the projection of the conformational space onto a few conformational coordinates. The illustration shows two coordinates for visualization purposes. Three coordinates are employed by FeLTr to describe projected conformations.

Testing on sequences of seven small-to-medium structurally-diverse proteins shows that FeLTr rapidly samples native-like conformations in a few hours on a single CPU. The figures below showcase lowest-energy conformations obtained for one of the tested sequences and juxtapose energies of computed conformations versus their lRMSD from the known native structure of this sequence. Analysis tested sequences shows that computed conformations represent diverse low-energy regions of the energy landscape and are therefore good candidates for further detailed energetic refinements by larger studies in protein engineering and design.


Left: Computed low-energy conformations of the engrailed homeodomain are clustered and representatives are shown superimposed in opaque red over the native structure drawn in transparent blue. Right: Energies of conformations are plotted vs. their lRMSDs from the native structure in red for FeLTr-computed conformations and light purple for conformations computed through a simple Monte Carlo approach employing the same fragment assembly and energy function.

This work appears in: 1) Amarda Shehu and Brian Olson "Guiding the Search for Native-like Protein Conformations with an Ab-initio Tree-based Exploration" Intl J of Robot Res 2010, 29(8):1106-1127; and 2) Amarda Shehu "An Ab-initio Tree-based Exploration to Enhance Sampling of Low-energy Protein Conformations" Robotics Science and Systems (RSS), Seattle, USA, 2009, pg. 241-248.

On this Project:

  • Brian Olson

    Kevin Molloy

    Amarda Shehu

This material is based upon work supported by the National Science Foundation under Grant No. 1016995 and IIS CAREER Award No. 1144106. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.