Mathematical Models and Algorithms for Genetic Regulatory Networks

This dissertation, "Mathematical Models and Algorithms for Genetic Regulatory Networks" by Shuqin, Zhang, 張淑芹, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author. Abstract: Abstract of thesis entitled MATHEMATICAL MODELS AND ALGORITHMS FOR GENETIC REGULATORY NETWORKS submitted by ZHANG Shu-Qin for the degree of Doctor of Philosophy at The University of Hong Kong in August 2007 Genetic regulatory network is an important research topic in bioinformat- ics, which considers the on-o(R) switches and rheostats of a cell operating at the gene level. Mathematical modeling and computation are indispensable in such studies, especially for the complex patterns of behavior which needs high indus- trialpayo(R)sandisdiculttogettheinformationthroughexperimentalmethods. Booleannetworks(BNs)andprobabilisticBooleannetworks(PBNs)areproposed to model the interactions among the genes and have received much attention in the biophysics community. The study in this thesis is based on the BN and PBN models. With the BN model, several algorithms using gene ordering and feedback vertex sets are devel- opedtoidentifysingletonattractorsandsmallattractorswhichcorrespondtocell types and cell states. The average case time complexities of some proposed al- gorithms are analyzed. Extensive computational experiments are also performed which are in good agreement with the theoretical results. A simple and complete proofforshowingthatndinganattractorwiththeshortestperiodisNP-hardis given. Finding global states incoming to a specied global state is useful for the preprocessingofndingasequenceofcontrolactionsinBooleannetworksandfor identifying the basin of attraction for a given attractor. This problem is shown to be NP-hard in general. New algorithms based on the algorithms for ndingsmall attractors are developed, which are much faster than the naive exhaustive search-based algorithm. Based on the PBN model, an ecient method for the construction of the sparse transition probability matrix is proposed. Power method is then applied to compute the steady-state probability distribution. With this method, the sensitivity of the steady-state distribution to the inuences of input genes, gene connections and Boolean functions is studied. Simulation results are given to illustrate the method and to demonstrate the steady-state analysis. An approxi- mation method is proposed to further reduce the time complexity for computing the steady-state probability distribution by neglecting some BNs with very small probabilities during the construction of the transition probability matrix. An error analysis of this approximation method is givenand theoretical result on the distribution of BNs in a PBN with at most two Boolean functions for one gene is also presented. Numerical experiments are given to demonstrate the eciency of the proposed method. The ultimate goal of studying the long-term behavior of the genetic regula- tory network is to study the control strategies such that the system can go into the desirable states with larger probabilities. A control model is also proposed for gene intervention here. The problem is formulated as a minimization prob- lem with integer variables to minimize the amount of control cost for a genetic network over a given period of time such that the probabilities of obtaining the target states are as large as possible. Experimental results show that the pro- posed formulation is ecient and e(R)ective for solving the control problem of gene intervention. DOI: 10.5353/th_b3884282 Subjects: Genetics - Mathematical models Algorithms Bioinformatics