title: Integer programming-based approach to allocation of reporter genes for cell array analysis.
abstract: 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.
authors.affiliation: Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji 611-0011, Japan. morihiro@kuicr.kyoto-u.ac.jp
authors.forename: Morihiro
authors.initials: M
authors.lastname: Hayashida
authors.forename: Fuyan
authors.initials: F
authors.lastname: Sun
authors.forename: Sachiyo
authors.initials: S
authors.lastname: Aburatani
authors.forename: Katsuhisa
authors.initials: K
authors.lastname: Horimoto
authors.forename: Tatsuya
authors.initials: T
authors.lastname: Akutsu
mesh_terms: 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*