Micro electrode dot array (MEDA) have attracted attention in the biochemical and medical industries. MEDA biochips enable biochemical experiments such as DNA analysis by manipulating droplets on the chip. Since the manipulation of droplets on the chip is based on the electro wetting on dielectric (EWoD) efect, a certain percentage of droplets may remain on the chip. Contamination cells on the chip due to left droplet has been considered as unavailable in previous studies. However, as the number of contaminated cells increases, droplets may not be able to move to the desired position if the contaminated cells are avoided. In order to clean the contamination, it is necessary to manually wash the chips or to move the droplets on the chips for washing. In this paper, we propose a method for simultaneous routing of washing droplets and functional droplets when a blockage occurs due to residual droplet contamination and reduce the droplet routing time by an average of 55% compared to existing method.
In DMFBs, the time required for droplet movement often constituted a small part of the overall process due to the complexity of mixing processes. However, MEDA biochips require fewer steps for mixing than DMFBs. As a result, the time required for droplet movement using MEDA biochips becomes more dominant in the overall process compared to using DMFBs.
During droplet movement on the biochip, there is a possibility of contamination when droplets
partially remain in cells through which they have passed. These remain droplets have potential
afecting the properties of subsequently passing droplets. There are lot of works to avoid the
efect by remain droplets. One method has been proposed such as allowing only one type of
droplet to pass through each cell to prevent interference from remain droplets [
The contributions of this paper are as follows. 1. We achieve simultaneous routing method of target droplet and washing droplet on MEDA biochips. 2. We realize a routing method that solves problems caused by route contamination by using washing. 3. We solve routing problems with diferent droplet volume ratios.
The rest of this paper is organized as follows. Section 2 describes related work, and Section 3 formulates our droplet routing problem that routing with washing droplets simultaneously. Section 4 describes the experiments and a comparison of the results, and Section 5 describes the conclusions of this paper.
Since the 2000s, extensive research has been conducted on eficient droplet routing in digital
microfluidic biochips (DMFB) [
In contrast, MEDA biochips achieves diverse droplet operations by dividing electrodes into
microelectrode cells (MCs) [
There is also extensive research on droplet routing leveraging the functions of MEDA biochips
[
Electrodes degrade over time with increased use, raising the likelihood of failures.
Additionally, it is known that droplet movement time depends on droplet size [
If a certain number of unusable cells occur or if there are too many droplets relative to the
biochip’s size, making it impossible to avoid interference with residual droplets, the biochip
needs to be cleaned. In the former case, cleaning before routing solves the issue [
In this section, we formulate the problem of simultaneous routing of washing droplet and target droplet on MEDA biochips. We assume that MEDA biochips is composed of W × H cells, and the coordinates of each cell are defined as (, ) with the bottom-left corner of the biochip being (1, 1). The washing droplet is set to the minimum volume of 1 to distribute the load on the electrodes. We assume a problem where the target droplet’s route does not exist due to contamination from past moving droplets, as shown in Figure 1(a). These contamination cells form a continuous block from the left edge to the right edge of the biochip. The washing droplet (a) Contamination cells (b) Move example : washing droplet (c) Move example : target droplet (Figure 1(b)) and target droplet (Figure 1(c)) move to each goal cells from each start cell. The target droplet move from the bottom-left to the top-right of the biochip, while the washing droplet move from the bottom edge to the top edge. The start and goal cells of the washing droplet can be set to any cell on the edges. In this condition, we realize routing problem that no mixing routes of target droplet by past moving droplet’s contamination.
MEDA biochips can reshape droplet. Reshaping a droplet takes the time as same as one moving, but it provides the advantage of potentially reducing the number of cells the droplet needs to pass through, depending on the direction of movement. This paper determines the routes that minimizes the moving time of the target droplet while using the smallest washing droplet to reduce the electrode load.
We consider a problem where pre-existing contaminated cells can be washed, and volume-1 washing droplet and volume-2 target droplet are routed simultaneously. The start and goal cell for the washing droplet are given. Figure 2 shows a 6 × 6 biochip, the contaminated cells, the start and goal cells of each droplet, and the initial shapes of the droplets.
Both the washing droplet and the target droplet move from their start cells to their goal cells. Once the washing droplet reaches its goal cell, they are discharged into a reservoir and thus are no longer present on the biochip. Since there is a possibility of interference between the washing droplet and the target droplet, a certain distance must be maintained between them during movement. Contaminated cells, indicated by black cells in Figure 2, are washed once the (a) Move of washing droplet (b) Move of target droplet washing droplet pass through them and become usable from the next operation cycle.
The objective of this problem is to minimize the time it takes for both the target droplet and the washing droplet to reach their goal cells.
First, we calculate the routing time based on the existing method [
As shown in Figure 3(a), the washing droplet move and require 6 steps. Then, as shown in Figure 3(b), the target droplet move, requiring 9 steps. In the existing method, the total routing steps are the sum of two droplets requiring steps both washing droplet and target droplet, resulting in a total of 15 steps.
Next, we calculate the routing time based on the proposed method in this paper. The proposed method moves the washing droplet and target droplet simultaneously. Therefore, it is necessary to avoid interference between the washing droplet and the target droplet.
(a) Phase 1
(b) Phase 2 (c) Phase 3 (d) Phase 4
Meaning Range
Volume of target droplet given The number of washing droplets given The number of target droplets given Start cell of washing droplets given, 1 ≤ ≤ ℎ. Goal cell of washing droplets given, 1 ≤ ≤ ℎ. Start cell of target droplets given, 1 ≤ ≤ Goal cell of target droplets given, 1 ≤ ≤
Contamination cells given The reference point of washing droplet at step 1 ≤ .ℎ, ≤ , 1 ≤ .ℎ, ≤ The reference point of target droplet at step 1 ≤ , ≤ , 1 ≤ , ≤ The aspect ratio of target droplet at step 1 ≤ ( , , ℎ, ) ≤ The operation of washing droplet at step 0 ≤ .ℎ, ≤ 2 The operation of target droplet at step 0 ≤ , ≤ 4
The routing time of target droplet 0 ≤
In Figure 4(a), the washing droplet moves for 2 steps, but the target droplet does not move to avoid interference. In Figure 4(b), the washing droplet moves upwards for 2 steps, while the taarget droplet moves rightwards for 2 steps. At this point, the contamination cells that the washing droplet passes through are washed, allowing the target droplet to pass through.
Subsequently, in Figure 4(c), the washing droplet moves upwards for 2 steps, and similarly, the target droplet moves for 2 steps. Once the washing droplet reaches goal cell, it is discharged into a reservoir and disappears from the biochip. Finally, in Figure 4(d), the target droplet moves to the goal position in 5 steps.
From the above, we show the example that the washing droplet requires 6 steps and the target droplet requires 11 steps. In the proposed method, the total routing steps are determined by the longer routing steps between target droplet and the washing droplet, resulting in a total of 11 steps. This shows an improvement of 4 steps compared to the existing method.
We present the formulation of the routing problem with washing based on integer programming. Table 1 shows the character used in this formulation and their meanings.
We define the coordinates and shapes of the droplets are expressed using formulation. Let represent the droplet number, which depends on the number of droplets, and denote the operation step. (.ℎ, , .ℎ, ) is defined as the reference point of washing droplet at step . Similarly, (, , , ) is defined as the reference point of target droplet at step . The reference point is the coordinate at the bottom-left of the droplet. The shape of target droplet at step can be expressed as (, , ℎ, ), where (, , ℎ, ) represent the width and height of the droplet, respectively.
Washing droplet is always assumed to be of size 1 and exist only at the reference point to reduce the load on the electrodes. In this paper, droplets are assumed to always occupy a rectangular cells, so target droplet occupies the cells from (, , , ) to (, + , − 1, , + ℎ, − 1).
Formula (1) shows that the target droplet reshapes while maintaining a constant volume. For example, if the volume of the droplet is 2, it can be in one of the two states: (, × ℎ, ) = (1× 2) or (2 × 1). ∀ , , , × ℎ, = (1)
There is no change in the formulation of the washing droplet and target droplet from Formula (2) to Formula (5). .ℎ, refers to both .ℎ, and , . (.ℎ, ,.ℎ, ) refer to both (.ℎ, ,.ℎ, ) and (, ,, ).
Formula (2) represents the initial positions of the washing droplet and target droplet. The coordinates at step 0 for both washing and target droplets are given.
∀ , (.ℎ,0 = .ℎ.)
∧ (.ℎ,0 = .ℎ.) (2)
Next, we formulate the operations of the droplets. We assume that droplets can move in various directions and reshape during routing. Droplets can move in horizontal (x-axis), vertical (y-axis), and diagonal directions. When .ℎ, = 0, the washing droplet and the target droplet do not move at step . When .ℎ, = 1, the washing droplet and the target droplet move one cell horizontally at step . When .ℎ, = 2, the washing droplet and the target droplet move one cell vertically at step . , = 3, the target droplet reshapes at step . When , = 4, the target droplet moves one cell diagonally at step .
Formula (3) represents the condition where both the washing droplet and the target droplet do not move when .ℎ, = 0. This is mainly used to avoid interference between droplets. ∀ , , (.ℎ, = 0) →
(.ℎ, = .ℎ, − 1) ∧ (.ℎ, = .ℎ, − 1)
Formula (4) represents the condition where both the washing droplet and the target droplet move one cell horizontally when .ℎ = 1. This is mainly used to avoid interference between droplets. The reference points of the washing droplet and the target droplet move horizontally, but the vertical coordinates remain unchanged.
∀ , , (.ℎ, = 1) → (.ℎ, − 1 − 1 ≤ .ℎ, ≤ .ℎ, − 1 + 1) ∧ (.ℎ, = .ℎ, − 1) Similar to Formula (4), Formula (5) shows the vertical motion of .ℎ, = 2: ∀ , , (.ℎ, = 2) → (.ℎ, = .ℎ, − 1) ∧ (.ℎ, − 1 − 1 ≤ .ℎ, ≤ .ℎ, − 1 + 1) (5)
Formula (6) represents the deformation of a droplet when = 3. When the target droplet is reshaped, the shape at step is diferent from the one at step − 1:
Formula (7) also shows the case of , . Droplets have several ways of reshaping the droplet. The reference point changes depending on the way of reshaping. The expression that allows such possible shapes is given by:
∀ , ,
Formula (9) shows whether the droplet is finished routing. Formula ( 9) determines if at least one cell of the droplet reaches the destination cell.
⎪⎪⎧⎪ (.ℎ, ≥ .) ⎪⎪⎫ ∑︁ ⎨⎪ ∧ (.ℎ, + , − 1 ≤ .) ⎪⎪⎬ ∀ , = 1 ⎪⎪⎪⎪⎩ ∧∧((..ℎℎ,,+≥ ℎ,.−1 )≤ .) ⎪⎪⎪⎪⎭ (9)
Formula (10) represents the constraints related to unusable cells. Target droplet cannot enter contamination cells. However, target droplet can enter contamination cells after the washing droplet have passed through.
∀ , , , ⎪⎪⎪⎧ (.ℎ, ≤ .) ⎪⎪⎫ ⎪⎨ ∧ (.ℎ, + , − 1 ≥ .)⎪⎬⎪
.) ¬ ⎪⎪⎪ ∧ (.ℎ, ≤ ⎪⎪ ⎪⎩ ∧ (.ℎ, + ℎ, − 1 ≥ .) ⎭⎪⎪
⎪⎧⎪⎪⎪⎨ (∧ <(.)∧ℎ(,,≤ ≤, .+ℎ,,−) 1)⎪⎬⎪⎪⎪⎫ ∨ ⎪⎪⎪⎪⎩ ∧∧ ((.,≤ℎ,.≤ℎ,,)+ , − 1) ⎪⎪⎭⎪⎪ (10)
Formula (11) defines , which represents the number of operations for target droplet . In this paper, the operation steps of the droplets are defined as the time required for movement, so the total number of operations corresponds to the movement time.
The objective function is to minimize the movement time of the target droplet. ∀ , = { ( , ̸= 0 ) × } : () (7) (8) (11) (12)
We conduct simulations to demonstrate the efectiveness of our proposed method. We compare
the proposed method with the existing method for the problem of simultaneous routing of
washing droplet and target droplet. The size of the biochip, the positions of contamination cells,
the volume of the two droplets, and their respective start and goal cells are given. The objective
function of this experiment is to minimize the routing time of the droplets from the start cell to
the goal cell. We compare the routing time with the following two techniques:
• Existing Method: A method where the movement of the target droplet begins after the
washing droplet have completed the washing process [
The following conditions are given for the experiment. The size of the washing droplet is set to 1, with only one present on biochips. Similarly, the size of the target droplet is set to 2, with only one present on biochips. Simulations are conducted in two scenarios: one where there is a single sequence of contamination cells on biochips and another where there are two sequences of contamination cells. The size of MEDA biochips is assumed to be = 10, = 15. The start and goal cells of the washing droplet are randomly assigned. In the case of a single sequence of contamination cells, 20 patterns are conducted by changing the start and goal cells of the washing droplets. Similarly, 20 patterns are conducted for the case of two sequences of contamination cells.
The experiments are executed on a Ryzen Threadripper 3970X (3.7 GHz, 32 cores, 64 threads) with 256 GB of memory. We use IBM ILOG CPLEX Optimization Studio 20.1.0 to solve both the existing method and the proposed method. The computation time is limited to a maximum of 10 hours of CPU time. If the optimal solution is not obtained within the computation time, the best feasible solution found within the time limit is used for comparison.
indicates the normalized routing time of the proposed method, using the routing time of the existing method as a baseline.
The proposed method successfully reduces routing time in all patterns compared to the
existing method. As shown in Figure 5, the proposed method successfully reduces routing
time by simultaneously moving the washing droplet and the target droplet. On average, the
proposed method achieves a 55% reduction in routing time. In the results for one sequence of
contamination cells shown in Figure 5:(a), an average 50% reduction in routing time is achieved.
For two sequences of contamination cells shown in Figure 5:(b), an average 60% reduction
in routing time is achieved. This indicates that the increase in the number of contaminated
cells requiring washing cause a more widespread distribution of contamination cells. Multiple
points requiring mandatory washing emerged with the increase in the number of sequences
of contamination cells, extending the washing droplet routing time. However, the proposed
method alleviated this problem to some extent by moving the target droplet simultaneously
with the washing droplet. If there were lot unusable cells which caused by broken, proposed
method would not alleviate. Therefore, setting unusable cells that the washing droplet cannot
handle due to electrode failures, or setting a limit on the number of cells that can be washed
per unit volume of the washing droplet, can create more realistic problems. Additionally, it is
known that droplet movement speed varies depending on their shape [
We proposed a simultaneous routing method for washing droplet and target droplet on MEDA biochips to minimize the routing time of target droplet, including the washing process. The proposed method successfully reduced the droplet routing time by an average of 55% compared to existing method. The future challenges include extending the problem to consider droplet movement speed and washing limits, and experimenting on actual biochips.
This work is partly supported by KAKENHI 20H04160 and 20H00590.