Unified Design and Optimization Tools for Digital Microfluidic Biochips

Digital microfluidics is an emerging technology that provides fluid-handling capability on a chip. Biochips based on digital microfluidics have therefore enabled the automation of laboratory procedures in biochemistry. By reducing the rate of sample and reagent consumption, digital microfluidic biochips allow continuous sampling and analysis for real-time biochemical analysis, with application to clinical diagnostics, immunoassays, and DNA sequencing. Recent advances in technology and applications serve as a powerful driver for research on computer-aided design (CAD) tools for biochips.

This thesis research is focused on a design automation framework that addresses chip synthesis, droplet routing, control-pin mapping, testing and diagnosis, and error recovery. In contrast to prior work on automated design techniques for digital microfluidics, the emphasis here is on practical CAD optimization methods that can target different design problems in a unified manner. Constraints arising from the underlying technology and the application domain are directly incorporated in the optimization framework.

The avoidance of cross-contamination during droplet routing is a key design challenge for biochips. As a first step in this thesis research, a droplet-routing method based on disjoint droplet routes has been developed to avoid cross-contamination during the design of droplet flow paths. A wash-operation synchronization method has been developed to synchronize wash-droplet routing steps with sample/reagent droplet-routing steps by controlling the order of arrival of droplets at cross-contamination sites.

In pin-constrained digital microfluidic biochips, concurrently-implemented fluidic operations may involve pin-actuation conflicts if they are not carefully synchronized. A two-phase optimization method has been proposed to identify and synchronize these fluidic operations. The goal is to implement these fluidic operations without pin-actuation conflict, and minimize the duration of implementing the outcome sequence after synchronization.

Due to the interdependence between droplet routing and pin-count reduction, this thesis presents two optimization methods to concurrently solve the droplet-routing and the pin-mapping design problems. First, an integer linear programming (ILP)-based optimization method has been developed to minimize the number of control pins. Next an efficient heuristic approach has been developed to tackle the co-optimization problem.

Dependability is an important system attribute for microfluidic biochips. Robust testing methods are therefore needed to ensure correct results. This thesis presents a built-in self-test (BIST) method for digital microfluidic biochips. This method utilizes digital microfluidic logic gates to implement the BIST architecture. A cost-effective fault diagnosis method has also been proposed to locate a single defective cell, multiple

rows/columns with defective cells, as well as an unknown number of rows/columns-under-test with defective cells. A BIST method for on-line testing of digital microfluidic biochips has been proposed. An automatic test pattern generation (ATPG) method has been proposed for non-regular digital microfluidic chips. A pin-count-aware online testing method has been developed for pin-constrained designs to support the execution of both fault testing and the target bioassay protocol.

To better monitor and manage the execution of bioassays, control flow has been incorporated in the design and optimization framework. A synthesis method has been developed to incorporate control paths and an error-recovery mechanism during chip design. This method addresses the problem of recovering from fluidic errors that occur

during on-chip bioassay execution.

In summary, this thesis research has led to a set of unified design tools for digital microfluidics. This work is expected to reduce human effort during biochip design and biochip usage, and enable low-cost manufacture and more widespread adoption for laboratory procedures.