On the complexity of boolean networks

Abstract

The Boolean Networks are a model which has proven to be useful to model realworld systems. The Random Boolean Network model introduced by Kau man in 1969 has been extensively used to model regulatory genetic networks and other types of systems. In this thesis, we propose the existence of a correlation between the complexity of a Boolean Network and the complexity of its constituents, i.e., the complexity of its topology and its set of updating functions. This hypothesis was tested by performing a series of experiments with the help of the implementation to approximate Kolmogorov complexity called Block Decomposition Method (BDM). First, we present a method to measure the complexity of the individual components of a Boolean Network and then, we propose a representation which can be used to measure the complexity of a Boolean Network. The results showed that this hypothesis was correct for Random Boolean Networks with small topologies given a su ciently large set of Boolean Networks. However, it could not be generalized to larger topologies because of the enormous computational time required by the implementation of the BDM to approximate Kolmogorov complexity. Finally, the di culties to measure the complexities of Random Boolean Networks with larger topologies inspired us to propose a novel method to measure Kolmogorov complexity. We have called this method the Block Decomposition Method with Neural Networks (BDMNN) and is based on the use of Neural Networks to perform a regression that approximates Kolmogorov complexity. These Neural Networks were trained by using random sequences for which its complexity was computed using the original BDM implementation to approximate Kolmogorov complexity. Our implementation was evaluated by performing some experiments with random sequences of bits. The results showed that our implementation is faster and requires less computational power to approximate Kolmogorov complexity than the original implementation. The only cost to be paid is a decrease in the accuracy of the results, however, we expect this error can be easily reduced with some little modi cations to the method.