## Finding Genetic Network from Experiments by Weighted Network Model

Kiyoshi Noda[1] (knoda@i.kyushu-u.ac.jp)

Ayumi Shinohara[1] (ayumi@i.kyushu-u.ac.jp)

Masayuki Takeda[1] (takeda@i.kyushu-u.ac.jp)

Satoshi Matsumoto[2] (matumoto@ss.u-tokai.ac.jp)

Satoru Miyano[3] (miyano@hgc.ims.u-tokyo.ac.jp)

Satoru Kuhara[4] (kuhara@grt.kyushu-u.ac.jp)

[1] Department of Informatics, Kyushu University

33, Fukuoka 812-8581, Japan

[2] Faculty of Science, Tokai University

Kanagawa 259-1291, Japan

[3] Human Genome Center, University of Tokyo

Tokyo 108-8639, Japan

[4] Graduate School of Genetic Resources Technology, Kyushu University

Fukuoka 812-8581, Japan

### Abstract

We study the problem of finding a genetic network from data obtained by multiple gene disruptions and overexpressions. We define a genetic network as a weighted
graph, and analyze the computional complexity of the problem. We show that if there exists a weighted network which is consistent with given data, we can find it in polynominal time. Moreover, we also consider the optimization problem, where we try to find an optimally consistent weighted network with given data. We show that the problem is NP-hard. On the other hand, we give a polynominal-time approximation ratio 2. We report some simulation results on experiments.

*Japanese Society for Bioinformatics*