Optimization Tools for the Design of Reconfigurable Digital Microfluidic Biochips

Microfluidics-based biochips combine electronics with biochemistry to open new application areas such as point-of-care medical diagnostics, on-chip DNA analysis, automated drug discovery and protein crystallization. Bioassays can be mapped to microfluidic arrays using synthesis tools and they can be executed through the electronic manipulation of sample and reagent droplets. The 2007 International Technology Roadmap for Semiconductors articulates the need for innovations in biochip and microfluidics as part of functional diversification ("Higher Value Systems" and "More than Moore"). This document also highlights "Medical" as being a System Driver for 2009 This thesis envisions an automated design flow for microfluidic biochips, in the same way as design automation revolutionized IC design in the 80s and 90s. Electronic design-automation techniques are leveraged whenever possible, and new design-automation solutions are developed for problems that are unique to digital microfluidics. Biochip users (e.g., chemists, nurses, doctors and clinicians) and the biotech/pharmaceutical industry will adapt more easily to new technology if appropriate design tools and in-system automation methods are made available. The thesis is focused on a design automation framework that addresses optimization problems related to layout, synthesis, droplet routing, testing, and testing for digital microfluidic biochips. Optimization goal includes the minimization of time-to-response, chip area, and test complexity. The emphasis here is on practical issues such as defects, fabrication cost, physical constraints, and application-driven design. To obtain robust, easy-to-route chip designs, a unified synthesis method has been developed to incorporate droplet routing and defect tolerance in architectural synthesis and physical design. It allows routing-aware architectural-level design choices and defect-tolerant physical design decisions to be made simultaneously. v In order to facilitate the manufacture of low-cost and disposable biochips, design methods that rely on a small number of control pins have also been developed. Three techniques have been introduced for the automated design of such pin-constraint biochips. First, a droplet-trace-based array partitioning method has been combined with an efficient pin assignment technique, referred to as the "Connect-5 algorithm". The second pin-constrained design method is based on the use of "rows" and "columns" to access electrodes. An efficient droplet manipulation method has been developed for this cross-referencing technique. The method maps the droplet-movement problem to the clique-partitioning problem from graph theory, and it allows simultaneous movement of a large number of droplets on a microfluidic array. The third pin-constrained design technique is referred to as broadcast-addressing. This method provides high throughput for bioassays and it reduces the number of control pins by identifying and connecting control pins with "compatible" actuation sequences. Dependability is another important attribute for microfluidic biochips, especially for safety-critical applications such as point-of-care health assessment, air-quality monitoring, and food-safety testing. Therefore, these devices must be adequately tested after manufacture and during bioassay operations. This thesis presents a cost-effective testing method, referred to as "parallel scan-like test", and a rapid diagnosis method based on test outcomes. The diagnosis outcome can be used for dynamic reconfiguration, such that faults can be easily avoided, thereby enhancing chip yield and defect tolerance. The concept of functional test for digital biochip has also been introduced for the first time in this thesis. Functional test methods address fundamental biochip operations such as droplet dispensing, droplet transportation, mixing, splitting, and capacitive sensing. To facilitate the application of the above testing methods and to increase their effectiveness, the concept of design-for-testability (DFT) for microfluidic biochips has been introduced in this thesis. A DFT method has been proposed that incorporates a test plan into vi the fluidic operations of a target bioassay protocol. The above optimization tools have been used for the design of a digital microfluidic biochip for protein crystallization, a commonly used technique to understand the structure of proteins. An efficient solution-preparation algorithm has been developed to generate a solution-preparation plan that lists the intermediate mixing steps needed to generate target solutions with the required concentrations. A multi-well high-throughput digital microfluidic biochip prototype for protein crystallization has also been designed. In summary, this thesis research has led to a set of practical design tools for digital microfluidics. A protein crystallization chip has been designed to highlight the benefits of this automated design flow. It is anticipated that additional biochip applications will also benefit from these optimization methods.