List-decoding methods for inferring polynomials in finite dynamical gene network models

Janis Dingel, Olgica Milenkovic

Research output: Contribution to journalArticle


Motivation: The problem of reverse engineering the dynamics of gene expression profiles is of focal importance in systems biology. Due to noise and the inherent lack of sufficiently large datasets generated via high-throughput measurements, known reconstruction frameworks based on dynamical systems models fail to provide adequate settings for network analysis. This motivates the study of new approaches that produce stochastic lists of explanations for the observed network dynamics that can be efficiently inferred from small sample sets and in the presence of errors. Results: We introduce a novel algebraic modeling framework, termed stochastic polynomial dynamical systems (SPDSs) that can capture the dynamics of regulatory networks based on microarray expression data. Here, we refer to dynamics of the network as the trajectories of gene expression profiles over time. The model assumes that the expression data is quantized in a manner that allows for imposing a finite field structure on the observations, and the existence of polynomial update functions for each gene in the network. The underlying reverse engineering algorithm is based on ideas borrowed from coding theory, and in particular, list-decoding methods for so called Reed-Muller codes. The list-decoding method was tested on synthetic data and on microarray expression measurements from the M3D database, corresponding to a subnetwork of the Escherichia coli SOS repair system, as well as on the complete transcription factor network, available at RegulonDB. The results show that SPDSs constructed via list-decoders significantly outperform other algebraic reverse engineering methods, and that they also provide good guidelines for estimating the influence of genes on the dynamics of the network.

Original languageEnglish (US)
Pages (from-to)1686-1693
Number of pages8
Issue number13
StatePublished - Jun 29 2009

ASJC Scopus subject areas

  • Statistics and Probability
  • Biochemistry
  • Molecular Biology
  • Computer Science Applications
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'List-decoding methods for inferring polynomials in finite dynamical gene network models'. Together they form a unique fingerprint.

  • Cite this