On-chip network-based computation, using biological agents, is a new hardware-embedded approach which attempts to find solutions to combinatorial problems, in principle, in a shorter time than the fast, but sequential electronic computers. This analytical review starts by describing the underlying mathematical principles, presents several types of combinatorial (including NP-complete) problems and shows current implementations of proof of principle developments. Taking the subset sum problem as example for in-depth analysis, the review presents various options of computing agents, and compares several possible operation 'run modes' of network-based computer systems. Given the brute force approach of network-based systems for solving a problem of input size C, 2C solutions must be visited. As this exponentially increasing workload needs to be distributed in space, time, and per computing agent, this review identifies the scaling-related key technological challenges in terms of chip fabrication, readout reliability and energy efficiency. The estimated computing time of massively parallel or combinatorially operating biological agents is then compared to that of electronic computers. Among future developments which could considerably improve network-based computing, labelling agents 'on the fly' and the readout of their travel history at network exits could offer promising avenues for finding hardware-embedded solutions to combinatorial problems.

Department of Bioengineering McGill University Montreal Quebec Canada H3A 0E9

Department of Chemical Engineering University of Chemistry and Technology Prague Technická 5 166 28 Prague 6 Czech Republic

Molecular Sense Ltd Liverpool L36 8HT UK

School of Mathematical Sciences Queensland University of Technology Brisbane QLD 4000 Australia

Erratum v

Interface Focus. 2019 Oct 6;9(5):20190051. doi: 10.1098/rsfs.2019.0051. PubMed

Zobrazit více v PubMed

Nam GJ, Sakallah KA, Rutenbar RA. 2002. A new FPGA detailed routing approach via search-based Boolean satisfiability. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 21, 674–684. (10.1109/TCAD.2002.1004311) DOI

Fraenkel AS. 1993. Complexity of protein folding. Bull. Math. Biol. 55, 1199–1210. (10.1007/BF02460704) PubMed DOI

Pierce NA, Winfree E. 2003. Protein design is NP-hard. Protein Eng. 15, 779–782. (10.1093/protein/15.10.779) PubMed DOI

Hopfield JJ, Tank DW. 1985. ‘Neural’ computation of decisions in optimization problems. Biol. Cybern. 52, 141–152. PubMed

Massacci F. 1996. Contextual reasoning is NP-complete. In Proc. 13th National Conf. on Artificial Intelligence, Portland, OR, USA, 4–8 August 1996, vol. 1, pp. 621–626.

Brandes U, Delling D, Gaertler M, Gorke R, Hoefer M, Nikoloski Z, Wagner D. 2008. On modularity clustering. IEEE Trans. Knowl. Data Eng. 20, 172–188. (10.1109/TKDE.2007.190689) DOI

Aaronson S. 2005. Guest Column: NP-complete problems and physical reality. ACM SIGACT News 36, 30–52. (10.1145/1052796.1052804) DOI

Hanson KL, Nicolau DV, Filipponi L, Wang L, Lee AP, Nicolau DV. 2006. Fungi use efficient algorithms for the exploration of microfluidic networks. Small 2, 1212–1220. (10.1002/smll.200600105) PubMed DOI

Adleman LM. 1994. Molecular computation of solutions to combinatorial problems. Science 266, 1021–1024. (10.1126/science.7973651) PubMed DOI

Lipton R. 1995. DNA solution of hard computational problems. Science 268, 542–545. (10.1126/science.7725098) PubMed DOI

Mao C, Labean TH, Reif JH, Seeman NC. 2000. Logical computation using algorithmic self-assembly of DNA triple-crossover molecules. Nature 407, 493–496. (10.1038/35035038) PubMed DOI

Qian L, Winfree E. 2011. Scaling up digital circuit computation with DNA strand displacement cascades. Science 332, 1196–1201. (10.1126/science.1200520) PubMed DOI

Beaver D. 1995. Computing with DNA. J. Comput. Biol. 2, 1–7. (10.1089/cmb.1995.2.1) PubMed DOI

Braich RS, Chelyapov N, Johnson C, Rothemund PWK, Adleman L. 2002. Solution of a 20-variable 3-SAT problem on a DNA computer. Science 296, 499–502. (10.1126/science.1069528) PubMed DOI

Ouyang Q, Kaplan PD, Liu S, Libchaber A. 1997. DNA solution of the maximal clique problem. Science 278, 446–449. (10.1126/science.278.5337.446) PubMed DOI

Reif JH. 2011. Scaling up DNA computation. Science 332, 1156–1157. (10.1126/science.1208068) PubMed DOI

