Something has to give: scaling combinatorial computing by biological agents exploring physical networks encoding NP-complete problems

Why cellular computations challenge our design principles

Biological systems inherently perform computations, inspiring synthetic biologists to engineer biological systems capable of executing predefined computational functions for diverse applications. Typically, this involves applying principles from the design of conventional silicon-based computers to create novel biological systems, such as genetic Boolean gates and circuits. However, the natural evolution of biological computation has not adhered to these principles, and this distinction warrants careful consideration. Here, we explore several concepts connecting computational theory, living cells, and computers, which may offer insights into the development of increasingly sophisticated biological computations. While conventional computers approach theoretical limits, solving nearly all problems that are computationally solvable, biological computers have the opportunity to outperform them in specific niches and problem domains. Crucially, biocomputation does not necessarily need to scale to rival or replicate the capabilities of electronic computation. Rather, efforts to re-engineer biology must recognise that life has evolved and optimised itself to solve specific problems using its own principles. Consequently, intelligently designed cellular computations will diverge from traditional computing in both implementation and application.

Engineering signalling pathways in mammalian cells

In mammalian cells, signalling pathways orchestrate cellular growth, differentiation and survival, as well as many other processes that are essential for the proper functioning of cells. Here we describe cutting-edge genetic-engineering technologies for the rewiring of signalling networks in mammalian cells. Specifically, we describe the recombination of native pathway components, cross-kingdom pathway transplantation, and the development of de novo signalling within cells and organelles. We also discuss how, by designing signalling pathways, mammalian cells can acquire new properties, such as the capacity for photosynthesis, the ability to detect cancer and senescent cell markers or to synthesize hormones or metabolites in response to chemical or physical stimuli. We also review the applications of mammalian cells in biocomputing. Technologies for engineering signalling pathways in mammalian cells are advancing basic cellular biology, biomedical research and drug discovery.

Optical Image Sensors for Smart Analytical Chemiluminescence Biosensors

Optical biosensors have emerged as a powerful tool in analytical biochemistry, offering high sensitivity and specificity in the detection of various biomolecules. This article explores the advancements in the integration of optical biosensors with microfluidic technologies, creating lab-on-a-chip (LOC) platforms that enable rapid, efficient, and miniaturized analysis at the point of need. These LOC platforms leverage optical phenomena such as chemiluminescence and electrochemiluminescence to achieve real-time detection and quantification of analytes, making them ideal for applications in medical diagnostics, environmental monitoring, and food safety. Various optical detectors used for detecting chemiluminescence are reviewed, including single-point detectors such as photomultiplier tubes (PMT) and avalanche photodiodes (APD), and pixelated detectors such as charge-coupled devices (CCD) and complementary metal-oxide-semiconductor (CMOS) sensors. A significant advancement discussed in this review is the integration of optical biosensors with pixelated image sensors, particularly CMOS image sensors. These sensors provide numerous advantages over traditional single-point detectors, including high-resolution imaging, spatially resolved measurements, and the ability to simultaneously detect multiple analytes. Their compact size, low power consumption, and cost-effectiveness further enhance their suitability for portable and point-of-care diagnostic devices. In the future, the integration of machine learning algorithms with these technologies promises to enhance data analysis and interpretation, driving the development of more sophisticated, efficient, and accessible diagnostic tools for diverse applications.

Microfluidics on lensless, semiconductor optical image sensors: challenges and opportunities for democratization of biosensing at the micro-and nano-scale

Optical image sensors are 2D arrays of pixels that integrate semiconductor photodiodes and field effect transistors for efficient photon conversion and processing of generated electrons. With technological advancements and subsequent democratization of these sensors, opportunities for integration with microfluidics devices are currently explored. 2D pixel arrays of such optical image sensors can reach dimensions larger than one centimeter with a sub-micrometer pixel size, for high spatial resolution lensless imaging with large field of view, a feat that cannot be achieved with lens-based optical microscopy. Moreover, with advancements in fabrication processes, the field of microfluidics has evolved to develop microfluidic devices with an overall size below one centimeter and individual components of sub-micrometer size, such that they can now be implemented onto optical image sensors. The convergence of these fields is discussed in this article, where we review fundamental principles, opportunities, challenges, and outlook for integration, with focus on contact-mode imaging configuration. Most recent developments and applications of microfluidic lensless contact-based imaging to the field of biosensors, in particular those related to the potential for point of need applications, are also discussed.

Nanolithographic Fabrication Technologies for Network-Based Biocomputation Devices

Network-based biocomputation (NBC) relies on accurate guiding of biological agents through nanofabricated channels produced by lithographic patterning techniques. Here, we report on the large-scale, wafer-level fabrication of optimized microfluidic channel networks (NBC networks) using electron-beam lithography as the central method. To confirm the functionality of these NBC networks, we solve an instance of a classical non-deterministic-polynomial-time complete ("NP-complete") problem, the subset-sum problem. The propagation of cytoskeletal filaments, e.g., molecular motor-propelled microtubules or actin filaments, relies on a combination of physical and chemical guiding along the channels of an NBC network. Therefore, the nanofabricated channels have to fulfill specific requirements with respect to the biochemical treatment as well as the geometrical confienement, with walls surrounding the floors where functional molecular motors attach. We show how the material stack used for the NBC network can be optimized so that the motor-proteins attach themselves in functional form only to the floor of the channels. Further optimizations in the nanolithographic fabrication processes greatly improve the smoothness of the channel walls and floors, while optimizations in motor-protein expression and purification improve the activity of the motor proteins, and therefore, the motility of the filaments. Together, these optimizations provide us with the opportunity to increase the reliability of our NBC devices. In the future, we expect that these nanolithographic fabrication technologies will enable production of large-scale NBC networks intended to solve substantially larger combinatorial problems that are currently outside the capabilities of conventional software-based solvers.

