Droplet Routing in Digital Microfluidic Biochip using Agglomerative Hierarchical Clustering

Abstract

Digital microfluidic biochip (DMFB) has established its potential in diferent applications like lab-on-chip device to perform pathological analysis and sample testing, air contamination detection, drug discovery and many others related to this. Droplet routing in DMFB is an essential operation. Optimization of diferent droplet routing aspects are fine tuned to enhance the performance of DMFB. Existing researches have used diferent traditional optimization techniques to optimize the performance of droplet routing. Use of machine learning mechanism is very less. Early-stage research indicates a wide scope for applying machine learning mechanism in DMFB domain. A clustering-based droplet routing mechanism based on the approach of agglomerative hierarchical clustering (AHC) has been used in this work which finds cluster of electrodes to form a path between source to target. Experimental studies on diferent test benches show a potential result for the approach in compare to existing research reports.

Keywords

• eol>agglomerative hierarchical clustering
• digital microfluidic biochip
• droplet routing
• fluidic constraints
• optimization

1. Introduction

DMFB is an upgradation over continuous fluid flow-based biochip. Digital microfluidic biochip has introduced microfluidic operations along two-dimensional micro-array of electrodes. It can operate on miniaturized samples. Sample size or volume in DMFB lies in the range of nanoliter or picoliter. Since the chips can operate with such a small volume of samples, it is also known as lab-on-chip device. Electro wetting of di-electric (EWOD) mechanism is used here to control the movement of droplets across microfluidic biochip. Droplets can move along horizontal or vertical direction across two-dimensional micro-array but no diagonal movements are allowed there [ 1 ]. Droplets can be controlled by EWOD in such a manner that it can travel from a specific electrode location to another electrode location, where the former electrode is termed as source and the latter is termed as target. Two diferent droplets can start routing from two diferent source locations and they can be routed towards a same target electrode where they can mix to perform a bio-chemical reaction. Diferent samples are thus mixed with specific reagents to perform chemical reactions and end results can be tested for a purpose. Thus, the biochip helps to simulate diferent bioassay protocols on the chips. Simulation of bioassay protocols helps bio-chemists to use DMFB extensively top perform diferent trials during their bio-chemical experimentations [ 2 ].

Applications of DMFB includes pathological experimentations, air contamination detection, smoke detection, drug discovery and many more. Figure 1 represents a schematic view of DMFB [ 3 ].

Schematic view shows that the arrangement is like a parallel glass plate, where two-dimensional micro-array is fabricated on bottom glass plate, and top glass plate is connected with ground. There is a hydrophobic filler medium in-between. Every unit cell of microarray is a separate electrode. A unit cell needs to be addressed distinctly to get electrical actuation. EWOD mechanism suggests that when a droplet moves from one cell to another then destination cell is charged with high voltage and electrode underneath of droplet is charged with a ground voltage. This facilitates the droplet to move from low charged electrode to active electrode. Reference to figure 2, a droplet is intending to move from source location 1 to 2. Droplet can move once cell at a time using EWOD. Cell 1 is kept at ground voltage and cell 2 is charged with high voltage, as a result the droplet shifts from 1 to 2 [ 4 ].

Droplet movement in DMFB is guided by some fluidic constraints. These fluidic constraints suggest that no two diferent droplets should be allowed to come at adjacent cells at any particular time or even any two droplets shouldn’t cross adjacent locations at two consecutive time instants. Always a one cell gap is maintained around any droplet which called critical region (figure 3).

Droplet routing performance across DMFB needs diferent types of performance optimization. The aspects of this optimization involve [ 1 ];

1. Minimization of total electrode usage with respect to any bioassay 2. Minimization of total turnaround time and average turnaround time Diferent optimization algorithms are reported in the literature to address the above issues. However,

use of machine learning based methods are being reported recently and the machine learning domain is mostly unexplored in this aspect.

Current work proposes a clustering approach based on agglomerative hierarchical clustering (AHC). It attempts to form cluster of electrodes which can form a routing path for any given droplet between a source – target pair. Bioassays designed by bio-chemists suggest a protocol where a droplet is represented in terms of source-target pair. AHC approach selects most potential electrodes into a single cluster for a given source-target pair and hierarchical clustering helps to track a sequence. A droplet can follow its route according to the sequence identified in the cluster of electrodes to travel from source to target. A bioassay protocol combines multiple define droplets with diferent combination of source-target pairs. All these droplets are routed together. AHC mechanism considers parallel movement following the fluidic constraints stated above and choose suitable electrodes in individual clusters for every droplet. Droplets here are identified with a separate yet parallel and non-conflicting set of clusters of electrodes so that all of them can travel in parallel without interfering each other.

