数理解析研究所講究録 1222 巻 2001 年 128-137

128
Pathway Graph Models for Molecular Computing in situ
LIU Jian-Qin and SHIMOHARA Katsunori
Information Sciences Division, ATR International
2-2-2, Hikaridai, Seika-cho, Soraku-gun, Kyoto, 619-0288, Japan
Abstract
This paper proposes anew class of models for molecular computing with biologicalplausible backgrounds, in which formalization, computability, logic forms and related

are presented and discussed. Some helpful conclusions for thefurther systematic studying of kinase computing and its formal theories are provided.

prototype$\mathrm{c}\mathrm{h}\mathrm{m}\mathrm{c}\mathrm{t}\mathrm{e}\dot{\mathrm{n}}\mathrm{s}\dot{\mathrm{u}}\mathrm{c}\mathrm{s}$1. Introduction
As an unconventional computational pmdig1k one of the most important purposes of ourwork is to surpass conventional technology. With regard to technology, this paper targets a
number of challenging topics, such as scalability, speed and error-handlng. Our

motivation comes from optimizing the above three topics by exploring computability toconstruct ascalable and robust scheme for$\mathrm{f}\mathrm{a}\mathrm{u}\mathrm{l}\nu \mathrm{d}\mathrm{e}\mathrm{f}\mathrm{e}\mathrm{c}\mathrm{t}$-tolerance and speed by employing

a“self-feeding” method, which is helpful step to bridge the gap between formal systems

2. Molecular Computing in siu by Kinase-centered Signaling Pathways
in Functional Cels
Among the various implementation technplogies for molecular computing, DNA, RNA

and other$\mathrm{b}\mathrm{i}\mathrm{o}$-molecules have been harnessed as components to build amolecular

computer. Briefly speaking, kinase computing here refers to molecular computing by

kinases and their related molecules in living cells. The biological background mainly
comes from the Rho family [1]. The original contribution of our work on kinase

computing can be

the initiation of anovel unconventional computational

paradigm to exbact the inexplicit structure of the problems and the computability whichleads to super-Turing machines. As we know, -informatics offers us rich landscape of$\mathrm{b}\mathrm{i}\mathrm{o}$129biologically-inspired infomation.mechanisms that can be classified into unconventional
computing. Among them, proteomics helps us to understand biochemical reactions related
to signaling pathways and cell communication [1]. Sieving the various types ofproteomics-based processes in cells, kinase and related enzymes and functional proteins
have become our starting point for studying these kinds of biochemical mechanisms
existing in nature. This is the core spirit of inventing synthesis engineering by bi0inorganic molecular electronics for moleware building based on themolecular$\mathrm{a}\mathrm{n}\mathrm{d}/\mathrm{o}\mathrm{r}$analysis of bi0-informatics.

3. Formalization, Graph Rewriting and Beyond
In this paper we present our theoretical work on formal models of kinase computing– LSsystems. At the beginning of our work on$\mathrm{L}\mathrm{S}$-systems, computability was our focus but welater found important merits in the aspects of formal languages, algebraic systems(especially in semi-groups) and the theory of computation in the mainstreams of boththeoretical computer science and multidisciplinary fields related to molecular biology,

mathematics and information engineering. Clearly, abroad area emerging from kinase

computing is within our scope.

3.1 LS-systems
The basic class of$\mathrm{L}\mathrm{S}$Let the construct be$\mathrm{V}$$\mathrm{E}$$\mathrm{Y}$-systems is defined as follows:$\mathrm{W}_{1\mathrm{s}}=<\mathrm{V}$, ,$\mathrm{E}$$\mathrm{Y}$,$\mathrm{A}$,$\mathrm{B}$,$\mathrm{Q}$,$\mathrm{Z}>$-the set of vertexes;-the set of edges;-the set of hyperedges for pathways;

A-the alphabet set;$\mathrm{B}$-the set of the constraints that can beother$\mathrm{f}\mathrm{o}\mathrm{m}$$\mathrm{d}\mathrm{e}\mathrm{s}\mathrm{c}\mathrm{r}\mathrm{i}\mathrm{b}\mathrm{e}\mathrm{d}/\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{d}$as logic, function, set or;-the set of operators or operations for graphs or hypergraphs from , , and$\mathrm{V}$$\mathrm{Q}$$\mathrm{Z}$$\mathrm{E}$$\mathrm{Y}$;-the set of local concentration.

