Hausdorff metric.

We start with a 3N-dimensional configuration space containing two paths P and Q represented, respectively, as sequences of conformations and . The Hausdorff distance is defined as (2) where (3) is the directed Hausdorff distance from P to Q, and d is a distance metric on ℝ^3N (measuring point distances) [43]; the vertical bar (P∣Q) emphasizes that δ_h(P∣Q) is not commutative. The function δ_h(P∣Q) selects the point p* ∈ P, among all points in P, with the most distant nearest neighbor q* ∈ Q (as measured by d(p*,q*)). In the language of conformational transitions, we interpret d(p, q) as a putative structural similarity measure between conformers p and q, so that for some conformer p_k ∈ P, its structural “nearest neighbor” in Q is given by min_{q ∈ Q} d(p_k, q). Thus, δ_h(P∣Q) is the distance d associated with the conformer in P having the most distant or least similar nearest neighbor (in Q). The Hausdorff distance between P and Q, δ_H(P, Q), is therefore the distance associated with the point—of all points in P and Q—with the least similar nearest neighbor, and implies that all points have a nearest neighbor that is at most δ_H(P, Q) away.

Fréchet metric.

Unlike the Hausdorff metric, Fréchet metrics are sensitive to the orientation (i.e., directionality) of paths; real transition paths are inherently directional which in principle makes Fréchet metrics superior to the Hausdorff metric. Informally, the continuous Fréchet distance can be visualized by considering a man walking on a path P and his dog on another path Q [47]. Both start at the initial points of their respective paths, and they are imagined to be connected by an elastic leash that remains taught so as to measure the distance separating them at all times. We then allow the man and dog to move independently on their respective paths under the condition that each progresses in a monotonic fashion (i.e., no backward steps) from start to finish. The Fréchet distance between P and Q is then defined as the length of the shortest leash necessary for the man and dog to move along their respective paths from beginning to end according to the aforementioned constraints. Formally, for two continuous curves P : [a₀, a₁] → ℝ^3N, a₀ < a₁ and Q : [b₀, b₁] → ℝ^3N, b₀ < b₁ that are parameterized with a real parameter, the continuous Fréchet distance corresponds to finding two specific continuous and monotonous parameterizations α:[0, 1] → [a₀, a₁] and β:[0, 1] → [b₀, b₁] (the “schedules” of the man and the dog along their paths) so that the largest point distance d for a given set of parameterizations is minimized [47], (4) Algorithms exist to solve this difficult problem in O(nm log nm) time for polygonal curves (where n and m are the number of vertices in each curve) [47] and various faster approximate solutions have been suggested [48, 49].

In this paper, however, we exclusively use the discrete Fréchet distance, δ_dF, with the algorithm outlined by [50] as it is simpler and faster to compute (in O(nm) time) than its continuous counterpart, δ_F. The formal definition of δ_dF considers two polygonal curves P and Q that are defined respectively by n and m ordered points in a metric space (V, d) for some metric d. Let the corresponding sequence of endpoints of the line segments of P and Q be respectively defined as σ(P) = (p₁, …, p_n) and σ(Q) = (q₁, …, q_m). In the product space σ(Q, P) ≡ σ(P) × σ(Q), we define a coupling between two polygonal curves P and Q as a sequence, (5) of L unique pairs of points (i.e., number of links) satisfying the following conditions: (1) The first/last pairs correspond to the first/last points of the respective paths (a₁ = b₁ = 1, a_L = n and b_L = m); (2) at least one point on a path (for a pair of points, one per path) must be advanced to its successive point, i.e., (a_i+1 = a_i and b_i+1 = b_i + 1) or (a_i+1 = a_i + 1 and b_i+1 = b_i) or (a_i+1 = a_i + 1 and b_i+1 = b_i + 1) for all i = 1, …, L. The largest distance between a pair of points (p_ai, q_bi) for a given coupling C defines the coupling distance (6) Given the space of all possible couplings between P and Q, Γ_{P, Q}, the discrete Fréchet distance between P and Q is the minimum coupling distance among all couplings in Γ_{P, Q}: (7)

The continuous Fréchet distance constitutes a lower bound on the discrete Fréchet distance, δ_F ≤ δ_dF, because δ_F accounts for points along the (straight) edges connecting the vertices, whereas δ_dF only takes the vertices themselves into consideration [50]. Furthermore, if we define the maximum edge length for a polygonal curve P to be the largest distance between consecutive points in P, d_max(P) ≡ max_{i = 1, …, p−1} d(p_i, p_i+1), we can set an upper bound on δ_dF given two polygonal curves P and Q so that δ_F(P, Q) ≤ δ_dF(P, Q) ≤ δ_F(P, Q) + max{d_max(P), d_max(Q)} [50]. Thus, δ_dF differs from δ_F by no more than the longest edge among both paths and, to good approximation, δ_dF ≈ δ_F for typical trajectories with regularly spaced conformations. Hereafter we refer to the discrete Fréchet distance as simply the Fréchet metric (distance) with symbol δ_F for brevity. The Fréchet distance is bounded from below by the Hausdorff distance for any given pair of piecewise-linear curves [51] (δ_F ≥ δ_H) because for convex polygonal curves the Fréchet and Hausdorff distances are equal [52] while for other path geometries the Fréchet distance can become arbitrarily larger than the Hausdorff distance [48]. In the case of macromolecular trajectories, the case of backtracking appears particularly relevant because of its conceptual link to a random walk and its connection to thermal fluctuations. If one path runs backward along some portion relative to another path, the Fréchet distance will increase with the extent of the backtracking, whereas the Hausdorff distance will be unaffected since it ignores the direction of path traversal (Fig 1).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 1. Comparison of Hausdorff and Fréchet distance. Two paths P (green) and Q (cyan) begin at state c₀ and end at state c_f with directionality indicated by the arrows.

