From OpenWetWare

Jump to: navigation, search
Undirected graph given
Undirected graph given

Chemical reaction network A=\langle \mathcal{M},\mathcal{R}\rangle 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 \mathcal{M} of molecular species consists of eight species:

\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\}.

(Note: species s_1^0 is denoted as \mathsf{s10} in the figure.)

The set \mathcal{R} of reaction rules is composed of three sets:

 \mathcal{R} = (\mathcal{V} \cup \mathcal{N} \cup \mathcal{D})


\mathcal{V}=\bigcup_{i=1}^4\mathcal{V}^i, \mathcal{N}=\bigcup_{i=1}^4\mathcal{N}^i, and \mathcal{D}=\bigcup_{i=1}^4\mathcal{D}^i.


\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{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{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}&\}\\

File history

Click on a date/time to view the file as it appeared at that time.

current06:56, 27 September 2006600×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. )

Personal tools