The fundamental of the computing processes is constructed on aparallelism where the PEs(Processing Elements) are formalized as vertexes in graphs and the whole set of related
graphs is denoted as G. The$\mathrm{E}$set is generated according to links between different PEs

130
Here the PEs can be implemented by the moleware form. The pathways refer to the strings

defined by the symbolic set A. Under the condition of , the main applied operations in$\mathrm{Y}$$\mathrm{B}$include (1) feedback-making, (2) interacting, and (3) stable-checking. Under thecircumstances of the cells where dynamical operations for signaling molecules exerted,
local features (e.g., concentrations) reflect the heterogenous architecture of thecomputational processes constructed above.

3B Simulation Model
For an overview of the feasible implementation, our proposed simulation model is given in
figure 1. It consists of three layers: (a) the biochemical molecular layer (the lowest layer),(b) the pathway layer (the middle layer), and (c) the operation layer (the highest layer).

Fig. 1Overview of the simulation model
In terms of software, the main dataflow includes the input and output of the molecules thatare handled in the molecular layer, where measures such as the local concenffations inorganelles and cells are defined. The number of molecules that we have used here incomputing is limited. They are drawn from adatabase verified by experimental evidence
from molecular biology (e.g., benchworks). Real values are assigned to objects andcombinatorial ODEs (Ordinary Differential Equations) corresponding to the pathways.
Theoretically speaking, infinite real numbers can be obtained in the computing system
mentioned above through finite molecules. In essence mapping in functional space isnecessary for$\det\ovalbox{\tt\small REJECT} \mathrm{g}$the relationship between the finite and the infinite throughcorresponding topological constraints (e.g., high dimensional networks).

3.3 Graph Rewriting and More
From this simulation model we can derive the following graph rewriting system:$<\mathrm{G}$,$\mathrm{Q}$,$\mathrm{B}’>$131

G–the set of hypergraphs;
Q– the operation set;$\mathrm{B}’--$

the set of related constraints.

Owing to the fact that graph rewriting is useful for parallel computing software andprograms, we have developed akernel of simulation software in an object-0riented way
and designed agraph rewriting language with primitive forms independent of machines
based on representation by asymbolic set of strings for hyperedges and their interactions
with increasing complexity. The three factors of context dependence, language level’s

operation, and context sensitive grammar need to be handled in the corresponding
landscape of grammars that are derived from formal models. This bids the question of how
to infer structures in pathways and$\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{r}\mathrm{g}\mathrm{e}/\mathrm{d}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{e}$formal languages. The main results

obtained are: (1) The non-feedback and linear combined pathways’ model gives regular

grammar, (2) The pathways’ model with interactions under certain conditions gives
context free and context sensitive grammar, and (3) The model gains the computability ofTuring machines when the feedback is equipped with the interactions. Through aparallel
structure, OL can be inferred. But the relationship between our model and indexedlanguages still remains open and we plan to address this in the near future. With the highspeed of molecular electronics, femt0-second speeds can be expected and therefore thequantum effect must be considered, so our proposed n0n-G8de1 construction schemes for

non-Turing machines can be used to describe the uncertain related phenomena and related
mechanisms, in which we use moleware in quanta to represent amolecular computer

prototype where asingle molecule level is adopted for the molecular logic and gate arrays.

Also considering evolutionary computation in the natural computing domain, let us
formalize evolutionary algorithms as$<\mathrm{W}\mathrm{e}$, Qe, Ge,$\mathrm{Y}\mathrm{e}>$where,

We– the population set;Qe– the evolutionary operator set;

Ge– the selection criterion set;Ye– the termination criterion set

132
When apopulation consisting 0. individual object-forms is provided to handle thescalability of NP problem-solving, the open end of evolution yields increasing complexity$\mathrm{f}$in paralel searching with adaptive fitness evaluation as akind of pruning for theunderlying structure (e.g., string, tree, graph or other high dimensional structures that areconcrete in programming and data structure or abstract in networks). Acertain degree ofcost-cutting can be achieved from the parallel evolution of the population in an adaptiveway.

