Transcript ILP-Based Synthesis for Sample Preparation Applications on Digital

ILP-Based Synthesis for Sample
Preparation Applications on Digital
Microfluidic Biochips
ABHIMANYU YADAV, TRUNG ANH DINH,
DAIKI KITAGAWA AND SHIGERU YAMASHITA
Digital Microfluidic Biochips
A typical digital microfluidic biochip consists of a two
dimensional control electrode array, peripheral devices such
as dispensing ports, optical detectors, integrated logic and
surrounding control pins as illustrated in the figure. Due to
electro wetting phenomenon, assigning time-varying
voltage values to activate/deactivate the electrodes in an
appropriate strategy can move droplets. To precisely control
the movements of the droplets, electrodes are connected
to control pins to realize input signals as shown in the
figure.
Solved Example. Sort of …
A very simple bio-assay carried out on a bio-chip. Involves
few different chemicals in blue to start with. These will be
placed in the Dispensing Ports . Notice that the given
graph is simple DAG. What will stored in the integrated
logic is the topological ordering of this graph, so that the
chip knows what to do next.
The nodes in orange are mixing operations that need
to performed on the input droplets. It is interesting
how droplets are mixed. The following video will
demonstrate the dispensing ports in action and the
droplets being mixed.
Biochip in Action
Some observations
Observation1 :
A mixing operation requires a certain number of cells to execute.
Observation2 :
It is not economically feasible to have a chip with infinite number of cells.
Conclusion :
As a result, there will be an upper bound on the number of mixing operations that can execute
simultaneously. Also, we would want to finish the entire application in the least amount of time
possible.
The graph
Scheduling Problem with constraints
This is what the entire problem narrows down to. Various researchers have devised methods to
compute the optimal scheduling. Some have used SAT solvers while others have used ILP (
Integer Linear Programming ) to solve this problem.
The entire research is focussed on devising a method to find the scheduling in the quickest
possible time.
This Paper
It proposes one such technique. This technique is based on ILP. The entire ILP formulation is
indeed quite simple and easy to understand. One Example here to show how to proceed.
Label each mixing operation with a label i N. Let Xit be a
binary variable which takes the value 1 if mixing
operation i is running at time t. This constraint be
formulated using ILP as follows:
t 𝑛𝑖=0 Xit <= 3