The Fréchet distance δ_F and Hausdorff distance δ_H are given by the lengths of the purple and orange lines, respectively. The purple lines are the same length and correspond to the minimally stretched Fréchet “leash”; the orange line spans a pair of points separated by the Hausdorff distance (only one is shown because in this case there are infinitely many pairs of points with the same δ_H). Due to the backtracking of path P toward state A, combined with the monotonicity (no-backward-movement) constraint of the Fréchet metric, δ_F > δ_H.

https://doi.org/10.1371/journal.pcbi.1004568.g001

Measuring structural similarity.

Both the Hausdorff and Fréchet distances defined in Eq 2 and Eq 7, respectively, are defined in terms of a point metric d(p, q) on 3N-dimensional configuration space that measures the distance (i.e., similarity) between conformations p and q. We employ the root mean square distance (rmsd) defined in the usual way as (8) where N is the number of atoms, and and define the configuration space coordinates of conformations p and q, respectively.

It should be noted that Hausdorff and Fréchet metrics can be defined in terms of other point metrics to measure and thus emphasize different aspects of macromolecular structure or topology. For example, one could choose to measure the similarity of two protein conformers by quantifying the percentage of shared contacts. Another promising approach may be to integrate information-based metrics used for measuring the similarity of protein ensembles [53]. In this paper, we exclusively used the best-fit rmsd as the point metric due to its simplicity and widespread use, helping to connect with familiar intuitions and avoid obfuscating the examination of the path metrics themselves.

Previous studies and alternative approaches.

The Hausdorff metric has found applications in image comparison [43], while the orientation-dependent Fréchet metric has been used for handwriting recognition and searching handwritten documents [54], and comparing trajectories of moving objects in geographic information systems [55]. Both metrics have also found applications in biology for protein structure alignment [56, 57] and protein homology analysis [58, 59].

To our knowledge, the Hausdorff and Fréchet metrics have not been widely used as general tools to quantify macromolecular pathways. However, recently two studies employed Fréchet distances to assess convergence of transition paths to an optimal path. Jiang et al. [60] used the same discrete Fréchet metric as used in this study to assess the convergence of a swarms-of-trajectories string method. Dickson et al. [61] employed a variation of the discrete Fréchet distance where the coupling distance was defined as the average distance between all pairs in a coupling (instead of the maximum distance as in Eq 6); this discrete average Fréchet distance was used in combination with an adaptive biasing force method to assess the convergence to an optimal path in an a priori CV space and was found to produce easier-to-read results by reducing statistical noise compared to the conventional metric. We explore this distance function in more detail in S1 Text along with a type of average Hausdorff distance. Protein folding pathways have been compared quantitatively but not with Hausdorff or Fréchet metrics. Several such studies utilized native contacts-based path (dis)similarity measures [62–65]. In particular, both Graham et al. [64] and Lindorff-Larsen et al. [65] used dissimilarity scores to assign individual paths to folding pathways using clustering. Different methods to sample conformational transitions were compared by Huang et al. [66], who contrasted the original targeted MD (TMD) algorithm [13] with a harmonic restraint variation of TMD (also known as “steered MD” (SMD) or “restrained TMD” (rTMD) [67])—and biased MD (BMD) approaches, and Ovchinnikov and Karplus [68], who analyzed the free energy profiles along the transition tubes surrounding the paths produced by several TMD variants.

The use of the Fréchet and Hausdorff path metrics on transition paths itself is not new; however, their application as general-purpose tools for quantitatively analyzing and comparing ensembles of transition paths—and extracting the molecular-scale determinants that dictate their differences—is, to our knowledge, novel. A particularly important advantage of the Hausdorff and Fréchet metrics is that they do not require a choice of progress variable, unlike metrics based on binning trajectory snapshots to compute path rmsds. While we emphasize that PSA suggests a general approach to quantitative transition path analysis using different structural and path metrics, we restricted our study to the Hausdorff and Fréchet path metrics implemented with the rmsd (as a structural similarity metric) to demonstrate the viability of a basic approach. We attempted to keep the underlying principles of PSA in view to engender future PSA-based analyses (such as quantifying putative reaction coordinates) and we stress that this study does not purport to exhaust all applications of PSA, nor represent an optimized application. Other path metrics—e.g., Fréchet with speed limits, direction-based Fréchet [69], or Fréchet with shortcuts for the analysis of noisy data [70]—may offer advantages in carrying out various analyses. The Hausdorff distance can be generalized as well to measure, for instance, distances between surfaces (instead of 1D curves) [71]. The multitudinous permutations that can be selected among the various path metrics, structural similarity metrics, clustering algorithms, etc. make PSA a flexible tool for trajectory analysis.

Path similarity analysis (PSA).

The Hausdorff metric, δ_H, and the discrete Fréchet metric, δ_dF, defined in Eq 2 and Eq 7, respectively, were computed as described in the Introduction. Further details on the numerical implementation are provided in S2 Text. Both metrics are implemented as part of the MDAnalysis Python package [92] in the module MDAnalysis.analysis.psa, which is available as open source at www.mdanalysis.org under the GNU General Public License 2.

To analyze a set of N paths, we compute the N(N − 1)/2 unique pairwise Hausdorff and Fréchet distances. To present the data efficiently, we levied the versatility of hierarchical clustering [93] along with the visual power of a heat map-dendrogram representation to present a quantitative approach to visualizing the similarities of collections of paths. In agglomerative hierarchical clustering, similar objects are linked together in a pairwise fashion to form growing clusters in a bottom-up approach. The similarity between two objects is defined by a metric, while the similarity of clusters (i.e., sets of objects) is uniquely determined by a linkage criterion that computes inter-cluster similarity as a function of the pairwise similarities of the objects comprising each cluster.

