Reconstruction of gene regulatory networks under the finite state linear model

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(2(K)n(K+1)M(2K)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.