Discrete models are popular in a wide variety of scientific applications, such as gene-regulatory networks, epidemics over social contact graphs, algorithms for gene function inference, and many numerical methods. The framework of graph dynamical systems (GDSs) naturally captures many parallel and sequential, iterative models and algorithms in a mathematically precise way that is amenable to rigorous analysis. The underlying theme of this proposal is the further development of a theoretical framework and body of mathematical results of these time-discrete dynamical systems over networks. The mathematics should be of interest in its own right, yet help advance applications involving discrete models and iterative computational algorithms. It will allow for better insight into validation aspects and general properties of algorithms from computational systems biology, which should lead to the construction of improved models and algorithms in this field and beyond. With the current developments in scientific computing and applications, this non-traditional area of applied mathematics is in a keen need of further advances. Moreover, the analysis and the results constitute natural underpinnings for the theory of stochastic GDSs, a construct of great interest to many application areas that is gaining popularity.
The time-discrete dynamical systems over networks that the investigator studies arise in systems biology and scientific computing from gene networks, to data mining, to epidemiology. Not only are these systems popular as models, but many algorithms are built on top of these models. Such algorithms are frequently poorly understood, and algorithm validation is usually approached by way of numerical experiments that shed little light on the fundamental analytic properties of the algorithms. One basic question is how to relate the constituents of the system (e.g., function type, network structure, update mechanism) to the resulting dynamics, especially with regard to stability analysis. In this project, the investigator will primarily focus on two specific system aspects, function structure and update sequence. This effectively comes down to two classes of graph dynamical systems in which the investigator has expertise: (1) Boolean networks (synchronous), and (2) sequential dynamical systems (asynchronous). For each of these areas, the investigator has a specific plan for the theory to be developed, as well as a specific application from computational systems biology in mind. For this first area, the newly introduced concept of nested canalyzing depth of functions will be studied, and with the application of reverse engineering gene networks in mind. For the second area, the dependence on the update sequence and the initial states on the phase space structure will be studied, with the goal of using this to develop quantitative stability measures that can be applied to iterative algorithms such as gene annotative methods.
This project funded the Principal Investigator (PI), along with one PhD student, and two undergraduate students, one whom has since graduated and entered into a PhD program. Thus far, it has resulted in over four publications, one book chapter, and one submitted paper, though there are more than this currently in preparation, as this remains an ongoing project. Two graduate students are currently writing their theses on topics from this project, and two former graduate students have been co-authors on several of the aforementioned papers. The central topic involves discrete finite dynamical systems on graphs or networks, and their stability. For example, when the local updates are asynchronous, then behind the scenes of their periodic function iteration is a "cyclic" partial order, called a toric partially ordered set, or "toric poset." Part of this project consists of developing the mathematical framework needed to study stability of these asynchronous networks. The other part is applying this to the actual networks, which remains an ongoing project. As another example, this project has looked at networks where the local functions are nested canalizing, which means that one can recursively pick off nodes that can completely determine the output. One can think of these nodes as having "shut-off values," that activate depending on certain input values. One can then ask how this determines the stability of the network dynamics, and how this can be described in an algebraic geometry setting, rather than just simple Boolean logic. More details can be found in a recent paper, book chapter, and several papers in preparation.