Using the Hausdorff and Fréchet metrics as similarity measures, we employed Ward’s method [94] in conjunction with agglomerative hierarchical clustering as implemented in the SciPy Python package [95]. The Ward linkage criterion specifies a minimum variance criterion that minimizes the total intra-cluster variance. In light of the focus of this paper, we restrict our study to hierarchical clustering using primarily Ward linkage—details regarding this restriction are provided in S3 Text in the Supporting Information along with other relevant considerations in using cluster analysis to facilitate PSA.

Native contacts analysis (NCA).

For consistency with other methods used in this paper, we define a contact to be a residue pair whose C_α atoms are separated by a distance smaller than 8 Å. A native contact is a contact present in a reference structure. Given a transition path, the fraction of native contacts Q [96] is the fraction of contacts in a native structure that are present in a transition structure. We then define Q1 and Q2, for any intermediate conformer in a transition, as the fractions of native contacts with respect to an initial and final structure, respectively. Transition paths are projected onto 2D Q₁-Q₂ (NC) space by parametrically plotting the percentage of contacts relative to the initial and final states.

Comparison with a linearly interpolated path.

A simple way to quantify the geometry of a single transition path is to measure its orthogonal separation, ρ, from a reference path as a function of progress, ζ, along the reference path (Fig 3). In this way, any transition path can be projected in a 2D space depicting “displacement” (ρ) versus “progress” (ζ) relative to a reference path. We selected naive linear interpolation (LinInt) to serve as a simple zeroth-order reference. Note that, in comparison with PSA, this approach necessitates defining an explicit progress measure in the form of a reference path—which may not be appropriate beyond relatively simple examples like the AdK transition—and is furthermore not amenable to direct pairwise comparisons among a large ensemble of transition paths.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 3. Comparison with a linearly interpolated path. A hypothetical transition pathway P (cyan line) in a 3D configuration space composed of a discrete number of conformer snapshots (cyan circles) connects an initial state (green circle), c₀, and final state (red diamond), c_f.

The reference path R (black line) is represented by LinInt. Each snapshot p_k is associated with its projection, r_k, on R; the progress, ζ(k), is the rmsd between r_k and c_f (dashed purple line along R) and the displacement, ρ(k), is the rmsd between p_k and r_k (dashed purple line perpendicular to R).

https://doi.org/10.1371/journal.pcbi.1004568.g003

Given two boundary conformations {c₀, c_f} ∈ ℝ^3N in 3N-dimensional configuration space with reference path R embedded in ℝ^3N (that linearly interpolates c₀ and c_f), and a piecewise-linear (transition) path P embedded in ℝ^3N and composed of a sequence of conformations, , where m is the number of time steps, we compute for each p_k: (1) the rmsd between p_k and its orthogonal projection onto R, r_k, (9) and (2) the rmsd between r_k and final state c_f, (10) (see Fig 3). A transition path can then be projected onto ζ-ρ space by parametrically plotting ζ(k) versus ρ(k) for all values of k. For a path beginning at r₀ = c₀, the rmsd to the final structure is given by the rmsd between the initial and final states, ζ(0) = d_RMS(c₀, c_f), while the rmsd for a path ending at r_m = c_f is ζ(m) = d_RMS(c_f, c_f) = 0.

Defining ρ using the rmsd permits a close connection with PSA in the following way: the maximal rmsd of a path P from LinInt, will be the Hausdorff distance between P and LinInt, δ_H(P,LinInt), when P is restricted to the region of configuration space between the boundary conformations (and assuming that structural alignment prior to rmsd measurement was performed identically). Furthermore, when P does not “backtrack”, ζ(k) is monotonically decreasing—indeed, P can be said to backtrack (with respect to some reference path) when ζ(k) is not monotone—and the Hausdorff and Fréchet distances coincide: .

Heuristic collective variables.

While dimensionality reduction can be useful for visualizing and identifying functional protein motions, selecting the collective variables that span the projected space and adequately describe a conformational transition is nontrivial [97, 98]. Choosing heuristic coordinates for a given system often requires strong physical intuition, something that may be absent when studying new or complicated transitions. In general, the determination of reaction coordinates and/or order parameters can be guided by quantitative methods, such as principal component analysis or the construction of isocommittor surfaces. In the relatively simple case of AdK’s closed ↔ open transition, several viable order parameters have been used as low-dimensional descriptions [12].

To explicitly illustrate the uses and limitations of heuristic collective variables, and to make a connection with previous work, we examine the AdK closed ↔ open transition (Fig 2A) in 2D angle-angle space [99]. The NMP-CORE angle θ_NMP is formed by the geometric centers of residues 115–125 (CORE-LID), 90–100 (CORE), and 35–55 (NMP) of E. coli AdK. Likewise, θ_LID is defined as the angle between residues 179–185 (CORE), 115–125 (CORE-hinge-LID), and 125–153 (LID). As many of the methods we studied used C_α-only models, we defined NMP-CORE and LID-CORE angles by exclusively using the C_α atoms of the residues. The angle-angle space defined by (θ_NMP, θ_LID) quantifies the degree to which NMP and LID are open and the sequence in which they open (close) for the closed → open (open → closed) transition.

Toy model: Double-barrel potential.

To determine the extent to which the Hausdorff and Fréchet metrics are suitable for measuring transition paths, we constructed a toy system to generate well-defined trajectories driven by a one-way ramp potential and subject to thermal noise; the resulting paths in configuration space can be viewed as thermally-perturbed straight lines. For our purposes, transition progress was measured by the center-of-mass distance of a group of particles moving along the ramp so that a transition was completed once the center-of-mass trajectory crossed a threshold value.

The toy system is defined as a group of N particles connected by harmonic springs subject to Brownian dynamics in a 3D potential energy landscape (Fig 4). Individual particles were connected in analogy to a complete graph, with vertices and edges respectively representing particles and springs. Spring equilibrium distances were set to zero separation for simplicity. Differing dimensionalities of the configuration space were examined by varying the number of particles N. The external potential was given a double-well shape in the y-direction and a parabolic shape in the x-direction (centered at x = y = 0), ensuring that particle clusters are confined to one of two “barrels” running along the z-direction (Fig 4). The energy barrier between the tubes was set to a height of 2 k_B T (∼ 5 kJ/mol) at T = 300 K. We set up a ramp potential sloping down toward increasing z (i.e., a constant potential energy gradient in the positive z direction) to induce large-scale transitions from small to large values of z.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 4. The toy model consists of a cluster of connected particles moving in a double-well potential along the z-axis under the influence of a linear ramp potential (not shown).

