Solving Exact Cover Instances with Molecular-Motor-Powered Network-Based Biocomputation

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.

Figure 1

Encoding exact cover into network format. (A) Schematic rendering of a biocomputation network where kinesin-1 motors coat the bottom of 200 nm wide channels etched in poly(methyl methacrylate) (PMMA). The channels are explored by microtubules propelled by kinesin-1 motors. Note that, for the actin–myosin system, the channels were only 100 nm wide. (B) Binary encoding principle: elements of the target set X are mapped to bits of a binary number. Here, 1 is mapped to the most significant bit and 4 is mapped to the least significant bit. Each subset in S is converted to a binary number by the same mapping rule: i.e., a bit is set to 1 if the respective element in X is a member of the subset and set to 0 otherwise. Two examples of exact cover instances (X_aS_a and X_bS_b) are given. X_aS_a has a solution (highlighted in green) and X_bS_b does not. (C) Example network block that encodes the subset 0011. Agents arriving at input 0100 (blue) encounter a split junction (example denoted by a cyan rectangle) that allows the agents to randomly choose (diagonal path) or disregard (the path straight down) the subset encoded by this network block. If the subset is chosen, the number 0011 is added to the input 0100 and the agent arrives at the output 0111. Otherwise, the agent stays in the input column 0100. Because input subsets containing identical elements shall not be combined (as this would violate the rules of exact cover), all inputs that contain elements already present in the encoded subset start with a reset junction (example denoted by a red rectangle). This junction forces the agents to take the path straight down: i.e., disregarding the encoded subset. For example, an agent entering at input 0001 (red rectangle) can only leave at output 0001. The input and output rows are separated by two rows of pass junctions (example denoted by a blue rectangle) that force agents to continue a diagonal path, incrementing the value of the binary number, or continue moving directly down and maintaining the value of the binary number. Thus, the number of pass junction rows ultimately defines which elements are contained in the encoded subset. A full network can contain many network blocks. The output of each network block constitutes the input to the next network block, enabling the combination of many subsets (see Figures 2 and 4 for examples). (D) Scanning electron micrographs of examples for each junction type. The color of the frame corresponds to the rectangles in (C). Note that the SEM images were taken for junctions etched in SiO₂ instead of PMMA, because PMMA decomposes under electron radiation. Adapted with permission under a Creative Commons Attribution 4.0 license from ref (13). Copyright 2021 IOP Publishing.

Figure 2

Five-set Exact Cover instances encoded into network format. (A, C) Instance E32₁ (A) and instance E32₀ (B) including the binary mapping of the given target sets X₁ and X₂ as well as the subsets in S₁ and S₂ as described in detail in Figure 1B. (B, D) Networks encoding instance E32₁ (B) and instance E32₀ (D), which enable agents exploring the respective network to randomly choose subcollections from S₁ or S₂, following the rules defined by Exact Cover as explained in Figure 1C. The solution to the Exact Cover instance encoded by the network can be identified by checking whether agents exit at the binary number that represents the target set (green arrows in (B) and (D)). If a significant number of agents arrive at that particular exit, then the Exact Cover instance does have a solution; otherwise, it does not. (A, B) Exact Cover instance that has a solution. (C, D) Exact Cover instance that has no solution. (B, D) Blue arrows indicate network entrances; correct paths are highlighted in blue. Note that the closed channels at the right edge of the network ensure that filaments reaching these paths are forced to detach from the network and that no correct path leads to these channels. Therefore, only filaments making errors can reach them.

Figure 3

Successful operation of optimized Exact Cover networks with 5 sets (32 potential solutions) by the actin–myosin system. Optimized networks encoding Exact Cover instances E32₁ (A, B) and E32₀ (C, D). (A, C) Standard deviation projection of 2500 frames of 0.2 s time-lapse fluorescence micrographs of computing networks. Network paths that were more frequently visited by actin filaments are brighter. The micrograph in (A) has a smaller field of view, because it was acquired with a higher magnification objective. (B, D) Number of actin filaments counted at each exit. RGB colors indicate probabilities that the respective counts correspond to a correct (more green) or an incorrect (more red) exit. Error bars represent the counting error (square root of the respective value). Values above the green dash-dotted lines are significantly correct exits (p < 0.05), and values below the magenta dotted lines are significantly incorrect exits (p < 0.05). The rightmost exits represent the solution to the Exact Cover instances. The insets give the probabilities that the respective Exact Cover instance had a solution. Probabilities were estimated as described in section S1 in the Supporting Information. In total, the calculations took 0.14 h for each network.

Figure 4

Layouts of reverse Exact Cover devices to solve an Exact Cover problem with 10 sets, which has 1024 solutions. (A) Network layout of the Exact Cover instance E1024₁ corresponding to the binary numbers 00000011, 00000101 and 00000110, 00000111, 00001001, 00010011, 11100000, 11101010, 11110000, 11110100. This Exact Cover instance has a solution, which is indicated by the green double arrow. (B) Network layout of the Exact Cover instance E1024₀ corresponding to the binary numbers 00000011, 00000101 and 00000110, 00000111, 00001101, 00010011, 11100000, 11101010, 11110000, 11110100. This Exact Cover instance has no solution. Correct paths are highlighted in blue.

Figure 5

Microtubule results for the large network of Exact Cover instances with 10 sets: (A, C, E) Instance E1024₁ with exactly one solution (indicated by the green double arrow in (A)). (B, D, F) Instance E1024₀. (A, B) Standard deviation plots of 3600 frames of 5 s time-lapse fluorescence micrographs of microtubules moving through the computational network. Paths that were more frequently visited by microtubules are brighter. (A) The green double arrow highlights where paths from the forward and reverse network meet, indicating that this instance has a solution. (C–F) Number of microtubules counted at each exit of the (C, D) forward and (E, F) reverse halves of the Exact Cover network. RGB colors indicate probabilities that the respective counts correspond to a correct (more green) or an incorrect (more red) exit. Error bars represent the counting error (square root of the respective value). Values above the green dash-dotted lines are significant correct exits (p < 0.05), and values below the magenta dotted lines are significant incorrect exits (p < 0.05). In total, the calculation took 6 h for each network.