Acronyms; Notations; Contents; 1 Introduction; 1.1 Motivation; 1.2 Overview; References; Part I Preliminaries ; 2 Design Methodology for Digital Microfluidic Biochips; 2.1 Compilation of Biochemical Applications; 2.2 Related Work; 2.2.1 Compilation Methods; 2.2.2 Droplet Routing Methods; 2.2.3 Methods for Pin-Constrained Biochips; 2.2.4 Methods for Cross-Contamination Avoidance; 2.2.5 Compilation Methods for Fault-Toleranceand Variability; 2.2.6 Methods for Biochip Architecture Synthesis; References; 3 Biochip Architecture Model; 3.1 Droplet Actuation

3.2 Typical Digital Microfluidic Biochip Architectures3.3 Fault Models; 3.3.1 Cross Contamination; 3.4 Operation Execution: Module vs. Routing; 3.5 Characterizing Routing-Based Operation Execution; 3.6 Dynamic Modules; 3.7 Non-Rectangular Modules; 3.8 Circular-Route Module; 3.9 Worst-Case Operation Execution Overhead in Case of Permanent Faults; 3.10 Estimation of Operation Execution in Case of Permanent Faults; References; 4 Biochemical Application Model; 4.1 Directed Acyclic Graph Model; 4.2 Case Studies; 4.2.1 Mixing Stage of the Polymerase Chain Reaction

4.2.2 In-Vitro Diagnostics on Physiological Fluids4.2.3 Colorimetric Protein Assay; 4.3 Transient Faults and Fault-Tolerance Models; 4.3.1 Fault-Tolerant Sequencing Graph; 4.3.2 Generalized Fault-Tolerant Application Model; 4.3.2.1 Error Propagation and Error Detection; 4.3.2.2 Redundancy Models; References; Part II Compilation; 5 The Compilation Problem; 5.1 Allocation; 5.2 Placement of Operations; 5.3 Binding and Scheduling; 5.3.1 Routing; 5.4 Building a Library of Circular-Route Modules; 5.4.1 Determining a Circular-Route Module; References; 6 Module-Based Compilation; 6.1 List Scheduling

6.2 Placement Algorithm6.2.1 Placement of Non-reconfigurable Devices; 6.3 Tabu Search; 6.4 Experimental Evaluation; References; 7 Module-Based Compilation with Reconfigurable Operation Execution; 7.1 Compilation with Dynamic Virtual Devices; 7.1.1 Motivational Example; 7.1.2 Algorithm for Compilation with Dynamic Devices; 7.1.3 Motivational Example; 7.1.4 Algorithm for Non-Rectangular Modules; 7.2 Experimental Evaluation; References; 8 Module-Based Compilation with Droplet-Aware Operation Execution; 8.1 Motivational Example; 8.2 Algorithm for Droplet-Aware Operation Execution

8.2.1 Time Complexity Analysis8.3 Experimental Evaluation; Reference; 9 Routing-Based Compilation; 9.1 Motivational Example; 9.2 Algorithm for Routing-Based Compilation; 9.3 Routing-Based Compilation with Contamination Avoidance; 9.3.1 Contamination Avoidance in Routing- vs. Module-Based Compilation; 9.3.2 Algorithm for Routing-Based Compilation with Contamination Avoidance; 9.4 Area-Constrained Routing for Contamination Avoidance; 9.5 Experimental Evaluation; References; Part III Compilation for Error Recovery and Uncertainty; 10 Fault-Tolerant Module-Based Compilation