In the cluster for N = 8, each particle (red) is connected to every other particle with a harmonic spring (blue) of equilibrium length 0 (cluster not shown to scale.) The potential landscape for constant z forms a “double barrel”—red (blue) regions correspond to high (low) energies—is parabolic along the x-direction (cyan line), and has a double-well shape in the y-direction (purple line), which produces a central barrier separating two “barrels” (gray crosshatching). A saddle point is located at the intersection of the cyan and purple lines. Motion in this landscape is biased toward either of the low-energy barrels, but transitions between barrels are possible at finite temperatures.

https://doi.org/10.1371/journal.pcbi.1004568.g004

To construct a properly coarse-grained system, we required zero-temperature cluster dynamics to be identical for all N-particle clusters (given sensibly chosen initial conditions). Spring constants, particle masses and sizes, and the external potentials were scaled so as to preserve the average diffusive behavior of a cluster. Furthermore, spring constants were chosen to be large enough to prevent clusters from splitting themselves across the central barrier (where some particles in the cluster fall to one tube and some fall to the other). Particles comprising a cluster were furthermore initialized at the same location so that zero temperature center-of-mass trajectories would be independent of particle number, N. It should be emphasized that this toy model was not intended to replicate a real physical system, but primarily served to build intuition prior to studying conformational pathways in realistic protein systems. More detailed information about the construction of the double-barrel system is provided in S4 Text in the Supporting Information.

Simulation methods and systems.

The path-sampling methods comparison was performed using the AdK closed → open transition—between the (initial) closed conformation (PDB id 1AKE:A) and final (open) conformation (PDB id 4AKE:A)—as a testbed. We used eight methods available on publicly accessible servers [31, 72, 100–104], two in-house methods (DIMS, dynamic importance sampling [105], and FRODA, Framework Rigidity Optimized Dynamics Algorithm [39]), and targeted MD (rTMD [67]) using local simulation resources (see Tables 1 and 2 for overviews). DIMS and FRODA were additionally used to generate example ensembles of AdK and DT transitions (200 transitions per method per protein, 800 total) for ensemble-based and Hausdorff pairs analysis. In principle, other path-sampling methods could be included in a comparison and, in the future, it would be worth exploring alternative methods such as the finite-temperature string method [106], weighted ensemble dynamics [107, 108], milestoning [109], transition path sampling [110], non-equilibrium umbrella sampling [111] or forward flux sampling [112], to name a few. Key aspects of each method used in this study are summarized below to help connect our results with physical intuition about the models. Each path-sampling method is described in the context of the energetics they model (Table 1) and the schemes by which paths are propagated or generated (Table 2). Additional details about the methods and the corresponding simulation settings that were used can be found in S5 Text.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 1. Modeling of energetics in tested path-sampling methods.

https://doi.org/10.1371/journal.pcbi.1004568.t001

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 2. Approach to generating paths in tested path-sampling methods.

https://doi.org/10.1371/journal.pcbi.1004568.t002

Two of the tested methods are based on MD combined with perturbation techniques (perturbation MD) designed to drive transitions between initial and final states. Two MD methods—DIMS MD [15, 105] (implemented in CHARMM c36b2 [113]) and TMD (implemented in NAMD 2.10 [114])—used the all-atom CHARMM22/CMAP force field [115, 116] with Langevin dynamics and implicit solvents (ACE [117] in CHARMM, Generalized Born [118] in NAMD) in the NVT ensemble at 300 K. NAMD’s TMD implementation uses a time-dependent harmonic restraint that moves toward a target conformation with constant velocity [67], instead of the original TMD approach introduced by Schlitter [13] that employed a stepwise holonomic constraint; in accordance with Ovchinnikov and Karplus [68], we refer to the NAMD implementation as restrained TMD (rTMD) to distinguish it from the original algorithm. DIMS and rTMD transitions were driven using the heavy-atom rmsd to the target structure. The soft-ratcheting DIMS algorithm moves towards the target by taking trial MD steps. Steps toward the target (decreasing rmsd-to-target) are accepted whereas backward steps are rejected with a finite probability; velocities are re-sampled (according to Maxwell-Boltzmann) until the step is accepted. rTMD moves a harmonic restraint to linearly decrease the rmsd-to-target. We generated three rTMD paths using a fast pulling speed and three with slower pulling. rTMD differs from DIMS in that explicit forces are introduced into the system Hamiltonian whereas DIMS effectively introduces an entropic force.

Maxwell-Demon discrete Molecular Dynamics [100] (MDdMD) and GOdMD [101] are similar in spirit and are the only two methods based on a physical dynamical model among the server-based transition path generation methods. Both are based on discrete MD combined with soft ratcheting and a type of essential dynamics sampling. MDdMD utilizes an atomistic representation and an implicit solvent model; GOdMD uses a C_α representation and neglects solvent effects. Both methods model bonded forces with infinite square-wells although MDdMD incorporates further detail by using simple potentials to describe van der Waals and electrostatic forces; GOdMD uses a Go-like potential to describe non-bonded forces. Both also include an additional form of biasing to ensure transitions follow essential deformation movements of a protein: MDdMD accepts steps when the transition vector (from the current conformer to the target) overlaps sufficiently with an essential transition vector (defined using eigenvectors from NMA on a Go-like potential about the initial or final state); GOdMD uses an ENM-based metadynamics approach to bias the sampling of essential deformation modes and to ensure that trajectories escape the initial minima.

