1887
banner image
No data available.
Please log in to see this content.
You have no subscription access to this content.
No metrics data to plot.
The attempt to load metrics for this article has failed.
The attempt to plot a graph for these metrics has failed.
Analyzing milestoning networks for molecular kinetics: Definitions, algorithms, and examples
Rent:
Rent this article for
USD
10.1063/1.4827495
/content/aip/journal/jcp/139/17/10.1063/1.4827495
http://aip.metastore.ingenta.com/content/aip/journal/jcp/139/17/10.1063/1.4827495

Figures

Image of FIG. 1.
FIG. 1.

A schematic representation of mapping continuous space and trajectories to a network. We have five cells in phase space denoted by , , , , . Each cell can be mapped to a network vertex and the edges would be between vertices, e.g., (α, β) and (β, γ). Sometimes the cells are represented by specific conformations (anchors) that are illustrated in the figure by the blue ellipses. In an alternate network representation, the vertices can be interfaces or milestones denoted on the figure by dashed red lines, which indicate the boundary between domains. There are six milestones in the above figure, . Continuous trajectories are mapped to the network either by their location in phase space or by the last milestone that they have passed (color coded curves in the figure). On the right side of the figure we show network representations. The top figure is an anchor-based network and the lower figure is based on the milestones.

Image of FIG. 2.
FIG. 2.

Conversion of a flux-space path with milestones as vertices to a state-space path with the corresponding anchors as vertices. The table in the figure shows the mapping from milestone index to anchor index. The weight on each milestone edge contributes to weights on two anchor edges. Each anchor edge in the middle gets a contribution from two milestone edges.

Image of FIG. 3.
FIG. 3.

(a) An example graph with multiple paths between vertices of interest, A and D. (b) Maximum weight paths (MWP) between A and D shown in green. (c) Global maximum weight path (GMWP) between A and D shown in red.

Image of FIG. 4.
FIG. 4.

Example graph demonstrating Dijkstra's single-source shortest path algorithm. This is a snapshot during the optimization process and not the final result. We are calculating the shortest path lengths from A to all other vertices. Path lengths marked by are current estimates of the shortest path length from vertex A to a given vertex. Vertices that have already been explored by the algorithm are marked with ✓ and current vertex being examined is marked with *.

Image of FIG. 5.
FIG. 5.

Example graph demonstrating single-source maximum weight algorithm. This is a snapshot during the optimization process and not the final result. See text for more details. We are calculating the maximum weights from A to all other vertices. Weights marked by are current estimates of the maximum weight from vertex A to a given vertex. Vertices that have already been explored by the algorithm are marked with ✓ and current vertex being examined is marked with *.

Image of FIG. 6.
FIG. 6.

An example graph showing the GMWP between vertices A and G in red.

Image of FIG. 7.
FIG. 7.

Visualization of average networks for helix unfolding under a load level 30 pN in (a) state-space, with 14 anchors (vertices). (b) flux-space with 125 milestones (vertices). The graphs are to illustrate the complexity of analysis and were prepared with the Pajek program. 43

Image of FIG. 8.
FIG. 8.

Global maximum weight paths using three different graph representations for helix unfolding under 0pN stress. Bottleneck edges (EMW) are in red. Note that the second path, represented in anchor space, has a loop to from to . Directional Milestoning representation allows for such choices since entry milestones (interfaces) can be different for the same state. The source of the difference between the state-based and flux-based graph is the finer (more detailed) description of the system in the flux-based graph. (a) OpN, Path from state-space graph based on flux-based edge weights; (b) OpN, Path from flux-space graph based on flux-based edge wights; (c) OpN, Path from flux-space graph based on rate coefficients.

Image of FIG. 9.
FIG. 9.

Global maximum weight paths using three different graph representations for helix unfolding under 30 pN stress. Bottleneck edges (EMW) are in red. (a) 30pN, Path from state-space graph based on flux-based edge weights; (b) 30pN, Path from flux-space graph based on flux-based edge weights; (c) 30pN, Path from flux-space graph based on rate coefficients.

Image of FIG. 10.
FIG. 10.

Global maximum weight paths using three different graph representations for helix unfolding under 70 pN stress. Bottleneck edges (EMW) are in red. (a) 70pN, Path from state-space graph based on flux-based edge weights; (b) 70pN, Path from flux-space graph based on flux-based edge weights; (c) 70pN, Path from flux-space graph based on rate coefficients.

Image of FIG. 11.
FIG. 11.

Global maximum weight paths using three different graph representations for membrane permeation of DOPC. The path descriptions are as follows: Path A: Path obtained from the state-space graph with flux-based weights. Path B: obtained from the flux-space graph with flux-based weights. Path C: obtained from the flux-space graph weighted by local rate coefficients.

Image of FIG. 12.
FIG. 12.

Visualization of proximity of paths shown in Figure 11 . All the nodes visited by the three paths are collected into a single network. The position of the nodes in the network are optimized using force model proposed in Gephi. 46 Connected nodes attract each other, while nodes that are far repel each other. The larger cyan nodes are the initial and final milestones. The path descriptions are as follows: Path A (green): Path obtained from the state-space graph with flux-based weights. Path B (red): obtained from the flux-space graph with flux-based weights. Path C (yellow): obtained from the flux-space graph weighted by local rate coefficients. This representation emphasizes similarities between paths A and B (because they both share several milestones), and their difference with respect to path C.

Tables

Generic image for table
Table I.

Algorithm 1 - Dijkstra's algorithm to find the shortest path lengths from vertex to all other vertices in graph

Generic image for table
Table II.

Algorithm 2 - Modified Dijkstra's algorithm for finding maximum weights and bottleneck (EMW) edges from to all other vertices in a graph . Refer to the algorithm description for the meaning of all variables.

Generic image for table
Table III.

Algorithm 3 – Recursive Dijkstra's algorithm to find the global maximum weight path between vertices and , in a directed graph, based on the modified Dijkstra algorithm for maximum weight paths. Refer to the Dijkstra's algorithm description for the meaning of variables.

Generic image for table
Table IV.

Summary of asymptotic time complexities using various algorithms for dense ( 2) and sparse () graphs. means the graph is implemented using adjacency lists, means the graph is implemented using adjacency matrices, means the priority queue in Dijkstra's algorithm is implemented using arrays and means the priority queue is implemented using Fibonacci heaps. These scaling factors have been derived in the Efficiency section of each algorithm.

Generic image for table
Table V.

Average runtimes in milliseconds for random graphs with 100, 1000, and 10 000 vertices, for the Recursive Dijkstra's, Edge-List Bisection, and Edge-Elimination algorithm. Runtimes were calculated on a single core of an 8 core Linux Intel Xeon X5460 processor with clock speed of 3.16 GHz and 16 GB memory shared among 8 cores. Runtimes were not calculated for the Edge-Elimination algorithm for 10 000 vertices since the estimated runtime was too long. Also shown is the number of edges for each size of random graphs.

Loading

Article metrics loading...

/content/aip/journal/jcp/139/17/10.1063/1.4827495
2013-11-05
2014-04-21
Loading

Full text loading...

This is a required field
Please enter a valid email address
752b84549af89a08dbdd7fdb8b9568b5 journal.articlezxybnytfddd
Scitation: Analyzing milestoning networks for molecular kinetics: Definitions, algorithms, and examples
http://aip.metastore.ingenta.com/content/aip/journal/jcp/139/17/10.1063/1.4827495
10.1063/1.4827495
SEARCH_EXPAND_ITEM