Library

Description: Finding metastable sets as dominant structures of Markov processes has been shown to be especially useful in modeling interesting slow dynamics of various real world complex processes. Furthermore, coarse graining of such processes based on their dominant structures leads to better understanding and dimension reduction of observed systems. However, in many cases, e.g. for nonreversible Markov processes, dominant structures are often not formed by metastable sets but by important cycles or mixture of both. This paper aims at understanding and identifying these different types of dominant structures for reversible as well as nonreversible ergodic Markov processes. Our algorithmic approach generalizes spectral based methods for reversible process by using Schur decomposition techniques which can tackle also nonreversible cases. We illustrate the mathematical construction of our new approach by numerical experiments.

Description: Human mobility always had a great influence on the spreading of cultural, social and technological ideas. Developing realistic models that allow for a better understanding, prediction and control of such coupled processes has gained a lot of attention in recent years. However, the modeling of spreading processes that happened in ancient times faces the additional challenge that available knowledge and data is often limited and sparse. In this paper, we present a new agent-based model for the spreading of innovations in the ancient world that is governed by human movements. Our model considers the diffusion of innovations on a spatial network that is changing in time, as the agents are changing their positions. Additionally, we propose a novel stochastic simulation approach to produce spatio-temporal realizations of the spreading process that are instructive for studying its dynamical properties and exploring how different influences affect its speed and spatial evolution.

Description: Many real-world processes can naturally be modeled as systems of interacting agents. However, the long-term simulation of such agent-based models is often intractable when the system becomes too large. In this paper, starting from a stochastic spatio-temporal agent-based model (ABM), we present a reduced model in terms of stochastic PDEs that describes the evolution of agent number densities for large populations. We discuss the algorithmic details of both approaches; regarding the SPDE model, we apply Finite Element discretization in space which not only ensures efficient simulation but also serves as a regularization of the SPDE. Illustrative examples for the spreading of an innovation among agents are given and used for comparing ABM and SPDE models.

Description: We present a comprehensive theory for analysis and understanding of transition events between an initial set A and a target set B for general ergodic finite-state space Markov chains or jump processes, including random walks on networks as they occur, e.g., in Markov State Modelling in molecular dynamics. The theory allows us to decompose the probability flow generated by transition events between the sets A and B into the productive part that directly flows from A to B through reaction pathways and the unproductive part that runs in loops and is supported on cycles of the underlying network. It applies to random walks on directed networks and nonreversible Markov processes and can be seen as an extension of Transition Path Theory. Information on reaction pathways and unproductive cycles results from the stochastic cycle decomposition of the underlying network which also allows to compute their corresponding weight, thus characterizing completely which structure is used how often in transition events. The new theory is illustrated by an application to a Markov State Model resulting from weakly damped Langevin dynamics where the unproductive cycles are associated with periodic orbits of the underlying Hamiltonian dynamics.

Description: The problem of decomposing networks into modules (or clusters) has gained much attention in recent years, as it can account for a coarsegrained description of complex systems, often revealing functional subunits of these systems. A variety of module detection algorithms have been proposed, mostly oriented towards finding hard partitionings of undirected networks. Despite the increasing number of fuzzy clustering methods for directed networks, many of these approaches tend to neglect important directional information. In this paper, we present a novel random walk based approach for finding fuzzy partitions of directed, weighted networks, where edge directions play a crucial role in defining how well nodes in a module are interconnected. We will show that cycle decomposition of a random walk process connects the notion of network modules and information transport in a network, leading to a new, symmetric measure of node communication. Finally, we will use this measure to introduce a communication graph, for which we will show that although being undirected it inherits all necessary information about modular structures from the original network.

Description: Background: Although several studies have provided insights into the role of long non-coding RNAs (lncRNAs), the majority of them have unknown function. Recent evidence has shown the importance of both lncRNAs and chromatin interactions in transcriptional regulation. Although network-based methods, mainly exploiting gene-lncRNA co-expression, have been applied to characterize lncRNA of unknown function by means of ’guilt-by-association’, no strategy exists so far which identifies mRNA-lncRNA functional modules based on the 3D chromatin interaction graph. Results: To better understand the function of chromatin interactions in the context of lncRNA-mediated gene regulation, we have developed a multi-step graph analysis approach to examine the RNA polymerase II ChIA-PET chromatin interaction network in the K562 human cell line. We have annotated the network with gene and lncRNA coordinates, and chromatin states from the ENCODE project. We used centrality measures, as well as an adaptation of our previously developed Markov State Models (MSM) clustering method, to gain a better understanding of lncRNAs in transcriptional regulation. The novelty of our approach resides in the detection of fuzzy regulatory modules based on network properties and their optimization based on co-expression analysis between genes and gene-lncRNA pairs. This results in our method returning more bona fide regulatory modules than other state-of-the art approaches for clustering on graphs. Conclusions: Interestingly, we find that lncRNA network hubs tend to be significantly enriched in evolutionary conserved lncRNAs and enhancer-like functions. We validated regulatory functions for well known lncRNAs, such as MALAT1 and the enhancer-like lncRNA FALEC. In addition, by investigating the modular structure of bigger components we mine putative regulatory functions for uncharacterized lncRNAs.