The geometrical targeting algorithm, FRODA [39], is an approach designed to produce stereochemically acceptable transition paths. FRODA moves a structure toward a target conformation by decreasing the rmsd-to-target while enforcing stereochemical constraints such as bond distances and angles, backbone dihedrals, and contact constraints. In particular, FRODA can avoid steric clashes in an all-atom structure, something that may not be achieved by coarse-grained elastic network models (CG-ENMs) or algorithms using simple linear interpolation.

We also generated transitions using five CG-ENM-based methods. These particular models first construct two harmonic potential energy functions, based on anisotropic network models (ANMs), about initial and final native (crystallographic) states, which has the general form where the sum is taken over all unique pairs of C_α atoms separated by less than a specified cutoff distance, R_c, and ΔU is the energy difference between the two states. For atoms i and j, C_ij is the force constant, d_ij is the Euclidean distance between them, and is the corresponding distance in the native (crystallographic) structure. Force constants can be determined by fitting to isotropic crystallographic B-factors for instance. A double-well (two-state) potential landscape is constructed by combining the separate potentials. Given a two-state potential, transition paths are generated by connecting the two (end-state) minima along low-energy pathways. The ENM-based methods are distinguished primarily by their two-state energetics (i.e., mixing potential) and method of defining and searching for low-energy transition paths. The cutoff distance, R_c, can be adjusted to some degree for all the tested ENM-based approaches, but a couple also enable modification of the force (spring) constants, C_ij, and the end state energy difference, ΔU.

ANMPathway [102] (ANMP) forms a double-well landscape where the energy at each point is taken to be the smaller of the energies specified by the two wells; the wells intersect to form a cusp hypersurface in configuration space. A path is found by locating the minimum along the cusp and performing steepest descent (SD) toward both well minima. The Mixed Elastic Network Model [104] (MENM) employs a double-well function with a tunable mixing temperature whose purpose is to modulate the cusp-like intersection to provide a smooth transition in energy between the two wells. The method locates saddle points (SPs), and can use a steepest descent (SD) mode (MENM-SD) to generate paths from the SPs to the minima, or it can provide a parametric equation describing an SP path through the fixed points of the landscape. The interpolated Elastic Network Model [103] (iENM) is similar to MENM-SP in that it analytically solves for a parametric SP path, although it only requires a general form of a double-well potential function (does not use an explicit mixing function). Unlike the other ENM-based methods, MinActionPath [31] (MAP) does not use a mixing function. Instead, a path is generated by minimizing the Onsager- Machlup (OM) action—which assumes overdamped Langevin dynamics—with the two separate ANMs for the native states to derive two one-dimensional differential equations describing the minimum action paths in the region of each ANM. A unique transition path between the initial and final states is found by satisfying continuity boundary conditions in the positions and velocities at the interface.

To provide a point of comparison to one of the most simple approaches, we used the Yale morph server [72, 119] (Morph), which combines linear interpolation and optional energy minimization of the intermediate snapshots (i.e., adiabatic mapping), and we also used explicit linear interpolation to generate a single path between the end states (LinInt).

The main thrust of the path-sampling methods comparison is to demonstrate PSA’s viability and not necessarily to directly evaluate the performance of the sampling algorithms. As such, adjustable parameters for all simulations were left at their default values unless explicitly stated. Transitions were produced using the highest allowable resolution, i.e., using all non-hydrogen atoms when possible or only C_α atoms otherwise. For each method, three unique paths were generated by either re-running those with stochastic algorithms or, for the deterministic ones, by adjusting a single parameter; in the case of rTMD, six total simulations were performed [three each for fast (∼ 1 Å/ps) and slow (∼ 0.01 Å/ps) pulling speed; see S5 Text for further details]. DIMS, FRODA and MDdMD simulations, which produce a unique trajectory every run, were run three times each without altering initial settings. Three GOdMD runs were performed by changing the relaxation window (20, 50 and 100). Distinct trajectories for the deterministic, ENM- based algorithms were obtained by varying spring cutoff distances: one transition at the default value and two by decreasing/increasing the cutoff. Morph trajectories were produced by toggling energy minimization and structural pre-alignment settings, and a single LinInt trajectory was included as a zeroth-order reference. All other simulation settings were left at default values where possible. Simulations and analyses performed in this study are summarized in Table 3. Furthermore, as half of the methods were limited to C_α structures as inputs—the coarsest representation among the methods—all analyses were restricted to C_α trajectory representations to provide a lowest common denominator. Trajectories were also aligned to a common reference structure generated by aligning and averaging the CORE C_α coordinates of the 1AKE:A and 4AKE:A structures (see S6 Text in the Supporting Information for a description of the structural alignment procedures).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 3. Summary of simulations, calculations, and analyses.

https://doi.org/10.1371/journal.pcbi.1004568.t003

Direct comparison using PSA.

A total of 37 paths (eleven methods, three paths per method with the exception of six paths for rTMD, plus one LinInt path) were analyzed by computing the Fréchet distance between all possible pairs and clustering of the resulting (symmetric) distance matrix (S5 Fig). Using the same approach as with the toy model, the clustered distance matrix was translated to a heat map-dendrogram representation (Fig 6).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 6. Path similarity analysis of trajectories generated by different path-sampling methods.

The AdK closed → open transition was sampled three times (except LinInt) with different methods (see text). Smaller distances indicate transition paths with greater similarity. The dendrogram depicts a hierarchy of clusters where smaller node heights of parent clusters indicate greater similarity between child clusters. Fréchet distances δ_F are in Å and correspond to a structural rmsd in accordance with the rmsd point metric. See text for a description of the methods. S5 Fig contains the same data annotated with numerical values of δ_F.

https://doi.org/10.1371/journal.pcbi.1004568.g006

