Stable and scalable computation of state visitation probabilities in finite Markov chains.

We report an algorithm based on renormalization to compute the probability that a particular state, or set thereof, is visited along the first passage or transition paths between two endpoint states of a finite Markov chain. The procedure is numerically stable and does not require dense storage of the transition matrix.

Analysing ill-conditioned Markov chains.

Discrete state Markov chains in discrete or continuous time are widely used to model phenomena in the social, physical and life sciences. In many cases, the model can feature a large state space, with extreme differences between the fastest and slowest transition timescales. Analysis of such ill-conditioned models is often intractable with finite precision linear algebra techniques. In this contribution, we propose a solution to this problem, namely partial graph transformation, to iteratively eliminate and renormalize states, producing a low-rank Markov chain from an ill-conditioned initial model. We show that the error induced by this procedure can be minimized by retaining both the renormalized nodes that represent metastable superbasins, and those through which reactive pathways concentrate, i.e. the dividing surface in the discrete state space. This procedure typically returns a much lower rank model, where trajectories can be efficiently generated with kinetic path sampling. We apply this approach to an ill-conditioned Markov chain for a model multi-community system, measuring the accuracy by direct comparison with trajectories and transition statistics. This article is part of a discussion meeting issue 'Supercomputing simulations of advanced materials'.

Stochastic paths controlling speed and dissipation.

Natural processes occur in a finite amount of time and dissipate energy, entropy, and matter. Near equilibrium, thermodynamic intuition suggests that fast irreversible processes will dissipate more energy and entropy than slow quasistatic processes connecting the same initial and final states. For small systems, recently discovered thermodynamic speed limits suggest that faster processes will dissipate more than slower processes. Here, we test the hypothesis that this relationship between speed and dissipation holds for stochastic paths far from equilibrium. To analyze stochastic paths on finite timescales, we derive an exact expression for the path probabilities of continuous-time Markov chains from the path summation solution to the master equation. We present a minimal model for a driven system in which relative energies of the initial and target states control the speed, and the nonequilibrium currents of a cycle control the dissipation. Although the hypothesis holds near equilibrium, we find that faster processes can dissipate less under far-from-equilibrium conditions because of strong currents. This model serves as a minimal prototype for designing kinetics to sculpt the nonequilibrium path space so that faster paths produce less dissipation.

Nearly reducible finite Markov chains: Theory and algorithms.

Finite Markov chains, memoryless random walks on complex networks, appear commonly as models for stochastic dynamics in condensed matter physics, biophysics, ecology, epidemiology, economics, and elsewhere. Here, we review exact numerical methods for the analysis of arbitrary discrete- and continuous-time Markovian networks. We focus on numerically stable methods that are required to treat nearly reducible Markov chains, which exhibit a separation of characteristic timescales and are therefore ill-conditioned. In this metastable regime, dense linear algebra methods are afflicted by propagation of error in the finite precision arithmetic, and the kinetic Monte Carlo algorithm to simulate paths is unfeasibly inefficient. Furthermore, iterative eigendecomposition methods fail to converge without the use of nontrivial and system-specific preconditioning techniques. An alternative approach is provided by state reduction procedures, which do not require additional a priori knowledge of the Markov chain. Macroscopic dynamical quantities, such as moments of the first passage time distribution for a transition to an absorbing state, and microscopic properties, such as the stationary, committor, and visitation probabilities for nodes, can be computed robustly using state reduction algorithms. The related kinetic path sampling algorithm allows for efficient sampling of trajectories on a nearly reducible Markov chain. Thus, all of the information required to determine the kinetically relevant transition mechanisms, and to identify the states that have a dominant effect on the global dynamics, can be computed reliably even for computationally challenging models. Rare events are a ubiquitous feature of realistic dynamical systems, and so the methods described herein are valuable in many practical applications.

Numerical analysis of first-passage processes in finite Markov chains exhibiting metastability.

