Title: Integer programming-based approach to allocation of reporter genes for cell array analysis

Authors: Morihiro Hayashida, Fuyan Sun, Sachiyo Aburatani, Katsuhisa Horimoto, Tatsuya Akutsu

Addresses: Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, 611-0011, Japan. ' Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology, 2-42 Aomi, Koto-ku, Tokyo, 135-0064, Japan. ' Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology, 2-42 Aomi, Koto-ku, Tokyo, 135-0064, Japan. ' Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology, 2-42 Aomi, Koto-ku, Tokyo, 135-0064, Japan. ' Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, 611-0011, Japan

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.

Keywords: integer programming; reporter genes; cell microarrays; signalling network; set cover; NP-hard; reporter gene selection; apoptosis pathway maps; artificial networks; bioinformatics.

DOI: 10.1504/IJBRA.2008.021201

International Journal of Bioinformatics Research and Applications, 2008 Vol.4 No.4, pp.385 - 399

Published online: 10 Nov 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article