4. uper-Turing Machine
Further, we envision the above model as a“Kinase Computing model with Local$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{c}\mathrm{e}\mathrm{n}\mathrm{n}\mathrm{a}\dot{\mathrm{u}}\mathrm{o}\mathrm{n}\mathrm{s}$(KCLC)”, which is shown in Figure 1and study its computability. Here,super-Turing machines refer to kind of abstract machines which can compute the Turingmachine in-computable information.
Theorem: The KCLC model is equipped with the computability of super-Turing$\prime \mathrm{s}$machines.

Proof (sketch):
Step 1: The real valued domains for the input and output are defined as topological areas
in measurable space, so the problem becomes aprocesses of recursively exerting theoperations of constructing and reconstructing the combined mapping with increasing
degrees of complexity.

Step 2: According to the theorems by Kolmogorov in 1957 and Sprecher in 1965 [2], thefunction sets and combined sets are constructive and the mapping set is feasible, so themapping set from real space to real space is guaranteed.
Step 3: order to prove the feature that the whole space of the real numbers for the input
and output can be covered, we use the method of eliminating the assumption ofcontroversial examples that certain uncoverable non-Turing computable numbers exist. If$\mathrm{h}$so, we can obtain the result that the pathway set can not be included in the set to operatethem in order to add the resultant ones into the set already obtained. Assuming this, at$\mathrm{Q}$least one pathway exists out of the pathways that are believed to have fallen into theproven domain, but they are reachable according to the links attached to them. This lead$\mathrm{s}$133
to controversy. Any new pathway that occurs by adding an operation from$\mathrm{Q}$is alsoreachable and acceptable in logic. So the coverability is assured.

Step 4: The number of kinases and enzymes is finite and the mapping determined by themis coverable for the real spaces above.
Step 5: Through finite operation ffom graph rewriting, the pathways reflecting the realvalued objects can be produced. They can be reduced into the pathways that are based on
the three basic operators of feedback-making, interaction and survival checking. The nonG\"odel logic introduced is necessary in the meaning of logic, leading to the framework for

Q.E.D.

the inferring.

This class should include the subclass with Turing computability discussed in the next

section.

5. Universal Computation
We define the measure of fitness for judging whether the objects in KCLC should beallowed to exist. The strings, i.e., the sequences of the symbols for the reactants in thepathways, derived from the hyperedges construct asubclass of KCLC, which is denoted as
KCLCI.
Theorem: KCLCI is Turing-computable.

Proof (sketch) :On the basis of the previous formalization, the function set$\{\mathrm{f} (.)|\mathrm{D}_{\mathrm{p}\mathrm{o}\mathrm{p}}->\mathrm{D}_{\mathrm{f}\mathrm{i}\mathrm{t}}\}$

is our starting point. Here,
population, and$\mathrm{D}_{\mathrm{f}\mathrm{i}\mathrm{t}}$$\mathrm{D}_{\mathrm{p}\mathrm{o}\mathrm{p}}$is the set of the objects, which means the domain of theis the measure for the fitness. The primitive recursive function for

constant 0, the successor function and the project function can be inferred directly ffom

the quantitative relation inherited ffom the structure given.

. are defined in the value domain oflarge value acting as athreshold. There exists an such that(a) Assuming that$\mathrm{L}$

$($

$)$

