Finding optimal gene networks using biological constraints.
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.
Ott
Sascha
S
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
Miyano
Satoru
S
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
D012333:RNA, Messenger