Natural Computation

The group seeks to understand, model, and program naturally occurring or nature-inspired self-organising processes. The current main focus is on DNA and RNA self-assembly, but related areas of interest are e.g. algorithms for swarm robotics and programmable matter, control of distributed sensor networks, and stochastic optimisation methods for complex energy landscapes.

Members

Present members

• Prof. Pekka Orponen
• M.Sc. Antti Elonen

Alumni

• Prof. Satu Elisa Schaeffer (LinkedIn, homepage)
• Prof. Shinnosuke Seki (homepage)
• Ass. Prof. Mika Göös (homepage)
• Ass. Prof. Joris Kinable (LinkedIn, homepage)
• Ass. Prof. Abdulmelik Mohammed (LinkedIn)
• Dr. Lauri Ahlroth (LinkedIn)
• Dr. Eugen Czeizler (LinkedIn)
• Dr. Vinay Gautam (LinkedIn)
• Dr. Harri Haanpää (LinkedIn)
• Dr. Orestis Kostakis (LinkedIn)
• Dr. Rémi Lemoy (LinkedIn)
• Dr. Tuomo Lempiäinen (LinkedIn)
• Dr. Hamed Mahmoudi (LinkedIn)
• Dr. Pierre-Étienne Meunier (LinkedIn)
• Dr. Alexander Mozeika (LinkedIn)
• Dr. Olli Pottonen (LinkedIn)
• Dr. André Schumacher (LinkedIn)
• Dr. Vo Hong Thanh (LinkedIn)
• M.Sc. Henrik Granö (LinkedIn)
• M.Sc. Antti Halme (LinkedIn)
• M.Sc. Hamidreza Kamkari (homepage)
• M.Sc. Dani Korpela (LinkedIn)
• M.Sc. Ayush Kumar (LinkedIn)
• M.Sc. Anna Lohikko (LinkedIn)
• M.Sc. Shiting Long (LinkedIn)
• M.Sc. Vladimir Morozov (LinkedIn)
• MA Malgorzata Nowicka (LinkedIn, homepage)
• M.Sc. Sachith Pai (LinkedIn)
• M.Sc. Mehdi Saman Booy (LinkedIn)
• M.Sc. Petri Savola (LinkedIn)
• B.Sc. Anastasiia Baltser (LinkedIn)
• B.Sc. Emil Hiitola (Linkedin)
• B.Sc. Aleksandr Kravchenko (LinkedIn)
• B.Sc. Teemu Pudas (LinkedIn)
• B.Sc. Alesya Raevskaya (LinkedIn)
• B.Sc. Leon Wimbes (LinkedIn)
• Mr. Sakari Seitz (LinkedIn)

Projects

• Algorithmic Designs for Biomolecular Nanostructures (Academy of Finland, 2017-2021)
• Practical Designs of Molecular Self-Assembly Systems and Their Optimisation (Academy of Finland, 2013-2015)
• FiDiPro Erik Aurell - Statistical Physics, Distributed Systems, and Computational Biology (Academy of Finland, 2009-2013)
• Modern Algorithmics and Its Interdisciplinary Applications (Academy of Finland, 2011)
• OLP: Online Optimisation and Production Planning (Academy of Finland, 2009-2011)
• Algorithmics for Data Security: Anomaly Detection and Call Graph Analysis (Tekes/ICT SHOK 2009-2011)

Publications and Preprints

2022

• Elonen, Antti; Natarajan, Ashwin K.; Kawamata, Ibuki; Oesinghaus, Lukas; Mohammed, Abdulmelik; Seitsonen, Jani; Suzuki, Yuki; Simmel, Friedrich C.; Kuzyk, A; Orponen, Pekka. Algorithmic design of 3D wireframe RNA polyhedra. ACS Nano, 2022. Vol. 16, nro 10, pp. 16608-16616. DOI: 10.1021/acsnano.2c06035. Preprint version bioRxiv 28.4.2022, 17+32 pp., DOI: 10.1101/2022.04.27.489653
• Saman Booy, Mehdi; Ilin, Alexander; Orponen, Pekka. RNA secondary structure prediction with convolutional neural networks. BMC Bioinformatics, 2022. Vol. 23, nro 58, 15 pp. DOI: 10.1186/s12859-021-04540-7

2021

• Kostitsyna, Irina; Orponen, Pekka (Eds.) Proceedings, 19th International Conference on Unconventional Computation and Natural Computation, UCNC 2021, Espoo, Finland, 18-22 October 2021. Springer Cham. DOI: 10.1007/978-3-030-87993-8
• Vo, H. Thanh; Korpela, Dani; Orponen, Pekka. Cotranscriptional kinetic folding of RNA secondary structures including pseudoknots. Journal of Computational Biology 28 (2021), pp. 892-908. DOI: 10.1089/cmb.2020.0606

2020

