Structural Bioinformatics Library
Template C++ / Python API for developping structural bioinformatics applications.

Authors: F. Cazals and T. Dreyfus and C. Roth
This package provides methods to build transition graphs, i.e. graphs connecting local minima of an energy landscape, across index one saddles.
This package provides various methods dealing with the construction of transition graphs (TG), i.e. graphs connecting local minima and index one saddles (Fig. figtgbuilderhimmelblaubasinsTG and definition deftransitiongraph). The TGs built are meant to be used as input for the analysis presented in the following packages:
In the sequel, we consider a conformational ensemble . We may also assume that the local minimum associated with each conformation , that is obtained by following the negative gradient of the potential energy, is known. Following classical terminology, this minimization process is called quenching. This set is denoted . We assume that the (potential) energy of each conformation is known.
Methods to build TG are provided in three settings:
From a database of stationary points (local minima and index one saddles).
From a conformational ensemble
From a dense sampling .
Himmelblau: (Compressed) Transition graph (A) The landscape of Himmelblau, decomposed into the catchment basins of the four local minima (B) The transition graph, with one node for each critical (i.e., stationary) point (C) The compressed transition graph, where the information associated with saddles is stored in the edges joining local minima. 
When a database of connected critical points (local minima and index one saddles) is available, building a transition graph is trivial.
We note that compressed transition graphs (rather than transition graphs) are built (definition defcompressedtg), to minimize the memory footprint.
The input consists on five files:
A calculation is launched as follows:
> sbltgbuilderlrmsd.exe fromDB discardloops samplestomins data/bln69_databasetransitions.txt pointsfile data/bln69_database_minima_conformations.txt energies data/bln69_database_minima_energies.txt pointsfile data/bln69_database_transitions_conformations.txt energies data/bln69_database_transitions_energies.txt directory results verbose outputprefix log
File Name  Description 
Transitions file  Transitions as pairs of minima indices 
BLN69 conformations file  Conformations of sampled transition states of BLN69 
Energies file  Energies of sampled transition states of BLN69 
BLN69 conformations file  Conformations of sampled local minima of BLN69 
Energies file  Energies of sampled local minima of BLN69 
Preview  File Name  Description 
General: log file  
Log text file  High level information on the run  
Moduel TG builder from DB  
Transition graph XML archive  Output transition graph serializedinto an XML archive 
Consider now the case where a plain sampling has been obtained, together with the local minimum associated with each sample (obtained by quenching) [107], [89] . Let us also assume that the transitions themselves have not been computed. In this case, one can locate pairs of conformations, say satisfying two conditions (see Fig. figmorsestableunstablemanifoldsalgoflowbackward):
the conformations and are neighbor – their distance (for some suitable distance metric) is less than a user defined threshold;
Such a pairs is said to witness a bifurcation. Note that the same two local minima may be witnessed by multiple pairs. For small enough value of the distance threshold, the sample with lowest energy amidst such pairs witnesses the adjacency of the catchment basins of and . An algorithm to detect such pairs is sketched below, see section Algorithms and Methods.
The input consists on five files:
A calculation is launched as follows:
> sbltgbuilderlrmsd.exe fromsampling pointsfile data/bln69_sampling_samples_conformations.txt energies data/bln69_sampling_samples_energies.txt samplestomins data/bln69_sampling_samples_to_quench.txt pointsfile data/bln69_sampling_quenched_conformations.txt energies data/bln69_sampling_quenched_energies.txt directory results verbose outputprefix log
File Name  Description 
BLN69 conformations file  A small sampling of BLN69 
BLN69 energies file  Energies of conformations in the sampling 
BLN69 conformations file  Quenched conformations from the sampling 
BLN69 energies file  Energies of the quenched conformations 
Indices pairs file  List of pairs (conformation, quenched conformation) Input files for the run described in section Input: Specifications and File Types . 
Preview  File Name  Description 
General: log file and weighted TG  
Log file  Log file containing high level information on the run  
Transition graph XML archive  Transition graph of input sampling serialized into an XML archive  
Module MTB analysis: minima weights in TG  
Morse Smale Witten chain complex xml file  Morse Smale Witten chain complex serialized using Boost into an XML archive  
Stable manifold partition xml file  XML archive listing the samples repartition by persistent basin  
Disconnectivity forest image file  Disconnectivity forest drawn in eps file formnat  
Sorted basins plain text file  List of all basins sorted by persistence  
Persistence diagram plot script  Gnuplot script for the persistence diagram  
Persistences plain text file  List of all finite persistences  
Persistence histogram plot script  R script for the persistence histogram  
Persistence histogram image  Persistence histogram drawn by R in pdf file format 
Consider finally the cases where only samples are known – that is the local minimum associated with a conformation is unknown. Also assume that the neighborhood of has been densely sampled, and that has been connected to a set of nearest neighbors, using a nearest neighbor graph (NNG, definition defnng). We estimate the gradient of the potential energy at using its neighbors in the NNG. More precisely, we estimate the gradient using the neighbor of yielding the maximum slope. Starting from and iteratively following this estimated gradient eventually leads to a sample having all its neighbors above it. One can use this sample as a substitute for .
The input consists on two files:
A calculation is launched as follows:
> sbltgbuildereuclid.exe fromsampling pointsfile data/himmelbleau_sampling.txt energies data/himmelbleau_heights.txt persistencethreshold 10 directory results verbose outputprefix log
File Name  Description 
2D points conformations file  2D points on a grid for sampling Himmelbleau function 
Energies file  Height of points in the Himmelbleau sampling 
Preview  File Name  Description 
General: log file  
Transition graph XML archive  Transition graph of input sampling serialized into an XML archive  
Log file  Log file containing high level information on the run  
Module NNG builder  
NNG xml file  Nearest neighbor graph serialized using Boost into an XML archive  
Module MTB abalysis: minima weights in TG  
Morse Smale Witten chain complex xml file  Morse Smale Witten chain complex serialized using Boost into an XML archive  
Stable manifold partition xml file  XML archive listing the samples repartition by persistent basin  
Disconnectivity forest image file  Disconnectivity forest drawn in eps file formnat  
Sorted basins plain text file  List of all basins sorted by persistence  
Persistence diagram plot script  Gnuplot script for the persistence diagram  
Persistence diagram image  Persistence diagram drawn by gnuplot in pdf file format  
Persistences plain text file  List of all finite persistences  
Persistence histogram plot script  R script for the persistence histogram  
Persistence histogram image  Persistence histogram drawn by R in pdf file format 
In the following, we sketch the construction of the TG from a collection of points and associated local minima. The reader is also referred to the package Morse_theory_based_analyzer for further details (see also the MTBA module in the workflow, Fig. figtgbworkflow).
Assume that one is given a conformational ensemble together with the corresponding quenched points . The algorithm consists of two main steps (Fig. figmorsestableunstablemanifoldsalgoflowbackward):
Step 1: Nearest neighbor graph. We build a NNG on the conformations – see package Nearest_neighbors_graph_builder, and in addition endow each sample with an edge to . Note that this connection directly links each sample to its local minimum.
Identifying the connexion between the basins of two local minima by quenching two samples and Sample is quenched to while is quenched to . The samples and sit across the (white) ridge separating the basins of their respective 
The programs of Transition_graph_of_energy_landscape_builders described above are based upon generic C++ classes, so that additional versions can easily be developed.
In order to derive other versions, there are two important ingredients, that are the workflow class, and its traits class.
T_Transition_graph_builder_from_sampled_energy_landscape_traits:
This class defines the main types used in the modules of the workflow. It is templated by the classes of the concepts required by these modules. This design makes it possible to use the same workflow within different(biophysical) contexts to make new programs. To use the workflow T_Transition_graph_builder_from_sampled_energy_landscape_workflow , one needs to define:
GeometricKernel  Traits class defining various geometric objects, in particular the number type used for representing the coordinates of a conformation, and the base representation of a point in dimension D – see class CGAL::Cartesian_d from the CGAL library 
DistanceFunction  Functor returning the distance between two conformations. It has to define the types Point (alias for a Conformation) and FT (alias for the returned number type) 
TDensityFunction  Functor returning the density of a conformation represented by a vertex in a nearest neighbor graph. The template parameter isthe type of the nearest neighbor graph. 
T_Transition_graph_builder_from_sampled_energy_landscape_workflow: