Hardware Reference
In-Depth Information
a
b
c
...
R
1
R
2
1
2
1
2
4
3
4
3
...
R
3
R
4
Fig. 5.8
(
a
) The undirected graph that represents the relationship among the basic mixing clusters
in Fig.
5.4
;(
b
) the adjusted graph after removing the edge between nodes
1
and
4
;(
c
) the ordering
of reservoirs on the electrode ring that can avoid conflicts of droplet routing
Definition 2.
If going from R
n
i
to R
n
j
along the electrode path P
.R
n
i
;R
n
j
/
is in
clockwise direction, then R
n
j
is the “clockwise neighbor” of R
n
i
.Otherwise,
R
n
j
is the “anti-clockwise neighbor” of R
n
i
.
An example is as follows. The sequencing graph in Fig.
5.4
can be divided
into five basic mixing clusters:
cluster
.R
1
;R
4
/,
cluster
.R
2
;R
4
/,
cluster
.R
3
;R
4
/,
cluster
.R
1
;R
2
/,and
cluster
.R
1
;R
3
/. The relationship among these mixing
clusters can be denoted by an undirected graph. Each node in the graph represents
a reservoir; if two reservoirs are in the same cluster, then an edge is added
between the pair of nodes that correspond to the reservoirs. The undirected
graph corresponding to Fig.
5.4
is shown in Fig.
5.8
a. As on the electrode ring
of low-cost biochips, each droplet has only two possible routing directions. If
a reservoir belongs to more than two basic mixing clusters, droplets dispensed
from the reservoir cannot be used in the mixing operations of all these clusters
concurrently. Accordingly, in the undirected graph, part of the edges will be
removed such that each node has no more than two edges. We have the following
conjecture:
Conjecture 5.1.
Assume that G
C
is a graph that represents the relationship of
mixing clusters in a bioassay, and each node in G
C
has no more than two edges.
Then we can always place the reservoirs on the electrode ring such that every
reservoir pair that has an edge between them can be placed as neighbors.
For two reservoirs R
n
i
and R
n
j
, if there is an edge between them, then
we place R
n
i
as the neighbor of R
n
j
. As discussed above, each reservoir on
the electrode ring has two neighbors: clockwise neighbor and anti-clockwise
neighbor. If one of the neighbor positions (e.g., clockwise neighbor) of R
n
j
is
occupied by another reservoir, then we place R
n
i
to the unoccupied position.
Note that each edge has no more than two edges, hence it will never happen that
both of the neighbor positions of R
n
j
are occupied by other reservoirs.
3.
Scheduling of operations:
Once the reservoir allocation step is completed, the
scheduling of operations can be determined based on the sequencing graph.
As operations in each basic mixing cluster can be performed locally without
long distance transportation, operations in different clusters can be performed