Paths from a given method were more similar to other paths from the same method than to those produced by a different method, as indicated by well-defined 3 × 3 squares along the heat map diagonal. Methods based on similar physical models tended to sample relatively similar pathways, while algorithmically distinct approaches appeared less likely to produce similar paths. For instance, Morph and LinInt both implement linear coordinate interpolation. Their paths are essentially identical (δ_F ≤ 0.5 Å), which indicates that additional features implemented in Morph, such as checking for steric overlaps, may not be relevant for the AdK transition. Another cluster was formed by the two MD-based importance sampling methods, DIMS and MDdMD, together with MD-based rTMD at slow pulling velocity (“rTMD-S”; Fréchet distance 2.1 Å ≤ δ_F ≤ 2.7 Å). In other cases, similarities and differences did not always follow an immediately obvious pattern. FRODA, which satisfies rigidity constraints during a transition but does not employ a potential energy function, nevertheless formed a cluster with DIMS, MDdMD, and rTMD-S (2.6 Å ≤ δ_F ≤ 3.1 Å). The grouping of FRODA with DIMS/MDdMD/rTMD-S appears, however, less strong than, for instance, the clustering of DIMS with MDdMD because for other choices of the linkage criterion FRODA is more distantly associated with the DIMS/MDdMD/rTMD-S cluster and a robust cluster of MAP/Morph/LinInt trajectories (see S6B–S6D Fig and further discussion in S3 Text). The fast-pulling rTMD (“rTMD-F”) and MAP trajectories were strikingly similar to the Morph paths (δ_F ≈ 1 Å), even though rTMD-F performs MD with an atomistic physics-based force field, whereas MAP’s energy function is based on an elastic network model and the path is generated via minimization of Onsager-Machlup action (and not just linear interpolation). Interestingly, the MAP/rTMD-F/Morph sub-cluster was grouped with the cluster formed by four of the dynamical algorithms (DIMS, MDdMD, rTMD-S, FRODA). The other four ENM algorithms—iENM, MENM-SD/SP, and ANMP—produced their own cluster, with MENM-SD and iENM being the most similar to each other. A careful examination of the heat map revealed that although MAP, rTMD-F, and Morph paths somewhat resembled iENM and MENM-SD paths (δ_F ≤ 2.5 Å), their overall patterns of Fréchet distances were very similar to DIMS/MDdMD/rTMD-S (as seen in the similar overall striping in the shading of the heat map) so that the “Morph-like cluster” rather clustered with these dynamical methods than with the “ENM cluster”. The GOdMD paths formed their own outlier cluster, appearing substantially different from all other methods (δ_F > 3 Å).

The classification of trajectories was found to be robust against use of different linkage functions in the clustering algorithm, provided that the linkage primarily assessed the dissimilarity of clusters (such as Ward’s criterion in Fig 6 and the complete/average/weighted linkage in S6B–S6D Fig) instead of similarity (single linkage in S6A Fig). Using the Hausdorff metric instead of the Fréchet metric did not change the clustering either and the Pearson correlation coefficient between δ_H and δ_F was very close to unity (S7 Fig). In S1 Text, alternative distance definitions, namely averaged Fréchet and Hausdorff distances (which are, however, not proper metrics), reduced the amount of detail in the clustering and resulted in an amalgamation of clusters into one large “dynamical methods cluster” (TMD-S, DIMS, MDdMD, GOdMD, FRODA), a “Morph-like cluster” (Morph, LinInt, TMD-S, MAP), and an “ENM cluster” (ANMP, iENM, MENM-SP/SD).

Without any input except the trajectories themselves, PSA produced distinct clusters that appeared to broadly distinguish between dynamical and non-dynamical path sampling methods. With the help of more specialized analyses to be described next we sought to further rationalize the observed pattern of clustering.

Native Contacts Analysis.

We performed two dimensional NCA on trajectories by measuring (for each conformer snapshot) the fraction of native contacts relative to the closed starting state (Q_1ake) and to the open target conformation (Q_4ake) as collective variables (Fig 7A). Using the NC trajectories, we examined the dynamic relationship of contact formation and breaking for each method. In general, the closed → open trajectories began on or near the right vertical axis, corresponding to the first conformers of the paths having (nearly) 100% of their contacts in common with the closed structure and around 95% of open state contacts. Most trajectories terminated at the top horizontal axis with the final conformers containing close to 100% of the final, open 4AKE:A structure contacts and about 93% of 1AKE:A contacts. The starting conformers of the DIMS NC paths only contained 96% of the contacts seen in the 1AKE crystal structure (Q_1ake = 0.96), which is to be expected given that the initial closed structure was energy-minimized and equilibrated prior to performing MD.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 7. Projections of trajectory 2 of the AdK closed → open transition from each path-sampling method onto low-dimensional collective variables.

The location of the initial structure is shown in each plot by the green circle, while the final structure is represented by the red diamond. (A) Projection of all pathways from the various path-sampling methods onto NC space. The horizontal axis corresponds to the percentage of contacts (of a transition snapshot) shared with the initial 1AKE:A structure (green circle) and the percentage of contacts in common with the final 4AKE:A structure (red diamond) is displayed on the vertical axis. The top-left legend identifies EN-based methods; the other methods are listed in the bottom legend. The LinInt path is shown for reference as a broken black curve. (B) Projection on NMP angle (θ_NMP) vs LID angle (θ_LID). In B and C, trajectories generated by the dynamical methods (DIMS, rTMD, FRODA, MDdMD, GOdMD) are plotted with diamonds and non-dynamical method trajectories with circles. (C) ζ-ρ space projection using LinInt as the reference path. Trajectory progress in ζ-ρ space is from left to right from higher to lower values of the progress variable ζ. MDdMD terminates at 1.5 Å C_α rmsd from 4AKE (red diamond); DIMS MD terminates at 0.5 Å heavy atom rmsd.

https://doi.org/10.1371/journal.pcbi.1004568.g007

