BioSysBio:abstracts/2007/Thorsten Lenser/AppendixC

From OpenWetWare

Jump to: navigation, search


Proof of exact association between maximal independent sets and organizations of size N

Given an undirected graph G=\langle V, E\rangle where V=\{v_1 \dots v_N\} is a set of N vertices and E is a set of edges, an algebraic chemistry \langle {\mathcal M}, {\mathcal R}\rangle can be constructed as described in Appendix B, where {\mathcal M}= \{a_1 \dots a_{2N}\}=\{s_i^0,s_i^1|i=1 \dots N\} is a set of 2N molecular species and {\mathcal R}=\{(A_j \rightarrow B_j)\} is a set of reaction rules. Here, we show with a proof that the constructed reaction network contains organizations with N species as the biggest and those organizations imply maximal independent sets in the given graph.

At first, we define the association between a set of vertices and a set of species.


Let I \subset V be a set of vertices. We call S_{I} = \{ s_{i}^{1} | v_i \in I\} \cup \{s_{i}^{0} | v_i \notin I\} the set of species that is induced by I.

In other words, S_{I} = \{s_1^{b_1} \dots s_i^{b_i} \dots s_{|I|}^{b_{|I|}} \} where bi = 1 when v_i \in I and bi = 0 otherwise.


In the reaction network \langle {\mathcal M},{\mathcal R} \rangle constructed as described in Appendix B, no organization can contain species s_{k}^{0} and s_{k}^{1} together. Therefore, no organization with a size (number of species) greater than N can exist.

Proof of this lemma is given below.


Set I of vertices is a maximal independent set if and only if the induced set SI of species is an organization.


left to right

Let I \subset V be a maximal independent set (MIS) and SI be the set of species induced by I. We have to show that SI is an organization, i.e. closed and self-maintaining.

Closure: Assume that SI is not closed, i.e. there exists a reaction (A_j \rightarrow B_j) \in {\mathcal R} that produces a species that is not in the set SI. If the reaction has the form s_j^1 \to s_k^0 (\in {\mathcal N}) for a edge (v_j,v_k)\in E, then we know s_j^1 \in S_{I} and thus v_j \in I. Since that reaction is assumed to violate the closure property, s_k^0 \notin S_I. We know then s_k^1 \in S_I from the lemma. Because set SI contains both s_j^1 and s_k^1, set I must include both vj and vj. This leads to a contradiction that set I is a MIS and there is an edge (v_j,v_k)\in E.

On the other hand, the reaction can have the form s_h^0 + s_l^0 + \dots + s_m^0 \to n_k s_k^1 (\in {\mathcal V}). In that case we know that s_p^0\in S_I for all neighbors vp of vertex vk. This means no vertexes vp neighboring vertex vk are included in set I. However, the vertex vk is not included in the set since species s_k^1 should not be in the set SI. This contradicts the fact that the independent set I is maximal.

From these arguments, no reaction can produce new species that is not in the set SI. Therefore, this set is closed.

Self-maintenance: Consider the flux vector \mathbf{v} that is 1 for all reactions involving only elements of SI on the left-hand side, and 0 for all others. Given this \mathbf{v}, the rate of change of all species in SI is 0, since inflow and outflow of these species are of equal size. For all species not in SI, no reaction takes place, so their concentrations do not change. Therefore, \mathbf{v} fulfills the self-maintainance condition and SI is self-maintaining.

Right to left

Given a set of vertices I and its induced set of species SI, which is an organization, we need to show that I is a MIS.

Given two vertexes vp and vq from the set I, we know that s_p^1 \in S_I and s_q^1 \in S_I. If there exists an edge (v_p,v_q) \in E, the reaction s_p^1 \to s_q^0 would produce s_q^0 inside the organization SI, which is impossible since s_q^1 \in S_I. Therefore, we conclude that (v_p,v_q) \notin E and I is an independent set.

