Integer programming-based approach to allocation of reporter genes for cell array analysis.
In this paper, we consider the problem of selecting the most effective set of reporter genes for analysis of biological networks using cell microarrays. We propose two graph theoretic formulations of the reporter gene allocation problem, and show that both problems are hard to approximate. We propose integer programming-based methods for solving practical instances of these problems optimally. We apply them to apoptosis pathway maps, and discuss the biological significance of the result. We also apply them to artificial networks, the result of which shows that optimal solutions can be obtained within several seconds for networks with 10,000 nodes.
Hayashida
Morihiro
M
Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji 611-0011, Japan. morihiro@kuicr.kyoto-u.ac.jp
Sun
Fuyan
F
Aburatani
Sachiyo
S
Horimoto
Katsuhisa
K
Akutsu
Tatsuya
T
D017209:Apoptosis / Q000235:genetics; D019295:Computational Biology; D053263:Gene Regulatory Networks; D017930:Genes, Reporter; D011382:Programming, Linear; D046888:Tissue Array Analysis / Q000706:statistics & numerical data*