We describe state-reduction algorithms for the analysis of first-passage processes in discrete- and continuous-time finite Markov chains. We present a formulation of the graph transformation algorithm that allows for the evaluation of exact mean first-passage times, stationary probabilities, and committor probabilities for all nonabsorbing nodes of a Markov chain in a single computation. Calculation of the committor probabilities within the state-reduction formalism is readily generalizable to the first hitting problem for any number of alternative target states. We then show that a state-reduction algorithm can be formulated to compute the expected number of times that each node is visited along a first-passage path. Hence, all properties required to analyze the first-passage path ensemble (FPPE) at both a microscopic and macroscopic level of detail, including the mean and variance of the first-passage time distribution, can be computed using state-reduction methods. In particular, we derive expressions for the probability that a node is visited along a direct transition path, which proceeds without returning to the initial state, considering both the nonequilibrium and equilibrium (steady-state) FPPEs. The reactive visitation probability provides a rigorous metric to quantify the dynamical importance of a node for the productive transition between two endpoint states and thus allows the local states that facilitate the dominant transition mechanisms to be readily identified. The state-reduction procedures remain numerically stable even for Markov chains exhibiting metastability, which can be severely ill-conditioned. The rare event regime is frequently encountered in realistic models of dynamical processes, and our methodology therefore provides valuable tools for the analysis of Markov chains in practical applications. We illustrate our approach with numerical results for a kinetic network representing a structural transition in an atomic cluster.

Graph transformation and shortest paths algorithms for finite Markov chains.

The graph transformation (GT) algorithm robustly computes the mean first-passage time to an absorbing state in a finite Markov chain. Here we present a concise overview of the iterative and block formulations of the GT procedure and generalize the GT formalism to the case of any path property that is a sum of contributions from individual transitions. In particular, we examine the path action, which directly relates to the path probability, and analyze the first-passage path ensemble for a model Markov chain that is metastable and therefore numerically challenging. We compare the mean first-passage path action, obtained using GT, with the full path action probability distribution simulated efficiently using kinetic path sampling, and with values for the highest-probability paths determined by the recursive enumeration algorithm (REA). In Markov chains representing realistic dynamical processes, the probability distributions of first-passage path properties are typically fat-tailed and therefore difficult to converge by sampling, which motivates the use of exact and numerically stable approaches to compute the expectation. We find that the kinetic relevance of the set of highest-probability paths depends strongly on the metastability of the Markov chain, and so the properties of the dominant first-passage paths may be unrepresentative of the global dynamics. Use of a global measure for edge costs in the REA, based on net productive fluxes, allows the total reactive flux to be decomposed into a finite set of contributions from simple flux paths. By considering transition flux paths, a detailed quantitative analysis of the relative importance of competing dynamical processes is possible even in the metastable regime.

Optimal dimensionality reduction of Markov chains using graph transformation.

Markov chains can accurately model the state-to-state dynamics of a wide range of complex systems, but the underlying transition matrix is ill-conditioned when the dynamics feature a separation of timescales. Graph transformation (GT) provides a numerically stable method to compute exact mean first passage times (MFPTs) between states, which are the usual dynamical observables in continuous-time Markov chains (CTMCs). Here, we generalize the GT algorithm to discrete-time Markov chains (DTMCs), which are commonly estimated from simulation data, for example, in the Markov state model approach. We then consider the dimensionality reduction of CTMCs and DTMCs, which aids model interpretation and facilitates more expensive computations, including sampling of pathways. We perform a detailed numerical analysis of existing methods to compute the optimal reduced CTMC, given a partitioning of the network into metastable communities (macrostates) of nodes (microstates). We show that approaches based on linear algebra encounter numerical problems that arise from the requisite metastability. We propose an alternative approach using GT to compute the matrix of intermicrostate MFPTs in the original Markov chain, from which a matrix of weighted intermacrostate MFPTs can be obtained. We also propose an approximation to the weighted-MFPT matrix in the strongly metastable limit. Inversion of the weighted-MFPT matrix, which is better conditioned than the matrices that must be inverted in alternative dimensionality reduction schemes, then yields the optimal reduced Markov chain. The superior numerical stability of the GT approach therefore enables us to realize optimal Markovian coarse-graining of systems with rare event dynamics.

