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.

[ Full-text PDF | Table of Contents ]