• Gautam, Vinay; Long, Shiting; Orponen, Pekka. RuleDSD: A rule-based modelling and simulation tool for DNA strand displacement systems. 13th International Joint Conference on Biomedical Engineering Systems and Technologies, BIOSTEC 2020, Valletta, Malta, February 24-26, 2020. Proceedings, 2020, SCITEPRESS - Science and Technology Publications, Lda, pp. 3:158-167. ISBN: 978-989-758-398-8. DOI: 10.5220/0008979101580167
• Vo, H. Thanh. RSSALib: A library for stochastic simulation of complex biochemical reactions. Bioinformatics, 2020. DOI: 10.1093/bioinformatics/btaa602

2019

• Hoffecker, Ian T.; Yang, Yunshi; Bernardinelli, Giulio; Orponen, Pekka; Högberg, Björn. A computational framework for DNA microscopy. Proceedings of the National Academy of Sciences, 2019. Vol. 116, nro 39, pp. 19282-19287. DOI: 10.1073/pnas.1821178116
• Simoni, Giulia; Vo, H. Thanh; Priami, Corrado; Marchetti, Luca. A comparison of deterministic and stochastic approaches for sensitivity analysis in computational systems biology. Briefings in Bioinformatics, 1-14, 2019. DOI: 10.1093/bib/bbz014

2018

• Benson, Erik; Mohammed, Abdulmelik; Rayneau-Kirkhope, Daniel; Gådin, Andreas; Orponen, Pekka; Högberg, Björn. Effects of design choices on the stiffness of wireframe DNA origami structures. ACS Nano, 2018, Vol. 12, nro 9, pp. 9291-9299. DOI: 10.1021/acsnano.8b04148
• Mohammed, Abdulmelik; Orponen, Pekka; Pai, Sachith. Algorithmic design of cotranscriptionally folding 2D RNA origami structures. 17th International Conference on Unconventional Computation and Natural Computation, UCNC 2018, Fontainebleau, France, June 25-29, 2018. Proceedings, 2018, Springer Berlin Heidelberg, pp. 159-172. DOI: 10.1007/978-3-319-92435-9_12 <--- BEST PAPER AWARD!
• Orponen, Pekka. Design methods for 3D wireframe DNA nanostructures. Natural Computing, 2018. Vol. 17, nro 1, pp. 147-160. DOI: 10.1007/s11047-9647-9
• Vo, H. Thanh. A critical comparison of rejection-based algorithms for simulation of large biochemical reaction networks. Bulletin of Mathematical Biology, 2018, pp. 1-21. DOI: 10.1007/s11538-018-0462-y
• Vo, H. Thanh. Efficient anticorrelated variance reduction for stochastic simulation of biochemical reactions. IET Systems Biology, 2018 (in press). DOI: 10.1049/iet-syb.2018.5035
• Vo, H. Thanh; Zunino, Roberto; Priami, Corrado. Efficient finite-difference method for computing sensitivities of biochemical reactions. Proceedings of The Royal Society A, 474(2218), 2018. DOI: 10.1098/rspa.2018.0303

2017

• Johnsen, Aleck; Kao, Ming-Yang; Seki, Shinnosuke. A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis. Journal of Combinatorial Optimization, 2017. Vol. 33, nro 2, pp. 496-529. DOI:10.1007/s10878-015-9975-6
• Mohammed, Abdulmelik; Czeizler, Elena; Czeizler, Eugen. Computational modelling of the kinetic Tile Assembly Model using a rule-based approach. Theoretical Computer Science, 2017. Vol. 701, pp. 203-215. DOI: 10.1016/j.tcs.2017.07.014
• Mohammed, Abdulmelik; Hajij, Mustafa. Unknotted strand routings of triangulated meshes. 23rd International Conference on DNA Computing and Molecular Programming, DNA23, Austin TX, USA, Sep 25-28, 2017. Proceedings, 2017, Springer Berlin Heidelberg, pp. 45-63. DOI: 10.1007/978-3-319-66799-7_4

2016

• Benson, Erik; Mohammed, Abdulmelik; Bosco, Alessandro; Teixeira, Ana I.; Orponen, Pekka; Högberg, Björn. Computer-aided production of scaffolded DNA nanostructures from flat sheet meshes. Angewandte Chemie International Edition, 2016. Vol. 55, nro 31, pp. 8869-8872. DOI: 10.1002/anie.201602446
• Geary, Cody; Meunier, Pierre-Étienne; Schabanel, Nicolas; Seki, Shinnosuke. Programming biomolecules that fold greedily during transcription. 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, Kraków, Poland, August 22-26, 2016, Proceedings, 2016, Schloss Dagstuhl - Leibniz Center for Informatics, pp. 43:1-43:14. DOI: 10.4230/LIPIcs.MFCS.2016.43
• Kari, Lila; Kopecki, Steffen; Meunier, Pierre-Étienne; Patitz, Matthew J.; Seki, Shinnosuke. Binary pattern tile set synthesis is NP-hard. Algorithmica, 2016. Vol. 78, nro 1, pp. 1-46. DOI: 10.1007/s00453-016-0154-7

2015