Rare events and first passage time statistics from the energy landscape.

We analyze the probability distribution of rare first passage times corresponding to transitions between product and reactant states in a kinetic transition network. The mean first passage times and the corresponding rate constants are analyzed in detail for two model landscapes and the double funnel landscape corresponding to an atomic cluster. Evaluation schemes based on eigendecomposition and kinetic path sampling, which both allow access to the first passage time distribution, are benchmarked against mean first passage times calculated using graph transformation. Numerical precision issues severely limit the useful temperature range for eigendecomposition, but kinetic path sampling is capable of extending the first passage time analysis to lower temperatures, where the kinetics of interest constitute rare events. We then investigate the influence of free energy based state regrouping schemes for the underlying network. Alternative formulations of the effective transition rates for a given regrouping are compared in detail to determine their numerical stability and capability to reproduce the true kinetics, including recent coarse-graining approaches that preserve occupancy cross correlation functions. We find that appropriate regrouping of states under the simplest local equilibrium approximation can provide reduced transition networks with useful accuracy at somewhat lower temperatures. Finally, a method is provided to systematically interpolate between the local equilibrium approximation and exact intergroup dynamics. Spectral analysis is applied to each grouping of states, employing a moment-based mode selection criterion to produce a reduced state space, which does not require any spectral gap to exist, but reduces to gap-based coarse graining as a special case. Implementations of the developed methods are freely available online.

Efficient and exact sampling of transition path ensembles on Markovian networks.

The problem of flickering trajectories in standard kinetic Monte Carlo (kMC) simulations prohibits sampling of the transition path ensembles (TPEs) on Markovian networks representing many slow dynamical processes of interest. In the present contribution, we overcome this problem using knowledge of the metastable macrostates, determined by an unsupervised community detection algorithm, to perform enhanced sampling kMC simulations. We implement two accelerated kMC methods to simulate the nonequilibrium stochastic dynamics on arbitrary Markovian networks, namely, weighted ensemble (WE) sampling and kinetic path sampling (kPS). WE-kMC utilizes resampling in pathway space to maintain an ensemble of representative trajectories covering the state space, and kPS utilizes graph transformation to simplify the description of an escape trajectory from a trapping energy basin. Both methods sample individual trajectories governed by the linear master equation with the correct statistical frequency. We demonstrate that they allow for efficient estimation of the time-dependent occupation probability distributions for the metastable macrostates, and of TPE statistics, such as committor functions and first passage time distributions. kPS is particularly attractive, since its efficiency is essentially independent of the degree of metastability, and we suggest how the algorithm could be coupled with other enhanced sampling methodologies. We illustrate our approach with results for a network representing the folding transition of a tryptophan zipper peptide, which exhibits a separation of characteristic timescales. We highlight some salient features of the dynamics, most notably, strong deviations from two-state behavior, and the existence of multiple competing mechanisms.

Energy Landscapes of Deoxyxylo- and Xylo-Nucleic Acid Octamers.

Artificial analogues of the natural nucleic acids have attracted interest as a diverse class of information storage molecules capable of self-replication. In this study, we use the computational potential energy landscape framework to investigate the structural and dynamical properties of xylo- and deoxyxylo-nucleic acids (XyNA and dXyNA), which are derived from their respective RNA and DNA analogues by inversion of a single chiral center in the sugar moiety of the nucleotides. For an octameric XyNA sequence and the analogue dXyNA, we observe facile conformational transitions between a left-handed helix, which is the free energy global minimum, and a ladder-type structure with approximately zero helicity. The competing ensembles are better separated in the dXyNA, making it a more suitable candidate for a molecular switch, whereas the XyNA exhibits additional flexibility. Both energy landscapes exhibit greater frustration than we observe in RNA or DNA, in agreement with the higher degree of optimization expected from the principle of minimal frustration in evolved biomolecules.

Energy Landscapes and Hybridization Pathways for DNA Hexamer Duplexes.

Strand hybridization is not only a fundamental molecular mechanism underlying the biological functions of nucleic acids but is also a key step in the design of efficient nanodevices. Despite recent efforts, the microscopic rules governing the hybridization mechanisms remain largely unknown. In this study, we exploit the energy landscape framework to assess how sequence-specificity modulates the hybridization mechanisms in DNA. We find that GG-tracts hybridize much more rapidly compared to GC-tracts, via either zippering or slithering pathways. For the hybridization of GG-tracts, both zippering and slithering mechanisms appear to be kinetically relevant. In contrast, for the GC-tracts, the zippering mechanism is dominant. Our work reveals that even for the relatively small systems considered, the energy landscapes feature multiple metastable states and kinetic traps, which is at odds with the conventional "all-or-nothing" model of DNA hybridization formulated on the basis of thermodynamic arguments alone. Interestingly, entropic effects are found to play an important role in determining the thermal stability of competing conformational ensembles and in determining the preferred hybridization pathways.

Identifying mechanistically distinct pathways in kinetic transition networks.

We present an implementation of a scalable path deviation algorithm to find the k most kinetically relevant paths in a transition network, where each path is distinguished on the basis of having a distinct rate-limiting edge. The potential of the algorithm to identify distinct pathways that exist in separate regions of the configuration space is demonstrated for two benchmark systems with double-funnel energy landscapes, namely a model "three-hole" network embedded on a 2D potential energy surface and the cluster of 38 Lennard-Jones atoms (LJ38). The path cost profiles for the interbasin transitions of the two systems reflect the contrasting nature of the landscapes. There are multiple well-defined pathway ensembles for the three-hole system, whereas the transition in LJ38 effectively involves a single ensemble of pathways via disordered structures. A by-product of the algorithm is a set of edges that constitute a cut of the network, which is related to the discrete analog of a transition dividing surface. The algorithm ought to be useful for determining the existence, or otherwise, of competing mechanisms in large stochastic network models of dynamical processes and for assessing the kinetic relevance of distinguishable ensembles of pathways. This capability will provide insight into conformational transitions in biomolecules and other complex slow processes.

Approximating the Shifted Hartree-Exchange-Correlation Potential in Direct Energy Kohn-Sham Theory.

Levy and Zahariev [Phys. Rev. Lett. 113 113002 (2014)] have proposed a new approach for performing density functional theory calculations, termed direct energy Kohn-Sham (DEKS) theory. In this approach, the electronic energy equals the sum of orbital energies, obtained from Kohn-Sham-like orbital equations involving a shifted Hartree-exchange-correlation potential, which must be approximated. In the present study, density scaling homogeneity considerations are used to facilitate DEKS calculations on a series of atoms and molecules, leading to three nonlocal approximations to the shifted potential. The first two rely on preliminary Kohn-Sham calculations using a standard generalized gradient approximation (GGA) exchange-correlation functional and the results illustrate the benefit of describing the dominant Hartree component of the shift exactly. A uniform electron gas analysis is used to eliminate the need for these preliminary Kohn-Sham calculations, leading to a potential with an unconventional form that yields encouraging results, providing strong motivation for further research in DEKS theory.

GATA2 regulates the erythropoietin receptor in t(12;21) ALL.

