A list-decoding approach for inferring the dynamics of gene regulatory networks

We propose a novel algebraic method for reverse engineering the dynamics of gene regulatory networks of known topology, based on list-decoding and iterative model refinement algorithms. The crux of our approach is to describe the update functions for gene expressions in terms of polynomials over finite fields, or more precisely, codewords of Reed-Muller (RM) codes. In this setting, errors, missing data points, and small sample sizes of the measurements are accounted for via list-decoding of RM codes. We test the performance of the new method both on synthetic data and a regulatory sub-net of the E. coli gene control network responsible for DNA repair. The expression profiles used in the study are obtained through data fusion techniques over the Many Microbe Microarray Database. The list-decoding approach offers significant performance improvements over previously known algebraic methods, such as those based on Grobner bases techniques.