Patterns of bacterial motility in microfluidics-confining environments

Understanding the motility behavior of bacteria in confining microenvironments, in which they search for available physical space and move in response to stimuli, is important for environmental, food industry, and biomedical applications. We studied the motility of five bacterial species with various sizes and flagellar architectures (Vibrio natriegens, Magnetococcus marinus, Pseudomonas putida, Vibrio fischeri, and Escherichia coli) in microfluidic environments presenting various levels of confinement and geometrical complexity, in the absence of external flow and concentration gradients. When the confinement is moderate, such as in quasi-open spaces with only one limiting wall, and in wide channels, the motility behavior of bacteria with complex flagellar architectures approximately follows the hydrodynamics-based predictions developed for simple monotrichous bacteria. Specifically, V. natriegens and V. fischeri moved parallel to the wall and P. putida and E. coli presented a stable movement parallel to the wall but with incidental wall escape events, while M. marinus exhibited frequent flipping between wall accumulator and wall escaper regimes. Conversely, in tighter confining environments, the motility is governed by the steric interactions between bacteria and the surrounding walls. In mesoscale regions, where the impacts of hydrodynamics and steric interactions overlap, these mechanisms can either push bacteria in the same directions in linear channels, leading to smooth bacterial movement, or they could be oppositional (e.g., in mesoscale-sized meandered channels), leading to chaotic movement and subsequent bacterial trapping. The study provides a methodological template for the design of microfluidic devices for single-cell genomic screening, bacterial entrapment for diagnostics, or biocomputation.

Formal Semantics and Verification of Network-Based Biocomputation Circuits

Network-Based Biocomputation Circuits (NBCs) offer a new paradigm for solving complex computational problems by utilizing biological agents that operate in parallel to explore manufactured planar devices. The approach can also have future applications in diagnostics and medicine by combining NBCs computational power with the ability to interface with biological material. To realize this potential, devices should be designed in a way that ensures their correctness and robust operation. For this purpose, formal methods and tools can offer significant advantages by allowing investigation of design limitations and detection of errors before manufacturing and experimentation. Here we define a computational model for NBCs by providing formal semantics to NBC circuits. We present a formal verification-based approach and prototype tool that can assist in the design of NBCs by enabling verification of a given design’s correctness. Our tool allows verification of the correctness of NBC designs for several NP-Complete problems, including the Subset Sum, Exact Cover and Satisfiability problems and can be extended to other NBC implementations. Our approach is based on defining transition systems for NBCs and using temporal logic for specifying and proving properties of the design using model checking. Our formal model can also serve as a starting point for computational complexity studies of the power and limitations of NBC systems.

A scalable photonic computer solving the subset sum problem

The subset sum problem (SSP) is a typical nondeterministic-polynomial-time (NP)-complete problem that is hard to solve efficiently in time with conventional computers. Photons have the unique features of high propagation speed, strong robustness, and low detectable energy level and therefore can be promising candidates to meet the challenge. Here, we present a scalable chip built-in photonic computer to efficiently solve the SSP. We map the problem into a three-dimensional waveguide network through a femtosecond laser direct writing technique. We show that the photons sufficiently dissipate into the networks and search for solutions in parallel. In the case of successive primes, our approach exhibits a dominant superiority in time consumption even compared with supercomputers. Our results confirm the ability of light to realize computations intractable for conventional computers, and suggest the SSP as a good benchmarking platform for the race between photonic and conventional computers on the way toward "photonic supremacy."

Dual-phone illumination-imaging system for high resolution and large field of view multi-modal microscopy

In this paper we present for the first time a system comprised of two mobile phones, one for illumination and the other for microscopy, as a portable, user-friendly, and cost-effective microscopy platform for a wide range of applications. Versatile and adaptive illumination is made with a Retina display of an Apple mobile phone device. The phone screen is used to project various illumination patterns onto the specimen being imaged, each corresponding to a different illumination mode, such as bright-field, dark-field, point illumination, Rheinberg illumination, and fluorescence microscopy. The second phone (a Nokia phone) is modified to record microscopic images about the sample. This imaging platform provides a high spatial resolution of at least 2 μm, a large field-of-view of 3.6 × 2.7 mm, and a working distance of 0.6 mm. We demonstrate the performance of this platform for the visualization of microorganisms within microfluidic devices to gather qualitative and quantitative information regarding microorganism morphology, dimension, count, and velocity/trajectories in the x-y plane.

Computation by natural systems

Computation is a useful concept far beyond the disciplinary boundaries of computer science. Perhaps the most important class of natural computers can be found in biological systems that perform computation on multiple levels. From molecular and cellular information processing networks to ecologies, economies and brains, life computes. Despite ubiquitous agreement on this fact going back as far as von Neumann automata and McCulloch–Pitts neural nets, we so far lack principles to understand rigorously how computation is done in living, or active, matter. What is the ultimate nature of natural computation that has evolved, and how can we use these principles to engineer intelligent technologies and biological tissues?