| 1. |
- Korten, Till, et al.
(författare)
-
Design of network-based biocomputation circuits for the exact cover problem
- 2021
-
Ingår i: New Journal of Physics. - : IOP Publishing. - 1367-2630. ; 23:8
-
Tidskriftsartikel (refereegranskat)abstract
- Exact cover is a non-deterministic polynomial time (NP)-complete problem that is central to optimization challenges such as airline fleet planning and allocation of cloud computing resources. Solving exact cover requires the exploration of a solution space that increases exponentially with cardinality. Hence, it is time- and energy consuming to solve large instances of exact cover by serial computers. One approach to address these challenges is to utilize the inherent parallelism and high energy efficiency of biological systems in a network-based biocomputation (NBC) device. NBC is a parallel computing paradigm in which a given combinatorial problem is encoded into a graphical, modular network that is embedded in a nanofabricated planar device. The network is then explored in parallel using a large number of biological agents, such as molecular-motor-propelled protein filaments. The answer to the combinatorial problem can then be inferred by measuring the positions through which the agents exit the network. Here, we (i) show how exact cover can be encoded and solved in an NBC device, (ii) define a formalization that allows to prove the correctness of our approach and provides a mathematical basis for further studying NBC, and (iii) demonstrate various optimizations that significantly improve the computing performance of NBC. This work lays the ground for fabricating and scaling NBC devices to solve significantly larger combinatorial problems than have been demonstrated so far.
|
|
| 2. |
- Surendiran, Pradheebha, et al.
(författare)
-
Solving Exact Cover Instances with Molecular-Motor-Powered Network-Based Biocomputation
- 2022
-
Ingår i: ACS Nanoscience Au. - : American Chemical Society (ACS). - 2694-2496 .- 2694-2496.
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 3. |
- van Delft, Falco C. M. J. M., et al.
(författare)
-
Roadmap for network-based biocomputation
- 2022
-
Ingår i: Nano Futures. - : Institute of Physics Publishing (IOPP). - 2399-1984. ; 6:3
-
Forskningsöversikt (refereegranskat)abstract
- 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 instances that are easy to parallelize. To achieve these objectives, the purpose of this roadmap is to identify pre-competitive research domains, enabling cooperation between industry, institutes, and universities for sharing research and development efforts and reducing development cost and time.
|
|
| 4. |
- Zhu, Jingyuan, et al.
(författare)
-
Physical requirements for scaling up network-based biocomputation
- 2021
-
Ingår i: New Journal of Physics. - : Institute of Physics (IOP). - 1367-2630. ; 23:10
-
Tidskriftsartikel (refereegranskat)abstract
- The high energy consumption of electronic data processors, together with physical challenges limiting their further improvement, has triggered intensive interest in alternative computation paradigms. Here we focus on network-based biocomputation (NBC), a massively parallel approach where computational problems are encoded in planar networks implemented with nanoscale channels. These networks are explored by biological agents, such as biological molecular motor systems and bacteria, benefitting from their energy efficiency and availability in large numbers. We analyse and define the fundamental requirements that need to be fulfilled to scale up NBC computers to become a viable technology that can solve large NP-complete problem instances faster or with less energy consumption than electronic computers. Our work can serve as a guide for further efforts to contribute to elements of future NBC devices, and as the theoretical basis for a detailed NBC roadmap.
|
|
| 5. |
- Zhu, Jingyuan, et al.
(författare)
-
Solving the 3-Satisfiability Problem Using Network-Based Biocomputation
- 2022
-
Ingår i: Advanced Intelligent Systems. - : John Wiley & Sons. - 2640-4567. ; 4:12
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
