Search

The 3-satisfiability Problem (3-SAT) is a demanding combinatorial problem that is of central importance among the nondeterministic polynomial (NP) complete problems, with applications in circuit design, artificial intelligence, and logistics. Even with optimized algorithms, the solution space that needs to be explored grows exponentially with the increasing size of 3-SAT instances. Thus, large 3-SAT instances require excessive amounts of energy to solve with serial electronic computers. Network-based biocomputation (NBC) is a parallel computation approach with drastically reduced energy consumption. NBC uses biomolecular motors to propel cytoskeletal filaments through nanofabricated networks that encode mathematical problems. By stochastically exploring possible paths through the networks, the cytoskeletal filaments find possible solutions. However, to date, no NBC algorithm for 3-SAT has been available. Herein, an algorithm that converts 3-SAT into an NBC-compatible network format is reported and four small 3-SAT instances (with up to three variables and five clauses) using the actin–myosin biomolecular motor system are experimentally solved. Because practical polynomial conversions to 3-SAT exist for many important NP complete problems, the result opens the door to enable NBC to solve small instances of a wide range of problems.

Information processing by traditional, serial electronic processors consumes an ever-increasing part of the global electricity supply. An alternative, highly energy efficient, parallel computing paradigm is network-based biocomputation (NBC). In NBC a given combinatorial problem is encoded into a nanofabricated, modular network. Parallel exploration of the network by a very large number of independent molecular-motor-propelled protein filaments solves the encoded problem. Here we demonstrate a significant scale-up of this technology by solving four instances of Exact Cover, a nondeterministic polynomial time (NP) complete problem with applications in resource scheduling. The difficulty of the largest instances solved here is 128 times greater in comparison to the current state of the art for NBC., QC 20220823

Network-based biocomputation (NBC) is an alternative, parallel computation approach that can potentially solve technologically important, combinatorial problems with much lower energy consumption than electronic processors. In NBC, a combinatorial problem is encoded into a physical, nanofabricated network. The problem is solved by biological agents (such as cytoskeletal filaments driven by molecular motors) that explore all possible pathways through the network in a massively parallel and highly energy-efficient manner. Whereas there is currently a rapid development in the size and types of problems that can be solved by NBC in proof-of-principle experiments, significant challenges still need to be overcome before NBC can be scaled up to fill a technological niche and reach an industrial level of manufacturing. Here, we provide a roadmap that identifies key scientific and technological needs. Specifically, we identify technology benchmarks that need to be reached or overcome, as well as possible solutions for how to achieve this. These include methods for large-scale production of nanoscale physical networks, for dynamically changing pathways in these networks, for encoding information onto biological agents, for single-molecule readout technology, as well as the integration of each of these approaches in large-scale production. We also introduce figures of merit that help analyze the scalability of various types of NBC networks and we use these to evaluate scenarios for major technological impact of NBC. A major milestone for NBC will be to increase parallelization to a point where the technology is able to outperform the current run time of electronic processors. If this can be achieved, NBC would offer a drastic advantage in terms of orders of magnitude lower energy consumption. In addition, the fundamentally different architecture of NBC compared to conventional electronic computers may make it more advantageous to use NBC to solve certain types of problems and

Molecular motor-driven filament systems have been extensively explored for biomedical and nanotechnological applications such as lab-on-chip molecular detection or network-based biocomputation. In these applications, filament transport conventionally occurs in two dimensions (2D), often guided along open, topographically and/or chemically structured channels which are coated by molecular motors. However, at crossing points of different channels the filament direction is less well determined and, though crucial to many applications, reliable guiding across the junction can often not be guaranteed. We here present a three-dimensional (3D) approach that eliminates the possibility for filaments to take wrong turns at junctions by spatially separating the channels crossing each other. Specifically, 3D junctions with tunnels and overpasses were manufactured on glass substrates by two-photon polymerization, a 3D fabrication technology where a tightly focused, femtosecond-pulsed laser is scanned in a layer-to-layer fashion across a photo-polymerizable inorganic-organic hybrid polymer (ORMOCER®) with µm resolution. Solidification of the polymer was confined to the focal volume, enabling the manufacturing of arbitrary 3D microstructures according to computer-aided design data. Successful realization of the 3D junction design was verified by optical and electron microscopy. Most importantly, we demonstrated the reliable transport of filaments, namely microtubules propelled by kinesin-1 motors, across these 3D junctions without junction errors. Our results open up new possibilities for 3D functional elements in biomolecular transport systems, in particular their implementation in biocomputational networks., QC 20220425

Significant advancements have been made towards exploitation of naturally available molecular motors and their associated cytoskeletal filaments in nanotechnological applications. For instance, myosin motors and actin filaments from muscle have been used with the aims to establish new approaches in biosensing and network-based biocomputation. The basis for these developments is a version of the in vitro motility assay (IVMA) where surface-adsorbed myosin motors propel the actin filaments along suitably derivatized nano-scale channels on nanostructured chips. These chips are generally assembled into custom-made microfluidic flow cells. For effective applications, particularly in biocomputation, it is important to appreciably prolong function of the biological system. Here, we systematically investigated potentially critical factors necessary to achieve this, such as biocompatibility of different components of the flow cell, the degree of air exposure, assay solution composition and nanofabrication methods. After optimizing these factors we prolonged the function of actin and myosin in nanodevices for biocomputation from 60 min. In addition, we demonstrated that further optimizations could increase motility run times to >20 h. Of great importance for the latter development was a switch of glucose oxidase in the chemical oxygen scavenger system (glucose oxidase-glucose-catalase) to pyranose oxidase, combined with the use of blocking actin (non-fluorescent filaments that block dead motors). To allow effective testing of these approaches we adapted commercially available microfluidic channel slides, for the first time demonstrating their usefulness in the IVMA. As part of our study, we also demonstrate that myosin motor fragments can be stored at -80 degrees C for more than 10 years before use for nanotechnological purposes. This extended shelf-life is important for the sustainability of network-based biocomputation., QC 20220425