Dissertations / Theses on the topic '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.

Flow-based microfluidic biochips constitute an emerging technology for the automation of biochemical procedures. Recent advances in fabrication techniques have enabled the development of these devices. Increasing integration levels provide biochips with tremendous potential; a large number of bioassays, i.e., protocols for biochemistry, can be processed independently, simultaneously, and automatically on a coin-sized microfluidic platform. However, the increases in integration level introduce new challenges in the design optimization and the testing of these devices, which impede their further adoption and deployment.

This thesis is focused on enhancing the automated design and use of flow-based microfluidic biochips and on developing a set of solutions to facilitate the full exploitation of design complexities that are possible with current fabrication techniques. Four key research challenges are addressed in the thesis; these include design automation, wash optimization, testing, and defect diagnosis.

Despite the increase in the number of on-chip valves, designers are still using full-custom methodologies involving many manual steps to implement these chips. Since these chips can easily have thousands of valves, manual design procedure can be time-consuming and error-prone, and it can result in inefficient designs. This thesis presents the first problem formulation for automated control-layer design in flow-based microfluidic biochips and describes a systematic approach for solving this problem. Our goal is to find an efficient routing solution for control-layer design with a minimum number of control pins.

The problem of contamination removal in flow-based microfluidic biochips must also be addressed. Applications in biochemistry require high precision to avoid erroneous assay outcomes, and they are vulnerable to contamination between two fluidic flows with different biochemistries. This thesis proposes the first approach for automated wash optimization for contamination removal in flow-based microfluidic biochips. The proposed approach ensures effective cleaning and targets the generation of wash pathways to clean all contaminated microchannels with minimum execution time under physical constraints.

Another practical problem addressed in this thesis is the lack of test techniques for screening defective biochips before they are used for biochemical analysis. This thesis presents an efficient approach for automated testing of flow-based microfluidic biochips. The test technique is based on a behavioral abstraction of physical defects in microchannels and valves. The flow paths and flow control in the microfluidic device are modeled as a logic circuit composed of Boolean gates, which allows test generation to be carried out using standard automatic test-pattern generation tools. Based on the analysis of untestable faults in the logic-circuit model, we present a design-for-testability technique that can achieve 100\% fault coverage.

Finally, this thesis presents a technique for the automated diagnosis of leakage and blockage defects. The proposed method targets the identification of defect types and their locations based on test outcomes. It reduces the number of possible defect sites significantly while identifying their exact locations.

In summary, this thesis has led to a set of optimization and testing methods for flow-based microfluidic biochips. The results of this research are expected to not only shorten the product development cycle, but also accelerate the adoption and further development of this emerging technology by facilitating the full exploitation of design complexities that are possible with current fabrication techniques.

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.

Microfluidic biochips have now come of age, with applications to biomolecular recognition for high-throughput DNA sequencing, immunoassays, and point-of-care clinical diagnostics. In particular, digital microfluidic biochips, which use electrowetting-on-dielectric to manipulate discrete droplets (or "packets of biochemical payload") of picoliter volumes under clock control, are especially promising. The potential applications of biochips include real-time analysis for biochemical reagents, clinical diagnostics, flash chemistry, and on-chip DNA sequencing. The ease of reconfigurability and software-based control in digital microfluidics has motivated research on various aspects of automated chip design and optimization.

This thesis research is focused on facilitating advances in on-chip bioassays, enhancing the automated use of digital microfluidic biochips, and developing an "intelligent" microfluidic system that has the capability of making on-line re-synthesis while a bioassay is being executed. This thesis includes the concept of a "cyberphysical microfluidic biochip" based on the digital microfluidics hardware platform and on-chip sensing technique. In such a biochip, the control software, on-chip sensing, and the microfluidic operations are tightly coupled. The status of the droplets is dynamically monitored by on-chip sensors. If an error is detected, the control software performs dynamic re-synthesis procedure and error recovery.

In order to minimize the size and cost of the system, a hardware-assisted error-recovery method, which relies on an error dictionary for rapid error recovery, is also presented. The error-recovery procedure is controlled by a finite-state-machine implemented on a field-programmable gate array (FPGA) instead of a software running on a separate computer. Each state of the FSM represents a possible error that may occur on the biochip; for each of these errors, the corresponding sequence of error-recovery signals is stored inside the memory of the FPGA before the bioassay is conducted. When an error occurs, the FSM transitions from one state to another, and the corresponding control signals are updated. Therefore, by using inexpensive FPGA, a portable cyberphysical system can be implemented.

In addition to errors in fluid-handling operations, bioassay outcomes can also be erroneous due the uncertainty in the completion time for fluidic operations. Due to the inherent randomness of biochemical reactions, the time required to complete each step of the bioassay is a random variable. To address this issue, a new "operation-interdependence-aware" synthesis algorithm is proposed in this thesis. The start and stop time of each operation are dynamically determined based on feedback from the on-chip sensors. Unlike previous synthesis algorithms that execute bioassays based on pre-determined start and end times of each operation, the proposed method facilitates "self-adaptive" bioassays on cyberphysical microfluidic biochips.

Another design problem addressed in this thesis is the development of a layout-design algorithm that can minimize the interference between devices on a biochip. A probabilistic model for the polymerase chain reaction (PCR) has been developed; based on the model, the control software can make on-line decisions regarding the number of thermal cycles that must be performed during PCR. Therefore, PCR can be controlled more precisely using cyberphysical integration.

To reduce the fabrication cost of biochips, yet maintain application flexibility, the concept of a "general-purpose pin-limited biochip" is proposed. Using a graph model for pin-assignment, we develop the theoretical basis and a heuristic algorithm to generate optimized pin-assignment configurations. The associated scheduling algorithm for on-chip biochemistry synthesis has also been developed. Based on the theoretical framework, a complete design flow for pin-limited cyberphysical microfluidic biochips is presented.

In summary, this thesis research has led to an algorithmic infrastructure and optimization tools for cyberphysical system design and technology demonstrations. The results of this thesis research are expected to enable the hardware/software co-design of a new class of digital microfluidic biochips with tight coupling between microfluidics, sensors, and control software.