Optimal Testing of Digital Microfluidic Biochips

Optimal Testing of Digital Microfluidic Biochips

0.00 Avg rating0 Votes
Article ID: iaor201111051
Volume: 23
Issue: 4
Start Page Number: 518
End Page Number: 529
Publication Date: Sep 2011
Journal: INFORMS Journal on Computing
Authors: , , ,
Keywords: testing
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.