msmbuilder.tpt.paths

msmbuilder.tpt.paths(sources, sinks, net_flux, remove_path='subtract', num_paths=inf, flux_cutoff=0.9999999999)

Get the top N paths by iteratively performing Dijkstra’s algorithm.

Parameters:

sources : array_like, int

One-dimensional list of nodes to define the source states.

sinks : array_like, int

One-dimensional list of nodes to define the sink states.

net_flux : np.ndarray

Net flux of the MSM

remove_path : str or callable, optional

Function for removing a path from the net flux matrix. (if str, one of {‘subtract’, ‘bottleneck’}) See note below for more details.

num_paths : int, optional

Number of paths to find

flux_cutoff : float, optional

Quit looking for paths once the explained flux is greater than this cutoff (as a percentage of the total).
Returns:

paths : list

List of paths. Each item is an array of nodes visited in the path.

fluxes : np.ndarray, shape = [n_paths,]

Flux of each path returned.

See also

msmbuilder.tpt.top_path
function for computing the single highest flux pathway through a network.

Notes

The Dijkstra algorithm only allows for computing the single top flux pathway through the net flux matrix. If we want many paths, there are many ways of finding the second highest flux pathway.

The algorithm proceeds as follows:

  1. Using the Djikstra algorithm, find the highest flux pathway from the sources to the sink states
  2. Remove that pathway from the net flux matrix by some criterion
  3. Repeat (1) with the modified net flux matrix

Currently, there are two schemes for step (2):

  • ‘subtract’ : Remove the path by subtracting the flux of the path from every edge in the path. This was suggested by Metzner, Schutte, and Vanden-Eijnden. Transition Path Theory for Markov Jump Processes. Multiscale Model. Simul. 7, 1192-1219 (2009).
  • ‘bottleneck’ : Remove the path by only removing the edge that corresponds to the bottleneck of the path.

If a new scheme is desired, the user may pass a function that takes the net_flux and the path to remove and returns the new net flux matrix.

References

[R68]Weinan, E. and Vanden-Eijnden, E. Towards a theory of transition paths. J. Stat. Phys. 123, 503-523 (2006).
[R69]Metzner, P., Schutte, C. & Vanden-Eijnden, E. Transition path theory for Markov jump processes. Multiscale Model. Simul. 7, 1192-1219 (2009).
[R70]Berezhkovskii, A., Hummer, G. & Szabo, A. Reactive flux and folding pathways in network models of coarse-grained protein dynamics. J. Chem. Phys. 130, 205102 (2009).
[R71]Dijkstra, E. W. A Note on Two Problems in Connexion with Graphs. Numeriche Mathematik 1, 269-271 (1959).
[R72]Noe, Frank, et al. “Constructing the equilibrium ensemble of folding pathways from short off-equilibrium simulations.” PNAS 106.45 (2009): 19011-19016.