Proposed AHC method has been tested on diferent standard test benches and experimental findings have been compared with a recently published article. Experimental results are promising.

Rest of the article contains a brief literature survey in the following section 2 followed by a discussion on proposed method in section 3. Experimental analysis is discussed in section 4 which is followed by a conclusion in section 5.

2. Literature Survey

Article [ 1 ] discussed droplet routing scheme in DMFB bypassing contamination zones. A preferred routing region has been identified by using shortest path routing scheme. Then the authors proposed a minimal cost circulation (MCC) algorithm for eficient wash-droplet routing. Droplet routing issue is divided into several smaller problems so that the contaminations between the smaller problems are also identified using a look-ahead prediction approach. Then, the MCC method helps to decrease the execution time and requirement of cells.

Article [ 2 ] provides an approach that addresses the issues of cross-contamination on biochips with pin constraints. Before placement, this algorithm reduces cross-contamination. Authors provide a wash droplet scheduling and routing method to deal with just one more control pin and no additional assay completion time is needed. It also reduces chip volume and the number of electrodes those are used during the routing time. Additionally, it minimized the number of electrodes needed for routing.

Another work demonstrated in [ 3 ] manages a cross-contamination-avoidance droplet-routing and optimization technique for DMFB. This approach combines washing procedures into useful dropletrouting phases and targets discontinuous droplet paths. Work has reduced the time taken by droplets to be transported by coordinating the routing of wash droplets with functional droplet-routing stages and carefully modifying the arrival orders of both types of droplets at cross-contamination sites. Additionally, an optimization technique to reduce the quantity of wash operations required in between consecutive routing phases has been proposed. This approach has been evaluated using two real-world bioassay applications.

The article [ 5 ] has proposed first integrated large functional wash droplet routing. Large wash droplet has more capacity to clean. Functional routing and wash droplet routing are performed concurrently to solve cross-contamination problem. It finds the washing channels through horizontal searching.

Authors in [ 6 ] propose a new algorithm for droplet routing that controls the situation of live-lock and deadlock. They also provide techniques to enable non-reconfigurable modules, including integrated heaters and detectors, and to enhance the efectiveness of wash droplet routing during routing-based synthesis.

Article [ 4 ] introduced a droplet routing technique depending on adaptive weighted PSO model to ifnd faulty electrodes and removes residue at the same time. It can efectively bypass inactive electrodes and manage significant flow through electrodes that are contaminated. As a result, it facilitates the identification of problematic areas and the removal of bio-residues from utilized electrodes. The proposed approach is based on an adaptive weighted particle swarm optimization method, in which complementary coeficients are used to build the guiding equation. Two complimentary coeficients are linked to the positive and negative inertia of weights, respectively. Additionally, it has the ability to identify fault locations.

Article [ 7 ] has focused on an eficient, innovative, sophisticated dual faults detection method. This algorithm detects the number of faults which are frequently occurring in DMFB along with particular types of their categories. It introduces two methods, Internal Electrode Traversal (IET) involves the selection of internal cells for testing within a microfluidic biochip. The test droplets are tested by moving them in certain movement patterns from the source to the sink. Boundary electrodes are tested in the method of Boundary Electrode Traversal (BET). In this method, every node and edge along the border line are tested that is left uncovered during internal cell traversal. The test droplet travels through the boundary electrodes anticlockwise. If a defect is found, this method can identify the faulty location by testing a droplet using backtracking method, otherwise it computes the traversal time for faultless biochip.

Authors of [ 8 ] proposed a unified contamination-aware routing strategy to decrease the execution time of a bioassay and successfully remove contaminations. They are given a top-down strategy to create potential routing paths, and after that, they build a shortest-path model to choose the best routing paths across all sub-problems. Lastly, for all sub-problems, contaminant removal using washing droplets with washing capability was taken into consideration.

Article [ 9 ] has introduced a serial-parallel conversion test technique to optimize the routing path in parallel by many droplets of DMFB. A combined method using both priority strategy and genetic algorithms is developed to enhance the optimization of parallel test paths on the biochip. This approach aims to mitigate the randomness inherent in using a single intelligent algorithm for test path optimization. Next, an adaptive approach is introduced to dynamically adjust the number of test tasks, enhancing the efectiveness of distributing test tasks evenly and optimizing parallel testing on the digital microfluidic biochip.

Authors in [ 10 ] introduce new optimized routing techniques using the deep-reinforcement learning for DMFB. This approach is separated into two phases. All droplets are routed from source to target through a distributed Ape-X DQN algorithm. Deadlocks and route collisions are resolved in the subsequent phase of the algorithm. It uses temporary stalling and detouring of certain droplets. Proposed novel algorithm was curated by combining the DQN approach with the double Q-learning technique. The algorithm also acts in two phases which involves acting followed by learning. Initially it finds all-possible routes of source-target pairs through the actors of this method and then review the policy of using deep neural network. Finally, the knowledge is reposited in a replay bufer. Then, the learner derives the experiences and manipulate routing pathways.

Article [ 11 ] is based on managing both known and unknown errors using deep-reinforcement learning for DMFB. The primary goal of reinforcement learning is problem solving through the use of intelligent agents that aims to maximize the overall rewards under a specific environment. It suggests and evaluates an algorithm capable of handling various types of errors, which might increase the dependability and efectiveness of biochips. This technique helped to find the most likely and eficient routing path while also helping to unknown faults that occurred throughout the routing process.

A droplet routing scheme which uses an indirect encoding mechanism through an evolutionary algorithm and an enhanced Dijkstra-based decoding technique to reduce the arrival time of the droplets has been proposed in [ 12 ]. This proposed algorithm considers indirect representation, which is a easy procedure for population initialization. In the decoding technique, the Dijkstra algorithm is extended with a problem-specific cost function to identify a path for each droplet within limited time requirement. Various techniques are introduced to avoid unwanted mixing in both 2D and 3D DMFBs for considering lfuidic constraints.

Recent studies of some diferent approaches addressing factors associated with droplet routing in digital microfluidic biochip shows that the scopes and prospect related to droplet routing in DMFB is wide yet the application of machine learning methods and approaches are minimal. Hence, it is quite important to focus on some techniques that can alleviate the process of introducing machine learning based solutions in the domains of DMFB droplet routing.

3. Agglomerative Hierarchical Clustering (AHC) for Droplet Routing

AHC is a familiar clustering approach for problems where solutions can be represented in a tree like structure. Microarray of electrodes in DMFB is a two-dimensional patterned array of unit electrodes. Electrodes are connected with each other in sequence, either row-wise or column-wise. Droplet routing path is a combination and sequential arrangement of electrodes. Hence the path and its options can be represented in a level wise tree like organization. Fluidic constraints of droplet routing have been simply considered here to represent parallel routing of droplet and formation of hierarchical cluster following the principle of agglomerative clustering. Let us consider the figure 4 as a sample workflow example.

Figure 4 (a) represents two nets. Net 1 is represented by S1 – T1 pair and net 2 is represented by S2 – T2 pair. Figure 4 (a) is [6 × 6] two-dimensional micro-array of electrodes taken as an example and unit cells are marked with yellow are blocked electrodes which can’t be used during routing. Net 1 is having source location (S1) at electrode 1 and target location (T1) at electrode 27. Similarly net 2 is having source (S2) at 4 and target (T2) at 20. Agglomerative hierarchical clusters for both the nets are formed simultaneously and parallelly as shown in figure 4 (b) while maintaining all fluidic constraints and avoiding blocked electrodes marked in yellow.

This proposed method is demonstrated with a flowchart in figure 5 and corresponding algorithm is formally represented after the figure.

Algorithm 1: Agglomerative Hierarchical Clustering (AHC) for droplet routing in digital microfluidic biochip

Input: Source location denotes S, target location denotes T and blockage location denotes in B in state space (DMFB dimensions m x n).

Let number of nets (N) = x (considering 2-pin nets) in state space.

Step 1: Initialize the position of source (), target () and blockage () location of each net. formation will only be confined within bounded-region of - .

Step 4: for (each net i = 1 to x) do (Finding route for each Ni) if <, then Find next possible location from current location for all .

(If current location is right on the state space, then select immediate left and down location from current location and if current location is left position on state space, then select immediate right and down location from current location)

if (+R != ) and (+D!= ) (where +R and +D denotes right and down location of respectively.) then check fluidic constraints with all pairs of - .

Calculate latest Arrival turnaround time () Repeat Step 4. end if end if end for

Step 5: Exit

4. Experimental Results

Proposed method has been implemented using python 3.13.0 on a Ubuntu Linux OS, version 20.0. Test bench-suite 1 [ 13 ] was rigorously used to generate the test result and compare the same with the most recent result available in [ 10 ]. Table 1 presents the detailed records of experimentation. Details of test bench-suite is given in the left of the table which includes some details like test name, test bench details, total number of nets present, percentage of blockage present. Experimentation was mainly focused on three factors, 1. Latest arrival time (LAT): Maximum time required to complete the whole process as per specification of test bench 2. Average arrival time (AAT): Average of arrival times for all individual nets under a specific test bench 3. Total electrodes usage (TEU): Total number of unique electrodes used to complete the droplet routing process under each test bench.

