title: Finding optimal gene networks using biological constraints.
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 Bacillus subtilis data.
authors.affiliation: Human Genome Center, Institute of Medical Science, University of Tokyo, 4-6-1 Shirokanedai, Minato-ku, Tokyo 108-8639, Japan. ott@ims.u-tokyo.ac.jp
authors.forename: Sascha
authors.initials: S
authors.lastname: Ott
authors.forename: Satoru
authors.initials: S
authors.lastname: Miyano
mesh_terms: D000465:Algorithms; D001499:Bayes Theorem; D001695:Biology / Q000379:methods; D002453:Cell Cycle; D019295:Computational Biology / Q000379:methods*; D005786:Gene Expression Regulation; D008957:Models, Genetic; D005810:Multigene Family; D012333:RNA, Messenger / Q000235:genetics; D012441:Saccharomyces cerevisiae / Q000166:cytology
chemical_list: D012333:RNA, Messenger