The five dynamical methods—DIMS, rTMD, FRODA, MDdMD, and GOdMD—produced somewhat noisy paths where the fluctuations took place along a positively sloping direction in NC space. A positive slope implies that contacts were simultaneously formed or broken relative to both native structures, which can be taken to be indicative of passage through a transition state that is distinct from either end state conformation. DIMS trajectories did not exactly reach the target structure (Q_4ake ≤ 0.98) as DIMS simulations were considered complete as soon as a conformer was within 0.5 Å heavy atom (non-hydrogen) rmsd from the target crystal structure 4AKE. MDdMD paths partly overlapped with DIMS paths during contact breaking but failed to reform them (Q_4ake < 0.94); as with DIMS, transition completion is determined by a cutoff—manually set to 1.5 Å C_α rmsd—due to the difficulties of convergence to a target using the soft-ratcheting biasing approach in MDdMD. DIMS and MDdMD broke a similar number of contacts relative to both states (around 8–9% and 9–10%, respectively). rTMD-S showed qualitatively similar behavior but broke up to about 12% of native contacts. The closely-knit cluster of DIMS, MDdMD and rTMD-S paths produced by PSA reflects the qualitative similarity of their NC trajectories. DIMS, MDdMD and FRODA all generated noisy, V-shaped NC pathways suggestive of a transition region, which supports the picture from PSA where these three methods form a loose cluster apart from the non-dynamical methods. FRODA clustered somewhat apart from the other three, correlating with the observation that FRODA trajectories in NC space exhibited the greatest contact breaking (Q_1ake = 0.82, Q_4ake = 0.80) of all methods tested. This behavior is not unexpected because FRODA achieves random motion by randomly displacing and rotating rigid units of the protein at the sub-amino acid level at each step prior to re-enforcing geometric constraints. As such, C_α fluctuations and, thus, native contact dynamics that would be prohibited by conventional potentials are permitted by the geometric model although constraints on the overall sequence and structure would nevertheless limit dramatic perturbations to the C_α rmsd. GOdMD paths, though quite noisy, followed a path more closely resembling those from the non-dynamical methods, particularly MAP and Morph.

Morph, LinInt, and two of the five ENM-based methods (ANMP and iENM) produced the shortest NC trajectories progressing directly to the target conformation with relatively little wandering, whereas the six MENM paths deviated noticeably toward the DIMS and FRODA trajectories in the latter half of the transition; MAP paths were also nearer the MENM pathways in location and shape than to the paths from the other ENM-based methods. The MENM paths and two MAP paths were unique among the non-dynamical methods in that they each contained a V-shaped, cusp-like feature where extra 4AKE:A contacts were broken (Q_4ake ≈ 0.91, 0.91 and 0.92, respectively) that were subsequently reformed toward the end of the transition. The rTMD-F NC paths were situated in an intermediate position between the other dynamical methods and the non-dynamical methods. Initially, only 1AKE:A contacts that do not exist in 4AKE:A were broken. Then the missing 4AKE:A native contacts were formed. The Morph, LinInt, ANMP and iENM paths, which were divided between two clusters in PSA, exhibited progress along negatively sloped NC space trajectories during which 4AKE:A contacts were formed while 1AKE:A contacts were simultaneously broken. However, the close structural correspondence between MAP, rTMD-F, and Morph paths in PSA was not recapitulated in NCA. On the other hand, the ANMP paths, which were reasonably similar to iENM in PSA (1.4 Å ≤ δ_F ≤ 2.7 Å in Fig 6) but fairly different from Morph (2.8 Å ≤ δ_F ≤ 3.1 Å), appeared fairly similar to both iENM and Morph in NC space.

Comparison of the NC projections of rTMD-S and rTMD-F indicated that the pulling velocity in rTMD directly affected the degree to which native contacts were broken and reformed. Consequently, different transition pathways were followed, as indicated by PSA, where rTMD-S clustered with the other dynamical methods and rTMD-F was most similar to LinInt and Morph.

NCA identified the same general division between the dynamical and non-dynamical methods as PSA, while some subdivisions within the dynamical/non-dynamical dichotomy are also borne out by both analyses, such as the closer grouping of MDdMD/rTMD-S/DIMS than FRODA/DIMS or FRODA/MDdMD. However, the cusp-like feature and overall qualitative similarity of the MENM and MAP trajectories in NC space that set them apart from the other non-dynamical methods is not obviously captured by PSA. The NC projection did not offer a clear hint as to why ANMP, iENM, and MENM-SD/SP were subdivided as they were in PSA and why GOdMD appeared as an outlier—two questions addressed by the following analysis of the transition paths projected onto ζ-ρ and angle-angle coordinates.

Projections into ζ-ρ and angle-angle space.

PSA and NCA are both general transition path analysis methods that do not require knowledge of any system-specific order parameters or collective variables. We employ the ζ-ρ projection (distance from and progress along the path of linear interpolation) in order to resolve the remaining apparent discrepancies between PSA and NCA. Because good collective variables are known for the AdK transition [12], we also use a 2D projection onto domain angles [99] to connect the conclusions derived from the general analyses to visually intuitive structural motions of the closed → open transition.

In the ζ-ρ space projection (Fig 7C), the dynamical methods tended to obtain the greatest distance from the LinInt reference path near the end of the transition (ζ ⪅ 3.5 Å) whereas the non-dynamical methods peaked nearer the beginning. Thus, the dynamical/non-dynamical method dichotomy previously observed in both NCA and PSA was also present in ζ-ρ space. The structural interpretation of this behavior is, based on the projection into angle-angle space (Fig 7B), that the dynamical methods favored a pathway during which first the LID domain opens, followed by the NMP domain. Non-dynamical methods produced either NMP-opening-first paths or paths with brief LID-opening motions. In ζ-ρ space, however, dynamical methods produced paths with a greater average and peak (orthogonal) displacement from LinInt than non-dynamical methods (which cannot be discerned by apparent displacements in angle-angle space), further corroborating the clusterings from PSA.