If I were not a "maximal" IS, we could add a vertex v_p \in V to I, and I \cup \{v_p\} would still be an IS. In other words, there exists p such that a set S'_I=((S_I \backslash \{s_p^0\}) \cup \{s_p^1\}) is still an organization. Because of the presence of species s_p^1, set S'I must contain s_q^0 for all neighbors vq of vp (p \neq q) to be closed due to the reactions in {\mathcal N}. However, this leads to a contradiction that the original set SI is not closed since the set also contains those species s_q^0 but does not contain s_p^1, produced by the reactions in {\mathcal V}. Thus, there does not exist such an index p.

Proof of the lemma

Let O \subset {\mathcal M} be an organization, and suppose the organization contains s_{k}^0 and s_{k}^1 simultaneously (s_{k}^{0}, s_{k}^{1} \in O).

From the definition of the organization to be self-maintaining, there exists a flux vector

\mathbf{v} = (v_{A_1 \rightarrow B_1}, \dots, v_{A_j \rightarrow B_j}, \dots, v_{A_{|{\mathcal R}|} \rightarrow B_{|{\mathcal R}|}})^T

satisfying the following three conditions:

  • v_{A_j \rightarrow B_j} > 0 if A_j \in \mathcal{P}_M(O)
  • v_{A_j \rightarrow B_j} = 0 if A_j \notin \mathcal{P}_M(O)
  • f_i \geq 0 if a_i \in O where (f_1, \dots, f_i, \dots, f_{|{\mathcal M}|})^T = \mathbf{M v}.

where \mathbf{M}=(m_{ij}) is a stoichiometric matrix.

Because of the third condition, the sum of the production rates fi with respect to the species in the organization should be bigger than zero:

\sum_{\{i | a_i \in O\}} f_i = \sum_{\{i | a_i \in O\}} \sum_{j=1}^{|{\mathcal R}|} m_{ij}v_{A_j \rightarrow B_j} \geq 0

We write the reaction indices as \mathcal V, \mathcal N, \mathcal D:

\sum_{\{i | a_i \in O\}} f_i = \sum_{\{i | a_i \in O\}} \sum_{\{j |(A_j \rightarrow B_j)\in {\mathcal V}\}} m_{ij}v_{A_j \rightarrow B_j} + \sum_{\{i | a_i \in O\}} \sum_{\{j |(A_j \rightarrow B_j)\in {\mathcal N}\}} m_{ij}v_{A_j \rightarrow B_j} + \sum_{\{i | a_i \in O\}} \sum_{\{j |(A_j \rightarrow B_j)\in {\mathcal D}\}} m_{ij}v_{A_j \rightarrow B_j}

= \sum_{\{j |(A_j \rightarrow B_j)\in {\mathcal V}\}} \sum_{\{i | a_i \in O\}} m_{ij}v_{A_j \rightarrow B_j} +
  \sum_{\{j |(A_j \rightarrow B_j)\in {\mathcal N}\}} \sum_{\{i | a_i \in O\}} m_{ij}v_{A_j \rightarrow B_j} +
  \sum_{\{j |(A_j \rightarrow B_j)\in {\mathcal D}\}} \sum_{\{i | a_i \in O\}} m_{ij}v_{A_j \rightarrow B_j}

The stoichiometric coefficients mij in the reactions of type \mathcal V and \mathcal N sum up to 0:

\forall j | (A_j \rightarrow B_j) \in ({\mathcal V} \cup {\mathcal N}) : \sum_{i | a_i \in O} m_{ij} = 0

Thus, the first two sums are equal to zero. It follows that the third term must be non-negative.

However, all the stoichiometric coefficients in reactions of type \mathcal D are negative. If organization O contains both s_k^0 and s_k^1 at the same time, the flux for reaction (s_{k}^0 + s_{k}^1 \to \emptyset)\in {\mathcal D} must be set to a positive value. Thus, the sum of the production rates cannot be positive, so at least one production rate has to be negative. This contradicts the definition of the organization. Given this fact, it is obvious that no organization bigger than N can exist.

Personal tools