Finding Optimal Gene Networks Using Biological Constraints

Sascha Ott (ott@ims.u-tokyo.ac.jp)
Satoru Miyano (miyano@ims.u-tokyo.ac.jp)

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


Abstract

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