• Benson, Erik; Mohammed, Abdulmelik; Gardell, Johan; Masich, Sergej; Czeizler, Eugen; Orponen, Pekka; Högberg, Björn. DNA rendering of polyhedral meshes at the nanoscale. Nature, 2015. Vol. 523, nro 7561, 441-444. DOI: 10.1038/nature14586. <--- HIGHLY CITED PAPER! (Web of Science)
• Chen, Ho-Lin; Doty, David; Seki, Shinnosuke. Program size and temperature in self-assembly. Algorithmica, 2015. Vol. 72, nro 3, pp. 884-899. DOI: 10.1007/s00453-014-9879-3.
• Czeizler, Eugen; Orponen, Pekka. Fault tolerant design and analysis of carbon nanotube circuits affixed on DNA origami tiles. IEEE Transactions on Nanotechnology, 2015. Vol. 14, nro 5, 817-877. DOI: 10.1109/tnano.2015.2455673.
• Geary, Cody; Meunier, Pierre-Étienne; Schabanel, Nicolas; Seki, Shinnosuke. Efficient universal computation by greedy molecular folding.. Technical report arXiv.org:1508.00510, August 2015, 23 pp.
• Ibarra, Oscar H.; Seki, Shinnosuke.F Semilinear sets and counter machines: A brief survey. Fundamenta Informaticae, 2015. Vol. 138, nro 1-2, pp. 61-76. DOI: 10.3233/FI-2015-1198".
• Jonoska, Natasa; Karpenko, Daria; Seki, Shinnosuke. Dynamic simulation of 1D cellular automata in the active aTAM. New Generation Computing, 2015. Vol. 33, nro 3, pp. 271-295. DOI: 10.1007/s00354-015-0302-7.
• Kari, Lila; Kopecki, Steffen; Meunier, Pierre-Étienne; Patitz, Matthew J.; Seki, Shinnosuke. Binary pattern tileset synthesis is NP-hard. 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I. 2015, Springer Berlin Heidelberg, pp. 1022-1034. DOI: 10.1007/978-3-662-47672-7_83.
• Kari, Lila; Kopecki, Steffen; Seki, Shinnosuke. 3-color bounded patterned self-assembly. Natural Computing, 2015. Vol. 14, nro 2, pp. 279-292. DOI: 10.1007/s11047-014-9434-9.
• Manea, Florin; Seki, Shinnosuke. Square-density increasing mappings. 10th International Conference, WORDS 2015, Kiel, Germany, Sep 14-17, 2015. pp. 160-169. DOI: 10.1007/978-3-319-23660-5_14.
• Meunier, Pierre-Étienne; Regnault, Damien. A pumping lemma for non-cooperative self-assembly. Technical report arXiv.org:1312.6668, December 2013 (Revised July 2015), 35 pp.
• Meunier, Pierre-Étienne. Noncooperative algorithms in self-assembly. 14th International Conference on Unconventional Computation and Natural Computation (UCNC 2015), Auckland, New Zealand, Aug 31 - Sep 4, 2015. pp. 263-276. DOI: 10.1007/978-3-319-21819-9_20.

Pre-2015

For older publications, please check the personal publication list of each member of the group.

Demos and Software

• Our newest software contribution DNAforge is a a generic design tool for DNA and RNA nanostructures based on 3D wireframe mesh models. The tool currently supports five design methods: the A-trail and spanning-tree methods for scaffolded DNA origami from (Benson et al. 2015) and (Veneziano et al. 2016), respectively; a cycle-cover method for scaffold-free DNA structures that generalises the one presented in (Wang et al. 2019); and the spanning-tree method for RNA origami from (Elonen et al. 2022), along with a variant that minimises the number of kissing loops in the eventual structure (in development).
• Sterna is a design tool (a Blender add-on) for generating RNA wireframe nanostructures from 3D meshes, following the method presented in (Elonen et al. 2022).
• We contributed a scaffold strand routing package BSCOR to the DNA-nanostructure design tool vHelix developed by the Högberg Lab at Karolinska Institutet, Stockholm. The algorithmic details of the routing scheme are described in the M.Sc. thesis of Abdulmelik Mohammed, and the whole design and synthesis process, together with experiments performed at the Högberg Lab, was presented in our recent joint article in Nature. (The nanoscale realisation of the Stanford bunny illustrated on the sidebar of this page was created using this methodology. The top frame shows the 3D mesh model, the middle frame the corresponding DNA strand design, and the bottom image an actual electron microscopy image of the synthesised bunny. The scale bar in the bottom frame measures 50 nm.)
• Asking questions about asynchronous processes, as we do when studying the theory of self-assembly, can also sometimes lead to unexpected results in seemingly unrelated areas: see Pijul, a version control system built on a sound theory of asynchronous work, yet not much slower (and sometimes faster) than heuristic-based systems (like git or mercurial).
• In Summer 2012, we pursued a pilot project on using techniques from distributed algorithmics to coordinate the actions of a small ensemble of low-cost swarm robots. For more details and a video clip, see the kilobots page by the group's alumnus Antti Halme.