Ladd TD, Jelezko F, Laflamme R, Nakamura Y, Monroe C, O'brien JL. 2010. Quantum computers. Nature 464, 45–53. (10.1038/nature08812) PubMed DOI

Chiu DT, Pezzoli E, Wu H, Stroock AD, Whitesides GM. 2001. Using three-dimensional microfluidic networks for solving computationally hard problems. Proc. Natl Acad. Sci. USA 98, 2961–2966. (10.1073/pnas.061014198) PubMed DOI PMC

Nicolau DV, Nicolau DV, Solana G, Hanson KL, Filipponi L, Wang L, Lee AP. 2006. Molecular motors-based micro- and nano-biocomputation devices. Microelectron. Eng. 83, 1582–1588. (10.1016/j.mee.2006.01.198) DOI

Nicolau DV, et al. 2016. Parallel computation with molecular-motor-propelled agents in nanofabricated networks. Proc. Natl Acad. Sci. USA 113, 2591–2596. (10.1073/pnas.1510825113) PubMed DOI PMC

Caulfield HJ, Dolev S. 2010. Why future supercomputing requires optics. Nat. Photonics 4, 261–263. (10.1038/nphoton.2010.94) DOI

Schnorr CP, Euchner M. 1994. Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66, 181–199. (10.1007/BF01581144) DOI

Kate A, Goldberg I. 2011. Generalizing cryptosystems based on the subset sum problem. Int. J. Inf. Secur. 10, 189–199. (10.1007/s10207-011-0129-2) DOI

Badawi AA, Veeravalli B, Aung KMM, Hamadicharef B. 2018. Accelerating subset sum and lattice based public-key cryptosystems with multi-core CPUs and GPUs. J. Parallel Distrib. Comput. 119, 179–190. (10.1016/j.jpdc.2018.04.014) DOI

Fréville A. 2004. The multidimensional 0–1 knapsack problem: an overview. Eur. J. Oper. Res. 155, 1–21. (10.1016/S0377-2217(03)00274-1) DOI

Darmann A, Nicosia G, Pferschy U, Schauer J. 2014. The Subset Sum game. Eur. J. Oper. Res. 233, 539–549. (10.1016/j.ejor.2013.08.047) PubMed DOI PMC

Oltean M, Groşan C, Oltean M. 2004. Designing digital circuits for the knapsack problem. In Computational science: ICCS 2004 (eds M Bubak, GD van Albada, PMA Sloot, J Dongarra). Lecture Notes in Computer Science, vol. 3038, pp. 1257–1264. Berlin, Germany: Springer (10.1007/978-3-540-24688-6_162) DOI

Oltean M, Muntean O. 2009. Solving the subset-sum problem with a light-based device. Nat. Comput. 8, 321–331. (10.1007/s11047-007-9059-3) DOI

Wu Q, Hao JK. 2015. A review on algorithms for maximum clique problems. Eur. J. Oper. Res. 242, 693–709. (10.1016/j.ejor.2014.09.064) DOI

Hwang FK, Richards DS. 1992. Steiner tree problems. Networks 22, 55–89. (10.1002/net.3230220105) DOI

Liu L, Song Y, Zhang H, Ma H, Vasilakos AV. 2015. Physarum optimization: a biology-inspired algorithm for the Steiner tree problem in networks. IEEE Trans. Comput. 64, 819–832.

Nakagaki T, Kobayashi R, Nishiura Y, Ueda T. 2004. Obtaining multiple separate food sources: behavioural intelligence in the Physarum plasmodium. Proc. R. Soc. Lond. B 271, 2305–2310. (10.1098/rspb.2004.2856) PubMed DOI PMC

Bektas T. 2006. The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34, 209–219. (10.1016/j.omega.2004.10.004) DOI

Matai R, Singh S, Mittal ML. 2010. Traveling salesman problem: an overview of applications, formulations, and solution approaches. In Traveling salesman problem (ed. Davendra D.). IntechOpen; (10.5772/12909) DOI

Jones J, Adamatzky A. 2014. Computation of the travelling salesman problem by a shrinking blob. Nat. Comput. 13, 1–16. (10.1007/s11047-013-9401-x) DOI

Dorigo M, Gambardella LM. 1997. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput. 1, 53–66. (10.1109/4235.585892) DOI

Mitra D, Roy S, Bhattacharjee S, Chakrabarty K, Bhattacharya BB. 2014. On-chip sample preparation for multiple targets using digital microfluidics. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 33, 1131–1144. (10.1109/TCAD.2014.2323200) DOI

