File:ReactionNets-structure-mis-n04-01-nets.png
ReactionNets-structure-mis-n04-01-nets.png (600 × 400 pixels, file size: 8 KB, MIME type: image/png)
Chemical reaction network [math]\displaystyle{ A=\langle \mathcal{M},\mathcal{R}\rangle }[/math] designed to solve the maximal independent set problem, given an undirected graph. The detail algorithm can be found in BioSysBio Abstract, Appendix B.
The set [math]\displaystyle{ \mathcal{M} }[/math] of molecular species consists of eight species:
- [math]\displaystyle{ \mathcal{M}=\{s_1^0, s_1^1, s_2^0, s_2^1, s_3^0, s_3^1, s_4^0, s_4^1\} }[/math].
(Note: species [math]\displaystyle{ s_1^0 }[/math] is denoted as [math]\displaystyle{ \mathsf{s10} }[/math] in the figure.)
The set [math]\displaystyle{ \mathcal{R} }[/math] of reaction rules is composed of three sets:
- [math]\displaystyle{ \mathcal{R} = (\mathcal{V} \cup \mathcal{N} \cup \mathcal{D}) }[/math]
where
- [math]\displaystyle{ \mathcal{V}=\bigcup_{i=1}^4\mathcal{V}^i }[/math], [math]\displaystyle{ \mathcal{N}=\bigcup_{i=1}^4\mathcal{N}^i }[/math], and [math]\displaystyle{ \mathcal{D}=\bigcup_{i=1}^4\mathcal{D}^i }[/math].
Specifically,
- [math]\displaystyle{ \begin{matrix} \mathcal{V}=\{&\underbrace{s_2^0 + s_3^0 \rightarrow 2 s_1^1},& \underbrace{s_1^0 + s_3^0 \rightarrow 2 s_2^1},& \underbrace{s_1^0+s_2^0+s_4^0 \rightarrow 3s_3^1},& \underbrace{s_3^0\rightarrow s_4^1}&\}\\ &\mathcal{V}_1&\mathcal{V}_2&\mathcal{V}_3&\mathcal{V}_4&\\ \end{matrix} }[/math],
- [math]\displaystyle{ \begin{matrix} \mathcal{N}=\{&\underbrace{s_2^1 \rightarrow s_1^0, s_3^1 \rightarrow s_1^0},& \underbrace{s_1^1 \rightarrow s_2^0, s_3^1 \rightarrow s_2^0}&, \underbrace{s_1^1 \rightarrow s_3^0, s_2^1 \rightarrow s_3^0, s_4^1 \rightarrow s_3^0},& \underbrace{s_3^1\rightarrow s_4^0}&\}\\ &\mathcal{N}_1&\mathcal{N}_2&\mathcal{N}_3&\mathcal{N}_4&\\ \end{matrix} }[/math],
and
- [math]\displaystyle{ \begin{matrix} \mathcal{D}=\{&\underbrace{s_1^0 + s_1^1 \rightarrow \emptyset}, & \underbrace{s_2^0 + s_2^1 \rightarrow \emptyset}, & \underbrace{s_3^0 + s_3^1 \rightarrow \emptyset}, & \underbrace{s_4^0 + s_4^1 \rightarrow \emptyset}&\}\\ &\mathcal{D}_1&\mathcal{D}_2&\mathcal{D}_3&\mathcal{D}_4&\\ \end{matrix} }[/math].
File history
Click on a date/time to view the file as it appeared at that time.
Date/Time | Thumbnail | Dimensions | User | Comment | |
---|---|---|---|---|---|
current | 03:56, 27 September 2006 | 600 × 400 (8 KB) | NaokiMatsumaru (talk | contribs) | Chemical reaction network to solve a maximal independent set problem. The undirected graph given consists of four vertexes and four edges. |
You cannot overwrite this file.
File usage
The following 3 pages use this file: