Transcript University of Connecticut

Optimal Testing of Digital Microfluidic
Biochips: A Multiple Traveling Salesman
Problem
R. Garfinkel1, I.I. Măndoiu2, B. Paşaniuc2 and A. Zelikovsky3
1Operations
and Information Management, University of Connecticut
2Computer Science and Engineering, University of Connecticut
3Computer Science, Georgia State University
Outline

Introduction

Problem definition

ILP Formulation

Bounds and Heuristic

Experimental results

Conclusions
Introduction

Lab-on-chip


Advantages




Systems for performing biomedical analyses of very small
quantities of liquids
Fast reaction times
Low-cost, portable and disposable
Compactness massive parallelization high-throughput
2 Types:


Continuous-flow: enclosed, interconnecting, microndimension channels
Digital: discrete droplets of fluid across the surface of an
array of electrodes.
Digital Microfluidic Biochips
I/O
I/O
Cell
[Srinivasan et al. 04]
[Su&Chakrabarty 06]
• Electrodes typically arranged in rectangular grid
• Droplets moved by applying voltage to adjacent cell
• Can be used for analyses of DNA, proteins, metabolites…
Optimization Challenges



Module placement
 Assay operations (mixing, amplification, etc.) can be
mapped to overlapping areas of the chip if
performed at different times
Droplet routing
 When multiple droplets are routed simultaneously
must prevent accidental droplet merging or
interference
Testing
 High electrode failure rate, but can re-configure
around
 Performed both after manufacturing and concurrent
with chip operation
 Main objective is minimization of completion time
Concurrent Testing Problem

GIVEN:



Input/Output cells
Position of obstacles (cells in use by ongoing reactions)
FIND:
 Trajectories for test droplets such that
 Every non-blocked cell is visited by at least one
test droplet
 Droplet trajectories meet non-merging and noninterference constraints
 Completion time is minimized
Defect model: test droplet gets stuck at defective electrode
Concurrent Testing Problem



[Su et al. 04] ILP-based solution for single test droplet case & heuristic
for multiple input-output pairs with single test droplet/pair
Our problem formulation allows an unbounded number of droplets out of
each input cell

additional droplets can be used at no extra cost

completion time can be reduced substantially by splitting the work
among multiple droplets

however, too many droplets may interfere with each other
Test problem for multiple droplets is NP-hard by reduction from the
Hamiltonian path problem in grid graphs [Itai et. al. 82]

we seek approximation algorithms and heuristics with good practical
performance
Merging region


Set of cells to be kept empty when (i,j) is occupied by a
droplet
Merging region:
MR (i, j )  {( i  1, j  1), (i  1, j ), (i  1, j  1),
(i, j  1), (i, j ), (i, j  1),
(i  1, j  1), (i  1, j ), (i  1, j  1)}
Interference region


Set of cells to be kept empty when a droplet moves away
from (i,j)
Interference region:
IR (i, j )  MR (i, j )
ILP formulation

0/1 variable for each pair of neighbor cells:

x(ti , j )( k ,l )
x(ti , j )( k ,l )
is set to 1 iff a droplet that occupies cell (i,j) at time t-1
occupies cell (k,l) at time t
i:
j:
k:
l:
Time t-1:
N (i, j )  {( i  1, j ), (i  1, j ), (i, j  1), (i, j  1), (i, j )}
Time t:
ILP Formulation for Unconstrained Number of
Droplets

Each cell (i,j) visited at least once:

Droplet conservation:

No droplet merging:
 x
t
t
x
 (k ,l )(i, j ) 
( k ,l )N ( i , j )
t
x
 (k ,l )(i, j ) 
( k ,l )N ( i , j )

No droplet interference:

Minimize completion time:
t
( k ,l )( i , j )
( k ,l )N ( i , j )
t 1
x
 (i, j )( k ,l )  0
( k ,l )N ( i , j )

t
x
 (k ,l )( k ',l ')  1
( k ,l )N ( i , j ) ( k ',l ')N ( k ,l )
t
x
 (i, j )( k ,l ) 
( k ,l )N ( i , j )
1

( i ', j ')N ( i , j )
t
x
 ( k ',l ')(i ', j ')  1
( k ',l ')N ( i ', j ')
Minimize z
t  x(tk ,l )( i , j )  z  0, for every (i, j )  O
Special Case
• NxN Chip
• I/O cells in Opposite Corners
• No Obstacles
 Single droplet solution
needs N2 cycles
Stripe Algorithm with N/3 Droplets
Completion time:
N  3( N  2)  N  5 N  6
Lower Bound
Lemma 1: Completion time is at least
N2
 4k  4 when k droplets are used
k
Proof: In each cycle, each of the k droplets places 1 dollar in current cell
 3k(k-1)/2 dollars paid waiting to depart
 1 dollar in each cell
 k dollars in each diagonal
Topt
3k(k-1 )  2k 2  N 2  k(k  1 ) N 2


 4k  4
k
k
 3k(k-1)/2 dollars paid
waiting for last droplet
Approximation guarantee
Lemma 2: Completion time for any #droplets is at least 4N  4
N2
 4k  4 is achieved when
Proof: Minimum for
k
k  N /2
Theorem: Stripe algorithm with N/3 droplets has approximation
factor of
5N  6 5

4N  4 4
Stripe Algorithm with Obstacles of width ≤ Q



Divide array into vertical stripes of width Q+1
Use one droplet per stripe
All droplets visit cells in assigned stripes in parallel

In case of interference droplet on left stripe waits
for droplet in right stripe
Results for 120x120 Chip, 2x2 Obstacles
Obstacle
Area
0%
1%
5%
10%
15%
20%
25%
Average completion time (cycles)
k=1
14400
14256
13680
12960
12240
11520
10800
k=12
1412
1420
1473
1490
1501
1501
1501
k=20
944
953.4
982.8
1010.8
1025.8
1046.8
1071
k=30
710
715.2
725
734.8
730.8
738.4
736.6
k=40
593
598.8
596.2
592.6
588.2
580.8
570
k=40 vs. k=1
speed-up
24x
24x
23x
22x
21x
20x
19x
~20x decrease in completion time by using multiple droplets
Conclusions


Presented ILP formulation, approximation
algorithm and heuristic for microfluidic biochip
testing problem
Combinatorial optimization techniques can yield
significant improvements