In this paper, the authors consider the problem of, given a metabolic network, a set of source compounds and a set of target compounds, finding a minimum size reaction cut, where a Boolean model is used as a model of metabolic networks. The problem has potential applications to measurement of structural robustness of metabolic networks and detection of drug targets. They develop an integer programming-based method for this optimization problem. In order to cope with cycles and reversible reactions, they further develop a novel integer programming (IP) formalization method using a feedback vertex set (FVS). When applied to an E. coli metabolic network consisting of Glycolysis/Glyconeogenesis, Citrate cycle and Pentose phosphate pathway obtained from KEGG database, the FVS-based method can find an optimal set of reactions to be inactivated much faster than a naive IP-based method and several times faster than a flux balance-based method. The authors also confirm that our proposed method works even for large networks and discuss the biological meaning of our results.
TopIntroduction
One of the important features of living organisms is robustness. For example, many organisms have strong adaptability to environmental changes. As another example, many organisms can live even if some of their genes are mutated. However, the origin of this robustness is not yet fully understood. Therefore, in order to understand the principles of living organisms, it is quite important to reveal the origin of the robustness. Studying robustness is also important from a medical point of view. It is considered that cancer cells are very robust (Kitano, 2004) and thus cancers are difficult to treat. If we can identify where the robustness of cancer cells comes from, we may develop novel and effective treatment methods by efficiently breaking the robustness of cancer cells.
Of course, the origin of the robustness will not be unique or simple. Many aspects must be taken into account. For example, we should consider dynamics and structure of various kinds of biological networks, which include genetic networks, protein-protein interaction networks, signal transduction networks and metabolic networks. However, it is quite difficult to consider these networks simultaneously. Although the amount of data for structures of genetic networks and protein-protein interaction networks is increasing (Kafri et al., 2005; Levy & Pereira-Leal, 2008), it is not enough yet. On the other hand, we have a lot of knowledge on metabolic networks. Indeed, many network data of various kinds of organisms are available from such databases as KEGG (Kanehisa et al., 2008) and EcoCyc (Karp et al., 2007. Thus, we focus on metabolic networks in this paper. In particular, we focus on structural aspects of metabolic networks because kinetic parameters and/or equations of many reactions are not available.
Various kinds of studies have been done on analysis of structures of metabolic networks. Many studies have been done on analysis of graph-theoretic properties such as degree distribution, network diameter, network motifs, and modularity (Guimerà et al., 2007; Jeong et al., 2000; Milo et al., 2002; Wagner & Fell, 2001. However, in these studies, the effects of substrates and products are not well reflected. Many studies have also been done based on elementary modes and extreme pathways (Behre et al., 2008; Haus et al., 2008; Klamt & Gilles, 2004; Papin et al., 2003; Stelling et al. 2002. In particular, robustness against mutations, insertions and deletions of enzymes was analyzed in (Schuster et al., 1999; Stelling et al., 2002). The methods used there are based on enumeration of elementary modes or extreme pathways and exhaustive mutations of single or multiple enzymes. Therefore, these methods are not very efficient.