Comparative analysis is given graphically figure 6 where the performance improved of the proposed method is evident.

5. Conclusion

Experimental finding of proposed AHC method for droplet routing in DMFB has shown potential to apply it further for other aspects associated with droplet routing. This concept can be further tuned to address fault aware droplet movement and optimize the electrode actuation pin so that minimum number of pins can be devised to control the electrode actuation during electro-wetting of di-electric. (a) Further extension of this work can address cross-contamination avoidance in-between two consecutive bio-assay operations on the same DMFB board.

Declaration on Generative AI

The author(s) have not employed any Generative AI tools.

References

[1] T. W. Huang , C. H. Lin , T. Y. Ho , A contamination aware droplet routing algorithm for the synthesis of digital microfluidic biochips , IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 29 ( 2010 ) 1682 - 1695 . doi: 10 .1109/TCAD. 2010 . 2062770 .

[2] C. C. Y. Lin , Y. W. Chang , Cross-contamination aware design methodology for pin-constrained digital microfluidic biochips , IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 30 ( 2011 ) 817 - 828 . doi: 10 .1109/TCAD. 2011 . 2108010 .

[3] Y. Zhao , K. Chakrabarty , Cross-contamination avoidance for droplet routing in digital microfluidic biochips , in: Proceedings of the 2009 Design , Automation Test in Europe Conference Exhibition, France, 2009 , pp. 1290 - 1295 . doi: 10 .1109/DATE. 2009 . 5090864 .

[4] S. Mukherjee , I. Pan, T. Samanta , A particle swarm optimization method for fault localization and residue removal in digital microfluidic biochips , Applied Soft Computing 85 ( 2019 ) 105839 . doi: 10 .1016/j.asoc. 2019 . 105839 .

[5] H. Yao , Q. Wang , Y. Shen , T.-Y. Ho, Y. Cai , Integrated functional and washing routing optimization for cross-contamination removal in digital microfluidic biochips , IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems 35 ( 2016 ) 1283 - 1296 . doi: 10 .1109/TCAD. 2015 . 2504397 .

[6] S. Windh , C. Phung , D. Grissom , P. Pop , P. Brisk , Performance improvements and congestion reduction for routing-based synthesis for digital microfluidic biochips , IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 36 ( 2017 ) 41 - 54 . doi: 10 .1109/TCAD. 2016 . 2557726 .

[7] A. Saha , M. Majumder , An eficient technique for double faults detection and their locations identification in digital microfluidic biochip , International Journal of Automation and Smart Technology 9 ( 2019 ) 65 - 75 .

[8] Z. Huang , X. Bai , T. Lan , X. Li , G. Lin , Unified contamination-aware routing method considering realistic washing capacity constraint in digital microfluidic biochips , IEEE Access 8 ( 2020 ) 192867 - 192879 . doi: 10 .1109/ACCESS. 2020 . 3032675 .

[9] X. Huang , C. Xu , L. Zhang , C. Hu , W. Mo , Parallel testing optimization method of digital microfluidic biochip , Measurement 194 ( 2022 ) 111018 . doi: 10 .1016/j.measurement. 2022 . 111018 .

[10] B. Saha , B. Das , M. Majumder , A deep-reinforcement learning approach for optimizing homogeneous droplet routing in digital microfluidic biochips , Nanotechnology and Precision Engineering 6 ( 2023 ) 023001 . 1 - 023001 .12. doi: 10 .1063/10.0017350.

[11] T. Kawakami , C. Shiro , H. Nishikawa , X. Kong , H. Tomiyama , S. Yamashita , A deep reinforcement learning approach to droplet routing for erroneous digital microfluidic biochips , Sensors 23 ( 2023 ) 8924 . doi: 10 .3390/s23218924.

[12] C. Jiang , R.-Q. Yang , B. Yuan , An evolutionary algorithm with indirect representation for droplet routing in digital microfluidic biochips , Engineering Applications of Artificial Intelligence 115 ( 2022 ) 105305 . doi: 10 .1016/j.engappai. 2022 . 105305 .

[13] F. Su , K. Chakrabarty , Benchmarks for digital microfluidic biochips and synthesis , Department of Electrical and Computer Engineering, Duke University, Durham, NC , 2006 .