||Synthesis of Biochemical Applications with Operation Variability on Digital Microfluidic Biochips
||Sjøgreen, Christian Ejdal
||Pop, Paul (Embedded Systems Engineering, Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
||Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
||Digital microfluidic biochips are small devices promising to replace much of
the equipment found in biochemical laboratories today. A digital biochip is
composed of a two-dimensional array of electrodes. A small drop of liquid (a
droplet) can occupy one electrode. The droplets can be manipulated on the
biochip using a technique called electrowetting-on-dielectric.
Any biochemical application (or bioassay), can be captured as a series of
basic microfluidic operations performed using the droplets on a digital biochip.
The bioassays are modeled using a directed graph, where each node is an operation. Apart from the operations themselves, the graph indicates the order in
which they must be executed for the bioassay to be successful. Such a graph is
called an application graph.
In order for a digital microuidic biochip to execute the application graph
of a bioassay the graph must be synthesized into a schedule for the biochip
microcontroller. The schedule tells the biochip when and where to move the
droplets to perform the bioassay.
Errors can appear during the execution of an application, such as a stuck
droplet or an imperfect split operation resulting in imbalanced volumes. A
simple scheme has been proposed in literature, where several recovery schedules
are produced at design time and are stored in the microcontroller. However, in
this thesis we consider that the recovery schedules are produced during runtime,
based on the observed errors.
Researchers have proposed methods for schedule synthesis based on meta-
heuristics, but they are very time-consuming. Hence, the existing methods
cannot be used to synthesize a recovery schedule for the biochemical application
at run time, as a reaction to errors. The objective of the thesis is to develop a
fast and accurate heuristic for recovery schedule synthesis that can be applied
online for fault-tolerance.
We present the types of errors that can appear. Different approaches for
the biochip controller to react to errors are discussed. The existing synthesis
method is presented, and a fast but accurate heuristic algorithm for recovery
schedule synthesis handling is proposed and implemented.
||Technical University of Denmark (DTU) : Kgs. Lyngby, Denmark
Creation date: 2011-03-25
Update date: 2011-03-25