An algorithm for reconstruction of Markov blankets in Bayesian networks of gene expression datasets

This paper presents an efficient algorithm, of polynomial complexity for learning Bayesian belief networks over a dataset of gene expression levels. Given a dataset that is large enough, the algorithm generates a belief network close to the underlying model by recovering the Markov blanket of every node. The time complexity is dependent on the connectivity of the generating graph and not on the size of it, and therefore yields to exponential savings in computational time relative to some previously known algorithms. We use bootstrap and permutation techniques in order to measure confidence in our finding. To evaluate this algorithm, we present experimental results on S.cerevisiae cell-cycle mesurements of Spellman et al. (1998).