Reconstruction of Gene Regulatory Networks under the Finite State Linear Model

Dace Ruklisa[1],[3] (
Alvis Brazma[2] (
Juris Viksna[1],[4] (

[1]Institute of Mathematics and Computer Science, University of Latvia, Rainis boulevard 29, Riga LV-1459, Latvia
[2]European Bioinformatics Institute, Wellcome Trust Genome Campus, Hinxton, Cambridge, CB10 1SD, UK
[3]supported by ESF (European Social Fund) project 2004/0001/VPD1/ESF/PIAA/04/NP/ and Latvian Council of Science grant 05.1535
[4]supported by EPSRC grant EP/C00373X/1 and Latvian Council of Science grant 05.1535


We study the Finite State Linear Model (FSLM) for modelling gene regulatory networks proposed by A. Brazma and T. Schlitt in [4]. The model incorporates biologically intuitive gene regulatory mechanism similar to that in Boolean networks, and can describe also the continuous changes in protein levels. We consider several theoretical properties of this model; in particular we show that the problem whether a particular gene will reach an active state is algorithmically unsolvable. This imposes some practical difficulties in simulation and reverse engineering of FSLM networks. Nevertheless, our simulation experiments show that sufficiently many of FSLM networks exhibit a regular behaviour and that the model is still quite adequate to describe biological reality. We also propose a comparatively efficient O(2K nK+1 M2K m log m ) time algorithm for reconstruction of FSLM networks from experimental data. Experiments on reconstruction of random networks are performed to estimate the running time of the algorithm in practice, as well as the number of measurements needed for successful network reconstruction.

[ Full-text PDF | Table of Contents ]

Japanese Society for Bioinformatics