The t(12;21) (p13;q22) chromosomal translocation resulting in the ETV6/RUNX1 fusion gene is the most frequent structural cytogenetic abnormality in children with acute lymphoblastic leukemia (ALL). The erythropoietin receptor (EPOR), usually associated with erythroid progenitor cells, is highly expressed in ETV6/RUNX1 positive cases compared to other B-lineage ALL subtypes. Gene expression analysis of a microarray database and direct quantitative analysis of patient samples revealed strong correlation between EPOR and GATA2 expression in ALL, and higher expression of GATA2 in t(12;21) patients. The mechanism of EPOR regulation was mainly investigated using two B-ALL cell lines: REH, which harbor and express the ETV6/RUNX1 fusion gene; and NALM-6, which do not. Expression of EPOR was increased in REH cells compared to NALM-6 cells. Moreover, of the six GATA family members only GATA2 was differentially expressed with substantially higher levels present in REH cells. GATA2 was shown to bind to the EPOR 5'-UTR in REH, but did not bind in NALM-6 cells. Overexpression of GATA2 led to an increase in EPOR expression in REH cells only, indicating that GATA2 regulates EPOR but is dependent on the cellular context. Both EPOR and GATA2 are hypomethylated and associated with increased mRNA expression in REH compared to NALM-6 cells. Decitabine treatment effectively reduced methylation of CpG sites in the GATA2 promoter leading to increased GATA2 expression in both cell lines. Although Decitabine also reduced an already low level of methylation of the EPOR in NALM-6 cells there was no increase in EPOR expression. Furthermore, EPOR and GATA2 are regulated post-transcriptionally by miR-362 and miR-650, respectively. Overall our data show that EPOR expression in t(12;21) B-ALL cells, is regulated by GATA2 and is mediated through epigenetic, transcriptional and post-transcriptional mechanisms, contingent upon the genetic subtype of the disease.

POU2F1 activity regulates HOXD10 and HOXD11 promoting a proliferative and invasive phenotype in head and neck cancer.

HOX genes are master regulators of organ morphogenesis and cell differentiation during embryonic development, and continue to be expressed throughout post-natal life. To test the hypothesis that HOX genes are dysregulated in head and neck squamous cell carcinoma (HNSCC) we defined their expression profile, and investigated the function, transcriptional regulation and clinical relevance of a subset of highly expressed HOXD genes. Two HOXD genes, D10 and D11, showed strikingly high levels in HNSCC cell lines, patient tumor samples and publicly available datasets. Knockdown of HOXD10 in HNSCC cells caused decreased proliferation and invasion, whereas knockdown of HOXD11 reduced only invasion. POU2F1 consensus sequences were identified in the 5' DNA of HOXD10 and D11. Knockdown of POU2F1 significantly reduced expression of HOXD10 and D11 and inhibited HNSCC proliferation. Luciferase reporter constructs of the HOXD10 and D11 promoters confirmed that POU2F1 consensus binding sites are required for optimal promoter activity. Utilizing patient tumor samples a significant association was found between immunohistochemical staining of HOXD10 and both the overall and the disease-specific survival, adding further support that HOXD10 is dysregulated in head and neck cancer. Additional studies are now warranted to fully evaluate HOXD10 as a prognostic tool in head and neck cancers.

The matricellular protein CCN3 regulates NOTCH1 signalling in chronic myeloid leukaemia.

Deregulated NOTCH1 has been reported in lymphoid leukaemia, although its role in chronic myeloid leukaemia (CML) is not well established. We previously reported BCR-ABL down-regulation of a novel haematopoietic regulator, CCN3, in CML; CCN3 is a non-canonical NOTCH1 ligand. This study characterizes the NOTCH1­CCN3 signalling axis in CML. In K562 cells, BCR-ABL silencing reduced full-length NOTCH1 (NOTCH1-FL) and inhibited the cleavage of NOTCH1 intracellular domain (NOTCH1-ICD), resulting in decreased expression of the NOTCH1 targets c-MYC and HES1. K562 cells stably overexpressing CCN3 (K562/CCN3) or treated with recombinant CCN3(rCCN3) showed a significant reduction in NOTCH1 signalling (> 50% reduction in NOTCH1-ICD, p < 0.05).Gamma secretase inhibitor (GSI), which blocks NOTCH1 signalling, reduced K562/CCN3 colony formation but increased that of K562/control cells. GSI combined with either rCCN3 or imatinib reduced K562 colony formation with enhanced reduction of NOTCH1 signalling observed with combination treatments. We demonstrate an oncogenic role for NOTCH1 in CML and suggest that BCR-ABL disruption of NOTCH1­CCN3 signalling contributes to the pathogenesis of CML.

