Finding Optimal Gene Networks Using Biological Constraints

Sascha Ott (
Satoru Miyano (

Human Genome Center, Institute of Medical Science, University of Tokyo, 4-6-1 Shirokanedai, Minato-ku, Tokyo 108-8639, Japan


The accurate estimation of gene networks from gene expression measurements is a major challenge in the field of Bioinformatics. Since the problem of estimating gene networks is NP-hard and exhibits a search space of super-exponential size, researchers are using heuristic algorithms for this task. However, little can be said about the accuracy of heuristic estimations. In order to overcome this problem, we present a general approach to reduce the search space to a biologically meaningful subspace and to find optimal solutions within the subspace in linear time. We show the effectiveness of this approach in application to yeast and {\em Bacillus subtilis} data.

[ Full-text PDF | Table of Contents ]

Japanese Society for Bioinformatics