Complexity of Patterns Generated by Genetic Circuits and Pfaffian Functions
by
Sergei Vakulenko
Institute of Mechanical Engineering Problems, St.Petersbourg
Coauthors: D.Grigoriev

Genetic circuit is a computational model which describes an interaction of genes. Each gate of the circuit involves a suitable real analytic function which approximates the threshold function (expressing an activation of a gene). Three types of results are obtained

First, it is proved that any function (treated as a pattern) can be approximated by an appropriate genetic circuit.

Second, we study the complexity of functions computed by a circuit. Based on the estimates for Pfaffian functions due to A.Khovanskii, we establish the upper bounds on the numver of zeroes and on the number of the connected components of the preimages of an interval for functions computed by a genetic circuit via the complexity of the circuit.

The third series of results deal with the stable behavoiur of functions computed by a genetic circuit when its complexity tends to infinity. The bounds on the probability of the function to stay in a given set are provided (this corresponds to the survival probability). As a consequence it appears that the greater is the degree of the graph of the circuit the higher is the survival probability.

Date received: March 8, 2003