$\mathrm{a}$$)\})$$[0, \mathrm{f}_{\max}]$,$\mathrm{L}(\mathrm{a})=0$($\mathrm{f}_{\max}$$\mathrm{L}($is asufficiently-. belongs to$)$$\{\mathrm{f}$$($.

where belongs to Dpop. This is obvious owing to the physical meaning of fitness.
$\mathrm{a}$(b) Increasing the value forwhere$\mathrm{H}$$($. belongs to$)$$\mathrm{f}$$($$\mathrm{f}$$($. is also feasible, i.e., there exits a such that
$)$

$b$

$\mathrm{H}(6)=b+1$,. owing to the existence of valuing mapping for the relationship$)$between strings and numbers

134(c)Let$\mathrm{Y}_{\mathrm{p}}=$represent the pathway ffom reactants$\mathrm{f}_{\mathrm{p}}(\mathrm{x}\mathrm{i},\mathrm{X}2)$$\mathrm{X}_{1}$and$\mathrm{X}_{2}$to product Yp.

According to the existence of the feedbac4 we obtain$\mathrm{f}_{\mathrm{p}}(\mathrm{x}_{1\lambda 2})=\mathrm{x}_{1}$or .
$\mathrm{x}_{2}$We can infer that$\mathrm{f}_{\mathrm{p}\mathrm{i}}(\mathrm{x}_{1},\ldots,\mathrm{x}_{\mathrm{n}})=\mathrm{x}_{\mathrm{i}}(\mathrm{i}=1,2,\ldots,\mathrm{n})$exists.
We can also define the following three hypergraph representations:$\mathrm{G}_{1}$:for$(\mathrm{x}_{1}, \mathrm{x}_{2}, \ldots, \mathrm{x}_{\mathrm{n}})->\mathrm{f}_{\mathrm{g}1}=\mathrm{f}(\mathrm{x}\mathrm{i}, \mathrm{x}_{2}, \ldots, \mathrm{x}_{\mathrm{n}})$G2: for ( , X2,$\mathrm{x}_{1}$$\mathrm{G}_{3}$:for (

where$\ldots$$\mathrm{f}_{\mathrm{g}1}$,$\mathrm{x}_{2}$$\mathrm{f}\mathrm{g}2$,$\mathrm{x}_{\mathrm{n}},$$\mathrm{x}_{\mathrm{j}}$, ( , X2,$\mathrm{f}$$\mathrm{x}_{1},$,)$\mathrm{x}\mathrm{i}$$\mathrm{h}(.)$$\mathrm{f}$$->\mathrm{f}_{\mathrm{g}2}=$$\ldots$,$\mathrm{x}_{\mathrm{n}},$$\mathrm{x}_{\mathrm{j}}$)($\mathrm{x}\mathrm{i}$$->\mathrm{h}(.)$

belong to the set ofThen, the rewriting of$\mathrm{G}_{1}$, X2,$\ldots$,$\mathrm{x}_{\mathrm{n}},$$\mathrm{x}_{\mathrm{j}}$).

$(\mathrm{h}(.)\}$.

to G2 and then G2 to G3 is feasible in the linear time of

For the relationship between the -place function$k$$\mathrm{Z}_{k}$$\mathrm{O}(\mathrm{n}+4)$

and the $(k+l)$ -place function$\mathrm{Z}_{k+\mathit{1}}$

.

, we

can obtain the following result:$\mathrm{Z}_{\mathrm{k}}(D-m$exists such that$\mathrm{Z}_{\mathrm{k}}(/,\mathrm{m})=0$,

when the index corresponds to the notation of the reactants in the -order of the pathway
$k$

$l$

and

$m$

represents the added reactant (labeled $k+l$ ). This means that the pathways give theresult that the final product with the index $k+l$ will stop when at least one enzyme isincluded in the order of the pathway. If the order of the pathway can not produce $k+l$ ,$k$

it is obvious that$k$$\mathrm{a}$$(/)$

must be zero.

So, KCLCI is proved to be equivalent to aclass of -recursive functions. So finally its$\mu$Turing computability is guaranteed.

Q.E.D.

After the Turing computability is obtained, simple operation can easily be implemented.

The number of these operations is not infinite for the universal computation in our model.
In the cell environment we can control the$\mathrm{Q}$operations by means of akinase-based

biochemical reaction mechanism, and agene regulation$\mathrm{f}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{c}\dot{\mathrm{u}}\mathrm{o}\mathrm{n}$can also easily beembedded. This is biologically supported argument.

6. Logic Description Based on Extended RPL
Based on the definition, above, the relation Kq on the.

$\mathrm{q}_{\mathrm{i}}K_{q}\mathrm{q}$where andj are integers,$\mathrm{i}$$\mathrm{q}\mathrm{i}$,$\mathrm{Q}$

set is defined as:

belong to the concerned objects defined in

135
the previous sections.

According to the truth value in the meaning of RPL (Rescher Probabilistic Logic),
belongs to $[0,1]$ ( belongs to$\mathrm{p}$$\mathrm{p}$$A$$y(\mathrm{p})$which is the set of all of the propositions; notice here thatis not probability).

The difference that we have constructed ffom RPL is$y(\mathrm{p}H_{y}\mathrm{q})=\mathrm{m}(\mathrm{p})*\mathrm{m}(\mathrm{q})$where
to the$H_{y}$$\mathrm{Q}$is defined as akind of$K_{q}$,$\mathrm{m}(\mathrm{p})$and$\mathrm{m}(\mathrm{q})$refer to the different measures related

set , respectively.

As aof meta-theory, the description ability is enhanced after introducing theTheorem: The logic construction for the$H_{y}$

operation.

set through extended RPL is close (it can also$\mathrm{Q}$be understood as “complete” in the meaning of the non-monotonic logic of artificial

intelligence, but this is not the completeness of$\mathrm{G}5\mathrm{d}\mathrm{e}\mathrm{F}\mathrm{s}$concept).

Proof (sketch):
For the structure of the relationship between domain and assignment, the assignment

mapping is given as$y$$y->[0,1]$

So the atomic formula can be easily constructed. And we getA$[\mathrm{s}]$So we have$\mathrm{Q}$is true,$y$(A$\mathrm{s}$$[\mathrm{s}]$is an object defined in the previous sections.

) $=1$ and know that the atomic formula is true. Here$\mathrm{T}$and$\mathrm{F}$for theset are assigned to the feasible pathway and unsustainable or impossible pathway,

respectively. Further, the probability for the final survival verification is employed toinduce the multi-value logic forms by RPL as $[0, 1]$ and$\mathrm{n}\mathrm{V}_{\mathrm{a}\mathrm{n}\mathrm{d}’}$and$n\mathrm{V}_{\varpi}’$

for the merging

of two pathways and the extraction of the common part of two pathways, respectively.
When the axiom set and separation rule are kept the same as the ones in RPL, an extended
operator$\mathrm{H}_{1\mathrm{s}}$is introduced under the following true value constraint:$\mathrm{y}(\mathrm{p}\mathrm{V}_{\mathrm{a}\mathrm{n}\mathrm{d}}\mathrm{q})=\mathrm{H}_{1\mathrm{s}}(\mathrm{p},\mathrm{q})$where$\mathrm{H}_{1\mathrm{s}}=\min$$(\mathrm{v}(\mathrm{p}), \mathrm{v}(\mathrm{q}))+\mathrm{n}\cdot \mathrm{n}$$(\mathrm{v}(\mathrm{p}), \mathrm{v}(\mathrm{q}))/(\mathrm{v}(\mathrm{p})+\mathrm{v}(\mathrm{q}))$.

When the proposition from the extended RPL is not the atomic

dividability of the$\mathrm{Q}$$\mathrm{f}\mathrm{o}\mathrm{m}\mathrm{u}\mathrm{l}*$through theset, it can be$\mathrm{S}_{\mathrm{q}}^{\mathrm{n}+1}=\mathrm{S}_{\mathrm{q}}^{\mathrm{n}}+\mathrm{S}_{\mathrm{q}}^{\mathrm{r}}$$\mathrm{s}.\mathrm{t}$.

$y(.)$,$\mathrm{S}_{\mathrm{q}}^{\mathrm{n}+1}$,,$\mathrm{S}_{\mathrm{q}}^{\mathrm{n}}$$\mathrm{S}_{\mathrm{q}}^{*}$

are the elements in the set of pathways,

they are also corresponding to the elements in Y.

136
This is reasonable provided.

$\mathrm{t}\mathrm{h}\mathrm{a}\mathrm{t}.\mathrm{S}_{\mathrm{q}}^{\mathrm{n}}$is close for$\mathrm{Q}$operators, so it is sufficient to only

can be inferred as one of the following three situations: (a)the feedback-inserting, (b) interaction of the obtained pathways, or (c) survival pathway
verification by duration. So the results can be concluded as (a) truth values unchanged, (b)can bethe or non-zero, or (c) the or F. Therefore the truth values’ feature inprove the existence of$\mathrm{S}_{\mathrm{q}}^{\mathrm{r}}$$\mathrm{S}_{\mathrm{q}}^{\iota}$$\mathrm{n}+1$$\mathrm{T}$$\mathrm{F}$inherited from the one in$\mathrm{n}$.

Q.E.D.

7. APrototype of Kinase Computing in situ:
The prototype we have built consists of the following major parts:(1) Implementation of arithmetic and logic operations: In order to implement the basic

units of computers, we must design an addition unit, which can be applied to carry
subtraction, multiplication and division by means of hardware for operation in aCPU.
-molecular computing, we work out
Conffary to the molecules’ ways in existing$\mathrm{b}\mathrm{i}\mathrm{o}$“pathways” that contract the MIMD molecular information flow and are also capable oftopological coding and are controllable for integrated cell signaling and communication.
The logic operations, such as AND, OR, NOT and others as XOR can be made mainly by
three methods: (a) the hardware-like method for implementing the assembly-language

level instructions of logic based on an addition$\mathrm{u}\mathrm{n}\cdot 1$$(\mathrm{b})$the basic logic unit of AND, OR

and NOT and more complicated logic built by gate circuits, and (c) tables applied to store
the input-t0-0utput information for data accessing, which is beneficial to the large-scale

memory of$\mathrm{b}\mathrm{i}\mathrm{o}$-molecular computers and the whole-memory schemes of molecular

computers employing molecular electronics.
(2) Algorithms for solving NP problems such as the classes of PSPACE-hard and othergraph-related problems by P-cost.
(3) Robust coding schemes based on the formal systems proposed above and simulations.

(4) Unsupervised training for pattern 1 油血$\mathrm{g}$and its extendability for non-parametriclearning: The core of our method is that we do not need any prior knowledge from aknown sample set. The principle here is that “Let the systems tell their own story bythemselves (LSTX)”, i.e. the LSTX principle. This is arequirement ffom the knowledge
discovery tasks in molecular biology for real world problems from bi0-informatics

137(5) Scalability for NP problem solving by 10 quadrillion molecules: We have simulated

the 3-SAT $(50, 20)$ with 10,000,000,000,000,000 molecules. The methods we developed
here are helpful to potential applications in massive signal processing such as image or

speech and high-dimensional clustering.
(6) Computer-aided design schemes for wetware implementation: The implementation is

expected to be done by cell systems through methods of synthesis engineering, which isbased on the analysis with simulation and experimental verification.
(7)

Robust computational model for-tolerant molecular computing:$\mathrm{f}\mathrm{a}\mathrm{u}\mathrm{l}\mathrm{t}/\mathrm{d}\mathrm{e}\mathrm{f}\mathrm{e}\mathrm{c}\mathrm{t}$Enlightened by our discovery of the “ladders” phenomena in algorithm chemistry (alsocalled artificial chemistry), we infer that their architecture is equipped with efficient task

allocations over the whole system where dynamical decision-making is used for moleculechanges, pathway changes and parameter changes.

8. An Open problem
Originating from the formal system here, an important question remains: “What is thecomplete language hierarchy in the space out of Turing machines and with astronger

computability than Turing machines?” To answer this, we are exploring the computational
mechanism in the single molecular level where the quantum effect occurs, which isleading to molecular computing in quanta.

Acknowledgement
J.-Q. Liu sincerely thanks Prof. Masami Ito for his teaching and academic advice on
formal languages and theory of computation, Prof. Tatsuhiko Sato, Prof. Teruo Imaoka,
Prof. Hidenosuke Nishio, and Prof. Reiji Nakajima for their suggestions on algebraic
theory, semi-groups, formalization and computability, respectively.
This work is partly supported by the Huo Yingdong Foundation (Project No. 71063) andthe National Natural Science Foundation of China (Project No. 69985008).

References[1] K. Kaibuchi, S. Kuroda, and M. Amano, Regulation of the cytoskeleton and cell adhesion by
the Rho family GTPases in mammalian cells, Annu. Rev. Biochem. 1999 .68: 459A86.

[2] J. Suykens et al., Artificial neural networks for modelling and control of non-linear systems.

Boston: Kluwer Academic Publishers, 1996; 23-24