124 F. Fages et al.
a new impetus to the study of analog computation and mixed analog/digital
parallel programs.
We have shown that recent results in computable analysis and theoretical
complexity establish solid links between analog and digital computation, and
can be used to compile analog specifications and mixed analog/digital programs
into elementary biochemical reactions. This opens new research avenues to ana-
lyze natural protein interaction circuits not only from point of view of the size
and the static complexity of the networks [ 1 ], but also from the computational
complexity and robustness points of view [ 39 ], to revisit the important particular
case of linear time invariant systems [ 14 – 16 ], to design reaction code optimizers,
and compare natural circuits acquired by evolution to engineered and compiler-
generated synthesized circuits.
The concept of biochemical computation and compilation can also be exper-
imentedin vitroandin vivo, either in Synthetic Biology, through the modifi-
cation and reprogramming of living cells [ 18 , 35 ], or in Synthetic Biochemistry,
through the creation and programming of non-living microfluidic vesicles [ 19 ],
with various applications including the design of biomarkers [ 18 ].
Furthermore, the formal specification by mathematical functions of the
input/output or transient behaviors of biochemical reaction systems under the
differential semantics, establishes novel ways to study the functions of natural
circuits mathematically, and on this route investigate their evolution history and
evolution capabilities [ 47 ].
Acknowledgements.We are grateful to especially one reviewer for his expert proof-
reading which helped us to improve the presentation of our results, and to the editors
for providing us with the necessary extra space. Part of this research is funded by the
ANR-MOST Biopsy project. The first author acknowledges fruitful discussions with
Jie-Hong Jiang (NTU, Taiwan) on the compilation of program control flows with reac-
tions, and motivating discussions with Frank Molina (CNRS, Sys2Diag, Montpellier)
on the biochemical implementation by enzymatic reactions in microfluidic vesicles.
References
- Barab ́asi, A.L.: Network Science. Cambridge University Press, Cambridge (2016)
- Berry, G., Boudol, G.: The chemical abstract machine. Theor. Comput. Sci. 96 ,
217–248 (1992) - Bournez, O., Gra ̧ca, D.S., Pouly, A.: Polynomial time corresponds to solutions of
polynomial ordinary differential equations of polynomial length. J. ACM (2017,
accepted) - Bournez, O., Campagnolo, M.L., Gra ̧ca, D.S., Hainry, E.: Polynomial differential
equations compute all real computable functions on computable compact intervals.
J. Complex. 23 (3), 317–335 (2007).https://hal-polytechnique.archives-ouvertes.
fr/inria-00102947 - Bournez, O., Campagnolo, M.L., Gra ̧ca, D.S., Hainry, E.: The general purpose
analog computer and computable analysis are two equivalent paradigms of analog
computation. In: Cai, J.-Y., Cooper, S.B., Li, A. (eds.) TAMC 2006. LNCS, vol.
3959, pp. 631–643. Springer, Heidelberg (2006). doi:10.1007/11750321 60