Browsing by Subject "Design automation"

Digital microfluidic biochips (DMFBs) are revolutionizing many biochemical analysis procedures, e.g., high-throughput DNA sequencing and point-of-care clinical diagnosis. However, today's DMFBs suffer from several limitations: (1) constraints on droplet size and the inability to vary droplet volume in a fine-grained manner; (2) the lack of integrated sensors for real-time detection; (3) the need for special fabrication processes and the associated reliability/yield concerns.

To overcome the above limitations, DMFBs based on a micro-electrode-dot-array (MEDA) architecture have recently been proposed. Unlike conventional digital microfluidics, where electrodes of equal size are arranged in a regular pattern, the MEDA architecture is based on the concept of a sea-of-micro-electrodes. The MEDA architecture allows microelectrodes to be dynamically grouped to form a micro-component that can perform different microfluidic operations on the chip.

Design-automation tools can reduce the difficulty of MEDA biochip design and help to ensure that the manufactured biochips are versatile and reliable. In order to fully exploit MEDA-specific advantages (e.g., real-time droplet sensing), new design, optimization, and test problems are tackled in this dissertation.

The dissertation first presents a droplet-size aware synthesis approach that can configure the target bioassay on a MEDA biochip. The proposed synthesis method targets reservoir placement, operation scheduling, module placement, and routing of droplets of various sizes. An analytical model for droplet velocity is proposed and experimentally validated using a fabricated MEDA chip.

Next, this dissertation presents an efficient error-recovery strategy to ensure the correctness of assays executed on MEDA biochips. By exploiting MEDA-specific advances in droplet sensing, the dissertation presents a novel probabilistic timed automata (PTA)-based error-recovery technique to dynamically reconfigure the biochip using real-time data provided by on-chip sensors. An on-line synthesis technique and a control flow are also proposed to connect local-recovery procedures with global error recovery for the complete bioassay.

A potentially important application of MEDA biochips lies in sample preparation via a series of dilution steps. Sample preparation in digital microfluidic biochips refers to the generation of droplets with target concentrations for on-chip biochemical applications. The dissertation presents the first droplet size-aware and error-correcting sample-preparation method for MEDA biochips. In contrast to previous methods, the proposed approach considers droplet sizes and incorporates various mixing models in sample preparation.

In order to ensure high confidence in the outcome of biochemical experiments, MEDA biochips must be adequately tested before they can be used for bioassay execution. The dissertation presents efficient structural and functional test techniques for MEDA biochips. The proposed structural test techniques can effectively detect defects and identify faulty microcells, and the proposed functional test techniques address fundamental fluidic operations on MEDA biochips.

In summary, the dissertation tackles important problems related to key stages of MEDA chip design and usage. The results emerging from this dissertation provide the first set of comprehensive design-automation solutions for MEDA biochips. It is anticipated that MEDA chip users will also benefit from these optimization methods.

Considerable effort has been devoted in recent years to the design and implementation of microfluidic platforms for biomolecular quantitative analysis. However, today's platforms suffer from two major limitations: (1) they were optimized for sample-limited analyses, thus they are inadequate for practical quantitative analysis and the processing of multiple samples through independent pathways; (2) the integrity of these platforms and their biochemical operations is still an open question, since no protection schemes were developed against adversarial contamination or result-manipulation risks.

Design optimization techniques for microfluidics have been studied in recent years, but they overlook the myriad complexities of biomolecular protocols and are yet to make an impact in microbiology research. The realization of microfluidic platforms for real-life quantitative analysis requires: (1) a new optimization flow that is based on the realistic modeling of biomolecular protocols, and (2) a microfluidic security flow that provides a high-level of confidence in the integrity of miniaturized quantitative analysis.

Motivated by the above needs, this dissertation is focused on optimized and trustworthy transfer of benchtop biomolecular analysis, particularly epigenetic studies, to programmable and cyber-physical microfluidic biochips. The dissertation first presents a set of optimization mechanisms that leverages cyber-physical integration to enable real-time execution of multi-sample biomolecular analysis. The proposed methods include a resource-allocation scheme that responds to decisions about the protocol flow, an interactive firmware that collects and analyzes sensor data, and a spatio-temporal reconfiguration technique that aims to enhance the reliability of the microfluidic system. An envisioned design for an Internet-of-Things (IoT)-based microfluidics-driven service is also presented to cope with the complexity of coordinated biomolecular research.

Next, this dissertation advances single-cell protocols by presenting optimized microfluidic methods for high-throughput cell differentiation. The proposed methods target pin-constrained design of reconfigurable microfluidic systems and real-time synthesis of a pool of heterogeneous cells through the complete flow of single-cell analysis. A performance model related to single-cell screening is also presented based on computational fluid-dynamics simulations.

With the increasing complexity of microbiology research, optimized protocol preparation and fault-tolerant execution have become critical requirements in today's biomolecular frameworks. This dissertation presents a design method for reagent preparation for parameter-space exploration. Trade-offs between reagent usage and protocol efficiency are investigated. Moreover, an integrated design for automated error recovery in cyber-physical biochips is demonstrated using a fabricated chip.

In order to ensure high confidence in the outcome of biomolecular experiments, appropriate security mechanisms must be applied to the microfluidic design flow. This dissertation provides an assessment of potential security threats that are unique to biomolecular analysis. Security countermeasures are also proposed at different stages of the biomolecular information flow to secure the execution of a quantitative-analysis framework. Related benchtop studies are also reported.

In summary, the dissertation tackles important problems related to key stages of the biomolecular workflow. The results emerging from this dissertation provide the first set of optimization and security methodologies for the realization of biomolecular protocols using microfluidic biochips.

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.

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.