Wu K, De Abajo JG, Soci C, Shum PP, Zheludev NI. 2014. An optical fiber network oracle for NP-complete problems. Light Sci. Appl. 3, e147.

Funke S, Nusser A, Storandt S. 2017. The simultaneous maze solving problem In 31st AAAI Conference on Artificial Intelligence, AAAI 2017.

Held M, Edwards C, Nicolau DV. 2008. Examining the behaviour of fungal cells in microconfined mazelike structures Proc. SPIE 6859, 68590U (10.1117/12.759453) DOI

Nakagaki T, Yamada H, Tóth Á. 2000. Maze-solving by an amoeboid organism. Nature 407, 470 (10.1038/35035159) PubMed DOI

Ntinas V, Vourkas I, Sirakoulis GC, Adamatzky AI. 2017. Oscillation-based slime mould electronic circuit model for maze-solving computations. IEEE Trans. Circuits Syst. Regul. Pap. 64, 1552–1563. (10.1109/TCSI.2016.2566278) DOI

Paolillo A, Faragasso A, Oriolo G, Vendittelli M. 2017. Vision-based maze navigation for humanoid robots. Auton. Robots 41, 293–309. (10.1007/s10514-015-9533-1) DOI

Qin J, Wheeler AR. 2007. Maze exploration and learning in C. elegans. Lab. Chip 7, 186–192. (10.1039/B613414A) PubMed DOI

Jellinger KA. 2007. Comparative cognition: experimental exploration of animal intelligence. Eur. J. Neurol. 14, e34 (10.1111/j.1468-1331.2007.01840.x) PubMed DOI

Held M, Binz M, Edwards C, Nicolau DV. 2009. Dynamic behaviour of fungi in microfluidics—a comparative study Proc. SPIE 7182, 718213 (10.1117/12.822464) DOI

Held M, Edwards C, Nicolau DV. 2011. Probing the growth dynamics of Neurospora crassa with microfluidic structures. Fungal Biol. 115, 493–505. (10.1016/j.funbio.2011.02.003) PubMed DOI

Park S, Wolanin PM, Yuzbashyan EA, Silberzan P, Stock JB, Austin RH. 2003. Motion to form a quorum. Science 301, 188 (10.1126/science.1079805) PubMed DOI

Asenova E, Lin HY, Fu E, Nicolau DV, Nicolau DV. 2016. Optimal fungal space searching algorithms. IEEE Trans. Nanobioscience 15, 613–618. PubMed

Malik S, Zhang L. 2009. Boolean satisfiability from theoretical hardness to practical success. Commun. ACM 52, 76–82. (10.1145/1536616.1536637) DOI

Boneh A, Hofri M. 1997. The coupon-collector problem revisited—a survey of engineering problems and computational methods. Commun. Stat. Part C Stoch. Models 13, 39–66. (10.1080/15326349708807412) DOI

Fuerstman MJ, Deschatelets P, Kane R, Schwartz A, Kenis PJA, Deutch JM, Whitesides GM, 2003. Solving mazes using microfluidic networks. Langmuir 19, 4714–4722. (10.1021/la030054x) DOI

Walther A, Müller AHE. 2013. Janus particles: synthesis, self-assembly, physical properties, and applications. Chem. Rev. 113, 5194–5261. (10.1021/cr300089t) PubMed DOI

Howse JR, Jones RAL, Ryan AJ, Gough T, Vafabakhsh R, Golestanian R. 2007. Self-motile colloidal particles: from directed propulsion to random walk. Phys. Rev. Lett. 99, 048102 (10.1103/PhysRevLett.99.048102) PubMed DOI

Garcia-Pichel F. 1989. Rapid bacterial swimming measured in swarming cells of Thiovulum majus. J. Bacteriol. 171, 3560–3563. (10.1128/jb.171.6.3560-3563.1989) PubMed DOI PMC

Vaituzis Z, Doetsch RN. 1969. Motility tracks: technique for quantitative study of bacterial movement. Appl. Microbiol. 17, 584–588. PubMed PMC

Schlegel HG. 1985. Allgemeine mikrobiologie. Stuttgart, Germany: Georg Thieme Verlag.

Weinstock MT, Hesek ED, Wilson CM, Gibson DG. 2016. Vibrio natriegens as a fast-growing host for molecular biology. Nat. Methods 13, 849–851. (10.1038/nmeth.3970) PubMed DOI

