Optimal Testing of Digital Microfluidic Biochips

Digital microfluidic biochips (DMFBs) are rectangular arrays of electrodes, or cells, that enable precise manipulation of nanoliter-sized droplets of biological fluids and chemical reagents. Because of the safety-critical nature of their applications, biochips must be tested frequently, both off-line (e.g., postmanufacturing) and concurrent with assay execution. Under both scenarios, testing is accomplished by routing one or more test droplets across the chip and recording their arrival at the destination. In this paper, we formalize the DMFB-testing problem under the common objective of completion time minimization, including previously ignored constraints of droplet noninterference. Our contributions include a proof that the general version of the problem is NP-hard, tight lower bounds for both off-line and concurrent testing, optimal and approximation algorithms for off-line testing of commonly used rectangular shaped biochips, as well as a concurrent testing heuristic producing solutions within 23%–34% of the lower bound in experiments conducted on data sets simulating varying percentages of biochip cells occupied by concurrently running assays.