AKT in stromal fibroblasts controls invasion of epithelial cells.

The tumour microenvironment has an important role in cancer progression and recent reports have proposed that stromal AKT is activated and regulates tumourigenesis and invasion. We have shown, by immuno-fluorescent analysis of oro-pharyngeal cancer biopsies, an increase in AKT activity in tumour associated stromal fibroblasts compared to normal stromal fibroblasts. Using organotypic raft co-cultures, we show that activation of stromal AKT can induce the invasion of keratinocytes expressing the HPV type 16 E6 and E7 proteins, in a Keratinocyte Growth Factor (KGF) dependent manner. By depleting stromal fibroblasts of each of the three AKT isoforms independently, or through using isoform specific inhibitors, we determined that stromal AKT2 is an essential regulator of invasion and show in oro-pharyngeal cancers that AKT2 specific phosphorylation events are also identified in stromal fibroblasts. Depletion of stromal AKT2 inhibits epithelial invasion through activating a protective pathway counteracting KGF mediated invasions. AKT2 depletion in fibroblasts stimulates the cleavage and release of IL1B from stromal fibroblasts resulting in down-regulation of the KGF receptor (fibroblast growth factor receptor 2B (FGFR2B)) expression in the epithelium. We also show that high IL1B is associated with increased overall survival in a cohort of patients with oro-pharyngeal cancers. Our findings demonstrate the importance of stromal derived growth factors and cytokines in regulating the process of tumour cell invasion.

Entinostat prevents leukemia maintenance in a collaborating oncogene-dependent model of cytogenetically normal acute myeloid leukemia.

The incidence of refractory acute myeloid leukemia (AML) is on the increase due in part to an aging population that fails to respond to traditional therapies. High throughput genomic analysis promises better diagnosis, prognosis, and therapeutic intervention based on improved patient stratification. Relevant preclinical models are urgently required to advance drug development in this area. The collaborating oncogenes, HOXA9 and MEIS1, are frequently co-overexpressed in cytogenetically normal AML (CN-AML), and a conditional transplantation mouse model was developed that demonstrated oncogene dependency and expression levels comparable to CN-AML patients. Integration of gene signatures obtained from the mouse model and a cohort of CN-AML patients using statistically significant connectivity map analysis identified Entinostat as a drug with the potential to alter the leukemic condition toward the normal state. Ex vivo treatment of leukemic cells, but not age-matched normal bone marrow controls, with Entinostat validated the gene signature and resulted in reduced viability in liquid culture, impaired colony formation, and loss of the leukemia initiating cell. Furthermore, in vivo treatment with Entinostat resulted in prolonged survival of leukemic mice. This study demonstrates that the HDAC inhibitor Entinostat inhibits disease maintenance and prolongs survival in a clinically relevant murine model of cytogenetically normal AML.

Detection and analysis of DNA methylation by pyrosequencing.

Pyrosequencing is a "sequencing by synthesis" technique which can be used to quantify DNA methylation at specific CpG sites within the target region of interest. Biotin labelled polymerase chain reaction (PCR) products form the template for base-pair nucleotide incorporation causing a light emitting cascade reaction resulting in the formation of a pyrogram and the calculation of the percentage methylation for each site. Prior to pyrosequencing, it is essential to bisulphite-convert the DNA sample and then perform locus-specific PCR for the region of interest. One of the PCR primers needs to be biotinylated and a separate sequencing primer is required for the pyrosequencing itself.