Probabilistic automata as a model for epigenesis of cellular networks

Probabilistic automata are compared with deterministic ones in simulations of growing networks made of dividing interconnected cells. On examples of chains, wheels and tree-like structures made of large numbers of cells it is shown that the number of necessary states in the initial generating cell automaton is reduced drastically when the automaton is probabilistic rather than deterministic. Since the price being paid is a decrease in the accuracy of the generated network, conditions under which reasonable compromises can be achieved are studied. They depend on the degree of redundancy of the final network (defined from the complexity of a deterministic automaton capable of generating it with maximum accuracy), on the "entropy" of the generating probabilistic automaton, and on the effects of different inputs on its transition probabilities (as measured by its "'capacity" in the sense of Shannon's information theory). The results are used to discuss and make more precise the notion of biological specificity. It is suggested that the weak metaphor of a genetic program, classically used to account for the role of DNA in specific genetic determinations, is replaced by that of inputs to biochemical probabilistic automata.