Herzog B, Wirth R. 2012. Swimming behavior of selected species of Archaea. Appl. Environ. Microbiol. 78, 1670–1674. (10.1128/AEM.06723-11) PubMed DOI PMC

Brennen AC, Winet H. 1977. Fluid mechanics of propulsion by cilia and flagella. Annu. Rev. Fluid Mech. 9, 339–398. (10.1146/annurev.fl.09.010177.002011) DOI

Sleigh MA, Blake JR. 1977. Methods of ciliary propulsion and their size limitations. In Scale effects in animal locomotion (ed. Pedley TJ.), pp. 234–236. New York: NY: Academic Press, Inc.

Hahm JH, Kim S, Diloreto R, Shi C, Lee SJV, Murphy CT, Nam HG. 2015. C. elegans maximum velocity correlates with healthspan and is maintained in worms with an insulin receptor mutation. Nat. Commun. 6, 8919 (10.1038/ncomms9919) PubMed DOI PMC

Nicolau DV, Jr, et al. 2016. Reply to Einarsson: The computational power of parallel network exploration with many bioagents. Proc. Natl Acad. Sci. USA 113, E3188 (10.1073/pnas.1605214113) PubMed DOI PMC

Potsaid B, Bellouard Y, Wen JT. 2005. Adaptive Scanning Optical Microscope (ASOM): a multidisciplinary optical microscope design for large field of view and high resolution imaging. Opt. Express 13, 6504–6518. (10.1364/OPEX.13.006504) PubMed DOI

Einarsson J. 2016. New biological device not faster than regular computer. Proc. Natl Acad. Sci. USA 113, E3187 (10.1073/pnas.1603944113) PubMed DOI PMC

Pisinger D. 1999. Linear time algorithms for knapsack problems with bounded weights. J. Algorithms 33, 1–14. (10.1006/jagm.1999.1034) DOI

Mckee SA. 2004. Reflections on the memory wall In Proc. 1st Conf. on Computing Frontiers, Ischia, Italy, 14–16 April 2004, p. 162. New York, NY: ACM (10.1145/977091.977115) DOI

DOE/NNSA. 2014 Preliminary conceptual design for an exascale computing initiative. Washington, DC: US Department of Energy Office of Science and National Nuclear Security Administration. See https://www.science.energy.gov/~/media/ascr/ascac/pdf/meetings/20141121/Exascale_Preliminary_Plan_V11_sb03c.pdf.

King J, Yarkoni S, Raymond J, Ozdan I, King AD, Mohammadi Nevisi M, Hilton JP, Mcgeoch CC. 2017. Quantum annealing amid local ruggedness and global frustration. D-Wave Technical Report Series. 2017(14-1003A-C).

Mitchell JG. 2002. The energetics and scaling of search strategies in bacteria. Am. Nat. 160, 727–740. (10.1086/343874) PubMed DOI

Mitchell JG, Kogure K. 2006. Bacterial motility: links to the environment and a driving force for microbial physics. FEMS Microbiol. Ecol. 55, 3–16. (10.1111/j.1574-6941.2005.00003.x) PubMed DOI

Landauer R. 2000. Irreversibility and heat generation in the computing process. IBM J. Res. Dev. 44, 261–269. (10.1147/rd.441.0261) DOI

Strohmaier E, Dongarra J, Simon H, Meuer M.2017. Top 500 Supercomputers. See https://www.top500.org/lists/top500/ .

Yin X, Li F, Bo X, Luo Z, Zuo X. 2017. Computation in chemistry: a summary of the development and models of DNA computing. Prog. Chem. 29, 1297–1315.

Lard M, Ten Siethoff L, Generosi J, Månsson A, Linke H. 2013. Molecular motor transport through hollow nanowires. Nano Lett. 14, 3041–3046. (10.1021/nl404714b) PubMed DOI

Balaz M, Månsson A. 2005. Detection of small differences in actomyosin function using actin labeled with different phalloidin conjugates. Anal. Biochem. 338, 224–236. (10.1016/j.ab.2004.12.012) PubMed DOI

Lard M, Ten Siethoff L, Månsson A, Linke H. 2013. Tracking actomyosin at fluorescence check points. Sci. Rep. 3, 1092 (10.1038/srep01092) PubMed DOI PMC

Ooms MD, Dinh CT, Sargent EH, Sinton D. 2016. Photon management for augmented photosynthesis. Nat. Commun. 7, 12699 (10.1038/ncomms12699) PubMed DOI PMC

Patterns of bacterial motility in microfluidics-confining environments

Zobrazit více v PubMed

figshare
10.6084/m9.figshare.c.4257845