Graph Algorithms for Gene Regulatory Network Minimization, Robustness and Evolvability

As an increasing amount of genomic data becomes available, there is a need for powerful computational and algorithmic approaches that successfully manage to analyse them in a large scale, and provide solid establishments for their profound interpretation. The current thesis is concerned with the emerging area of gene and biochemical regulatory networks, and provides computational methods for analysing them under various perspectives. To this end, the results presented here follow two different directions. The first (chapter 2) deals with the minimization of gene regulatory networks. We introduce the notion of network floods, a combinatorial network approach that aims to reveal the core cell regulatory structure in the presence of external stimuli that trigger a cell response. Our method is evaluated against both synthetic and real biological datasets. The second (chapter 3) deals with the already studied notions of robustness and evolvability in gene regulatory networks, and provides our perspective in our attempt to answer questions that examine these two metrics both independently, and jointly. In this direction, we develop a formal language, and provide efficient algorithms for addressing such questions, using synthetic datasets.