Increasing Feasibility of Optimal Gene Network Estimation

Annika Hansen (a.hansen@ucl.ac.uk)
Sascha Ott (s.ott@ucl.ac.uk)
Georgy Koentges (g.koentges@ucl.ac.uk)

Functional Genomics Laboratory, Wolfson Institute for Biomedical Research, University College London, The Cruciform Building, Gower Street, London WC1E 6AU, UK


Abstract

Disentangling networks of regulation of gene expression is a major challenge in the field of computational biology. Harvesting the information contained in microarray data sets is a promising approach towards this challenge. We propose an algorithm for the optimal estimation of Bayesian networks from microarray data, which reduces the CPU time and memory consumption of previous algorithms. We prove that the space complexity can be reduced from O(n² · 2n) to O(2n), and that the expected calculation time can be reduced from O(n² · 2n) to O(n · 2n), where n is the number of genes. We make intrinsic use of a limitation of the maximal number of regulators of each gene, which has biological as well as statistical justifications. The improvements are significant for some applications in research.

[ Full-text PDF | Table of Contents ]


Japanese Society for Bioinformatics