Fast-pulling rTMD (rTMD-F), as a dynamical method, appeared as an exception to the dynamical/non-dynamical method dichotomy. However, both the projection onto domain angles and especially the ζ-ρ projection clearly showed that the rTMD-F path was very similar to LinInt (ρ < 1 Å in Fig 7C). rTMD with very high pulling velocities of the restraint potential moves the system almost exlusively in the direction of the restraint force. For an rmsd restraint, the gradient points exactly along the LinInt path. Therefore, rTMD-F functions more like LinInt or Morph and less like equilibrium MD with an additional bias potential and hence PSA clustered rTMD-F with LinInt and Morph (Fig 6).

MENM-SP was the most distant member in the cluster of the four ENM-based methods in PSA (Fig 6). Careful inspection of both angle-angle space (Fig 7B) and ζ-ρ (Fig 7C) revealed that the MENM-SP path contained a very large gap in the trajectory snapshots; the penultimate conformer was located in the first half of the transition (ζ > 4 Å), while the final snapshot was the open crystal structure end state. Such a big gap in the path affects the discrete Hausdorff/Fréchet distances because the distance between two MENM-SP paths with well-aligned gaps is unaffected whereas the distance between an MENM-SP path and one without gaps tends to be somewhat larger due to large point distances originating from the latter’s conformers in the portion of the transition where the gap occurs. ANMP was also somewhat of an outlier within the ENM cluster (Fig 6), which can be traced to its path being much farther away from the LinInt reference than any other ENM/Morph method (ρ ≈ 2.2 …2.3 Å versus ρ ≈ 1.3 Å; Fig 7C). Structurally, the NMP domain opened nearly all the way before much of the LID motion took place, in contrast with every other method (Fig 7B).

GOdMD produced the path with the greatest peak displacement (ρ ≈ 2.8 Å; Fig 7C), corresponding to complete LID opening before substantial NMP movement occured (Fig 7B). The results from GOdMD are unlike any of the other methods and therefore GOdMD is well-classified as an outlier by PSA (Fig 6).

PSA was able to group fast transition path sampling methods into distinct clusters. These groupings could be rationalized by employing projections on more specialized collective variables. An important observation was that transition paths were most similar to other transition paths generated by the same method. This conclusion was, however, based on a small sample of three paths per method. We then sought to extend our analysis to larger ensembles of paths that would provide a statistically more meaningful comparison.

Summary.

We have developed a flexible and quantitative framework for analyzing macromolecular transition paths using path metrics as a means to measure the mutual similarity of paths in configuration space, potentially using the full 3N-dimensional configuration space information. As far as we are aware, there is currently no standard procedure for quantitatively analyzing and characterizing transition paths. After comparing a set of transitions from a variety of path-sampling algorithms and analyzing transition ensembles of two sets of dynamical, stochastic trajectories, the viability of PSA (Path Similarity Analysis) as a tool to quantitatively compare transition paths appears promising.

In particular, PSA demonstrated that for the adenylate kinase closed → open transition, fast path sampling methods generated paths that were more similar to other paths produced by the same method than to any other paths, suggesting that among these methods there is currently no real consensus for what a realistic conformational transition looks like. Hierarchical clustering in combination with a heat map representation indicated broad patterns whereby dynamical methods tended to be clustered with each other while non-dynamical ones (especially most of the elastic network-based ones) were more similar to each other than to methods such as dynamic importance sampling (DIMS) or the Framework Rigidity Optimized Dynamics Algorithm (FRODA). The clustering was qualitatively confirmed by a range of low-dimensional projections on collective variables, which can be used synergistically with PSA once additional knowledge about the system of interest is available.

The ensemble analysis also clearly showed that at least for large scale macromolecular transitions, the Fréchet and the Hausdorff distance are equally appropriate measures for path similarity, with the Hausdorff distance being cheaper to compute.

A key advantage of PSA is its generality in that no system specific knowledge is required and all trajectory data can easily be used. That generality might, however, obscure the physical and biological detail that is important for a mechanistic understanding of protein function. The new concept of Hausdorff (or Fréchet) pairs within the context of PSA suggests an effective approach to identifying the molecular determinants responsible for differences in paths between sampling methods, which could be related to variations in protein function, differences in path-sampling algorithms/models, or some combination of both (as demonstrated for the comparison between DIMS and FRODA).

Future directions.

The rmsd proved a useful choice for the point metric to measure structural similarity as its preponderance in the literature helps to connect path metric distance measurements to familiar intuitions although its interpretation is not entirely obvious across disparate contexts [120]. A further study would, for instance, benefit from a revised definition of native contacts where consecutive alpha carbons (within the cutoff distance) would be ignored. As such, a revised native- or self-contacts measure could be used as a point metric instead of rmsd. We also plan to employ k-medoids clustering—used to identify a “median” element (i.e., a medoid) in a set—as one possible approach to identifying representative transition paths, bringing us a step closer to identifying transition tubes or candidates for reaction coordinates.

Furthermore, PSA can aid the assessment of enhanced path-sampling algorithms and their performance by quantifying the degree of similarity to gold-standard transition paths (for instance, equilibrium MD transitions or—when available—experimental time-resolved structural data). Such quantitative comparisons would be key to assessing the physical plausibility of transitions generated by enhanced sampling methods. However, comparison of such transition paths to true equilibrium paths will require the development of a method to identify the actual transition events in the equilibrium data and to distinguish them from residency in (meta) stable states, ideally without introducing problem-specific order parameters. Possible approaches may include an analysis of the distribution of Hausdorff nearest neighbor distances or discrete Fréchet couplings or techniques to match subtrajectories [121, 122] but identifying barrier crossing events from coordinate trajectories in a general manner alone remains an open problem. By extending the analysis of Hausdorff pairs we should also be able to better pinpoint key structural events or mutations that affect the function of biomolecules and so improve our understanding of the connection between protein structure, dynamics and function.