Part I
Synthesis Techniques
As more bioassays are executed concurrently on a digital microfluidics-based biochip, system integration and application complexity are expected to increase steadily. Thus system-level design automation tools (e.g., synthesis tools) are needed to handle increasing biochip design complexity. Synthesis research for digital microfluidic biochips can benefit from classical CAD techniques, which is a well-studied problem, and advances in synthesis techniques for integrated circuits continue even today.
As stated in Section 1.3.2, we envisage that the synthesis of a digital microfluidic biochip can be divided into two major phases, referred to as architectural-level synthesis (i.e., high-level synthesis) and geometry-level synthesis (i.e., physical design), respectively. A behavioral model (e.g., sequencing graph model) for a biochemical assay is first obtained from the protocol for that assay. Note that by using discrete unit-volume droplets, a microfluidic function can be reduced to a set of repeated basic operations (i.e., moving one unit of fluid over one unit of instance). This âdigitizationâ method facilitates the implementation of many well-defined protocols for nano- and microscale bioassays on a microchip. A generic class of microdroplet-based bioassay protocols that can be applied to digital microfluidic biochips usually consists of the following steps:
1. Dispensing sample/reagent droplets into the microfluidic array
2. Transporting the droplets to some locations on the array for assays operations (e.g., mixing, dilution or optical detection)
3. Finally, moving the droplets of assay products or wastes out of the microfluidic array.
Based on the generated sequencing graph model, architectural-level synthesis is used to generate a macroscopic structure of the biochip; this structure is analogous to a structural register-transfer level (RTL) model in electronic CAD. This macroscopic model provides an assignment of assay functions to biochip resources, as well as a mapping of assay functions to time steps, based in part on the dependencies between them. Finally, geometry-level synthesis creates a physical representation at the geometrical level (i.e., the final layout of the biochip) consisting of the configuration of the microfluidic array, locations of reservoirs and dispensing ports, droplet routes, and other geometric details.
The goal of a synthesis procedure is to select a design that minimizes a certain cost function under resource constraints. For example, architectural-level synthesis for microfluidic biochips can be viewed as the problem of scheduling assay functions and binding them to a given number of resources so as to maximize parallelism, thereby decreasing response time. On the other hand, geometry-level synthesis addresses the placement of resources and the routing of droplets to satisfy objectives such as area or throughput. Defect/fault tolerance can also be included as a critical objective in the proposed synthesis method.
In architectural-level synthesis, both scheduling and resource-binding problems are addressed to generate a structural view of biochip design. As in the case of highlevel synthesis for integrated circuits, resource binding in the biochip synthesis flow refers to the mapping from bioassay operations to available functional resources. Scheduling determines the start times and stop times of all assay operations, subject to the precedence constraints imposed by the sequencing graph. In Chapter 2, we present the proposed architectural synthesis methodology based on integer linear programming and heuristic techniques for scheduling assay operations under resource constraints. Resource-binding problem is also investigated in this chapter.
A key problem in the geometry-level synthesis of biochips is the placement of microfluidic modules such as different types of mixers and storage units. Based on the results obtained from architectural-level synthesis (i.e., a schedule of bioassay operation, a set of microfluidic modules, and the binding of bioassay operations to modules), placement determines the locations of each module on the microfluidic array in order to optimize some design metrics. Chapter 3 presents a simulated annealing-based methodology to solve the microfluidic module problem in a computationally efficient manner.
In Chapter 4, we further propose a synthesis methodology that unifies operation scheduling, resource binding, and module placement. This method allows architectural design and physical design decisions to be made simultaneously. Moreover, the proposed technique, which is based on parallel recombinative simulated annealing, can also be used after fabrication to bypass defective cells in the microfluidic array.
Chapter 5 investigates another key problem in biochip physical design (i.e., droplet routing between modules and between modules and on-chip reservoirs). It follows architectural-level synthesis and module placement in the proposed synthesis flow. We present the first systematic routing method for digital microfluidic biochips; the proposed approach attempts to minimize the number of cells used for droplet routing, while satisfying constraints imposed by throughput considerations and fluidic properties.
1 Introduction
Recent advances in microfluidics technology have generated tremendous interest in the design and implementation of miniaturized devices for biochemical analysis [1,2,3,4]. These composite microsystems, referred to interchangeably in the literature as microfluidic biochips, lab-on-a-chip, and bioMEMS, offer a number of advantages over conventional laboratory procedures. They automate highly repetitive laboratory tasks by replacing cumbersome equipment with miniaturized and integrated systems, and they enable the handling of small amounts (e.g., nanoliters) of fluids. Thus they are able to provide ultrasensitive detection at significantly lower costs per assay than traditional methods, and in a significantly smaller amount of laboratory space.
Microfluidic biochips promise to revolutionize enzymatic analysis (e.g., glucose and lactate assays), DNA analysis (e.g., PCR and nucleic acid sequence analysis), proteomic analysis involving proteins and peptides, immunoassays, and toxicity monitoring [5,6]. An emerging application area for microfluidic biochips is clinical diagnostics, especially immediate point-of-care diagnosis of diseases [5,6]. Microfluidics can also be used for countering bioterrorism threats [7,8]. Microfluidics-based devices, capable of continuous sampling and real-time testing of air/water samples for biochemical toxins and other dangerous pathogens, can serve as an always-on âbio-smoke alarmâ for early warning.
The so-called first generation microfluidic biochips were based on continuous liquid flow through fabricated microchannels, and they were designed for simple biochemical analyses or assays [3,4]. Recently, a second-generation paradigm has emerged that manipulates liquids as discrete nanoliter droplets [9,10]. Following the analogy of digital electronics, this technology is referred to as digital microfluidics. In contrast to continuous-flow biochips, digital microflu...