A High-Performance Online Assay Interpreter for Digital Microfluidic Biochips
Abstract:
In the coming decade, microfluidic biochips, or labs-‐on-‐a-‐chip (LoCs), will automate and miniaturize repetitive laboratory experiments that are today performed by humans in domains such as enzymatic, proteomic, and DNA analysis, drug discovery, biomolecular recognition, molecular imaging, toxicity monitoring, and clinical diagnostics. LoC technology will replace manual execution of assays with automation and miniaturization, therefore achieving higher throughput than is available with today’s technologies; moreover, they will be programmed using text based languages, similar in principle to computer programming today. Industrial laboratories will desire concurrent execution of multiple assays on one or more large LoCs. The objective of this research is to develop a prototype system that facilitates the dynamic execution of multiple assays on an array of one or more LoCs. Assays will arrive in an online fashion and a microfluidic operating system/virtual machine will interpret them in real time; multiple assays will execute in parallel on the microfluidic device. We present a software interpreter for discrete droplet-‐based digital microfluidic biochips (DMFBs). These biochips manipulate droplets of liquid on a 2-‐dimensional grid. Each cell in the grid can perform different functions, namely droplet storage, transport, mixing, splitting and merging. The interpreter imposes a mesh-‐like virtual architecture on the DMFB, which imposes a strict separation between droplet transport and other droplet functions. Certain cells within the topology are only used for droplet transport, while other cells perform the other fluidic operations. The cells responsible for transportation are organized into streets and rotaries (i.e., traffic circles for droplets), while the other cells are organized into larger blocks called chambers. Altogether, the overall organization of the virtual architecture has the appearance of a well-‐planned city. The interpreter solves the same three problems as a traditional static assay compiler, but does so in real-‐time, aided by the virtual architecture:
- Dynamic scheduling, motivated by thread scheduling in operating systems, is employed, in lieu of static scheduling.
- The interpreter dynamically selects a chamber to execute each fluidic operation; the search space is much smaller than traditional formulations of the module placement problem, where modules can be placed at virtually any location on the chip (subject to appropriate constraints). The virtual architecture ensures that no modules are placed in a way that prevents a droplet from reaching its destination, which has been a concern in traditional assay compilation.
- Droplet routing, an NP-‐complete problem, is replaced with deadlock-‐free mesh routing algorithms for computer networks, with appropriate adaptations for DMFBs. This significantly reduces the software overhead required to route a large number of droplets concurrently.
Initial research validates our approach to deadlock-‐free routing as a reliable, real-‐time droplet transport protocol and demonstrates that deterministic routing algorithms yield higher throughput than adaptive algorithms.
Submitted by Philip Brisk
on
Abstract:
In the coming decade, microfluidic biochips, or labs-‐on-‐a-‐chip (LoCs), will automate and miniaturize repetitive laboratory experiments that are today performed by humans in domains such as enzymatic, proteomic, and DNA analysis, drug discovery, biomolecular recognition, molecular imaging, toxicity monitoring, and clinical diagnostics. LoC technology will replace manual execution of assays with automation and miniaturization, therefore achieving higher throughput than is available with today’s technologies; moreover, they will be programmed using text based languages, similar in principle to computer programming today. Industrial laboratories will desire concurrent execution of multiple assays on one or more large LoCs. The objective of this research is to develop a prototype system that facilitates the dynamic execution of multiple assays on an array of one or more LoCs. Assays will arrive in an online fashion and a microfluidic operating system/virtual machine will interpret them in real time; multiple assays will execute in parallel on the microfluidic device. We present a software interpreter for discrete droplet-‐based digital microfluidic biochips (DMFBs). These biochips manipulate droplets of liquid on a 2-‐dimensional grid. Each cell in the grid can perform different functions, namely droplet storage, transport, mixing, splitting and merging. The interpreter imposes a mesh-‐like virtual architecture on the DMFB, which imposes a strict separation between droplet transport and other droplet functions. Certain cells within the topology are only used for droplet transport, while other cells perform the other fluidic operations. The cells responsible for transportation are organized into streets and rotaries (i.e., traffic circles for droplets), while the other cells are organized into larger blocks called chambers. Altogether, the overall organization of the virtual architecture has the appearance of a well-‐planned city. The interpreter solves the same three problems as a traditional static assay compiler, but does so in real-‐time, aided by the virtual architecture:
- Dynamic scheduling, motivated by thread scheduling in operating systems, is employed, in lieu of static scheduling.
- The interpreter dynamically selects a chamber to execute each fluidic operation; the search space is much smaller than traditional formulations of the module placement problem, where modules can be placed at virtually any location on the chip (subject to appropriate constraints). The virtual architecture ensures that no modules are placed in a way that prevents a droplet from reaching its destination, which has been a concern in traditional assay compilation.
- Droplet routing, an NP-‐complete problem, is replaced with deadlock-‐free mesh routing algorithms for computer networks, with appropriate adaptations for DMFBs. This significantly reduces the software overhead required to route a large number of droplets concurrently.
Initial research validates our approach to deadlock-‐free routing as a reliable, real-‐time droplet transport protocol and demonstrates that deterministic routing algorithms yield higher throughput than adaptive algorithms.