Biomedical Engineering Reference
In-Depth Information
After an efficient partitioning of electrodes is derived, we address all
the electrodes in a group using a single control pin. A common activation
sequence compatible with all the individual sequences in each group is
calculated and used as the input sequence for the control pin. In the pre-
ceding example, electrodes E
1
and E
4
are connected and share the common
activation sequence of {01000010}. Since we broadcast a common activa-
tion sequence to several electrodes, we refer to this addressing method as
“broadcast addressing.”
The complete steps in broadcast addressing are as follows:
1. Obtain droplet-routing information from the biochip synthesis
results and calculate the control-signal sequence for each control
pin. The control-signal sequence consists of the values 1 (activated),
0 (deactivated), and x (don't-care).
2. Draw an undirected graph representing the relationship between
control-signal sequences. For every pair of electrode-activation
sequence, if one sequence can be derived from the other by simply
changing x's to 1's/0's, then draw an edge between the nodes repre-
senting them.
3. Apply clique partitioning to minimize the number of independent
control signals.
4. Group and connect the control lines that are in the same clique.
The general clique-partitioning problem is known to be NP-hard [57].
Therefore, we use a heuristic based on the union-find algorithm [73], which
partitions the graph by iteratively searching for a maximal clique, defined as
a clique not contained in any larger clique, and then deleting the maximal
clique from the graph. The algorithm takes O(
N
3
) computation time, where
N
is the number of electrodes on the chip.
By using this broadcast-addressing method, the input bandwidth for the
microfluidic biochip can be significantly reduced. For example, in Figure 3.33,
instead of using eight independent control pins to address the electrode
loop, broadcast addressing needs only four control pins. A more significant
reduction is expected in large arrays with more don't-care terms in activa-
tion sequences.
Another advantage of the broadcast-addressing method is that it provides
maximum freedom of droplet movement. It does not change the schedule
of operations or the droplet-routing pathways for the target bioassay; there-
fore, bioassays can be executed as fast as on a direct-addressing-based chip.
Compared to the array-partitioning-based method presented in Section 3.1,
broadcast addressing does not need to limit the number of concurrent droplet
movements to get fewer partitions. The proposed method also reduces assay
operation time compared to cross-referencing; the latter typically requires
several substeps for a set of droplet manipulations that can be carried out
