Keywords

Introduction

Microfluidic biochips, also renowned as “lab-on-a-chip”, have become very important biomedical analytic instruments [1, 2] as the experiments in a laboratory can be efficiently performed within a chip. It manipulates nanolitre or microlitre volumes of biological samples and reagents which lead to consumption of a very low cost and relatively a very less time. Moreover, higher sensitivity of DMFBs and less involvement of human manipulation make it less erroneous than laboratory experiments. In spite of all the facilities of a biochip system, physical defects may arise during microfluidic operations. Some manufacturing defects may be realised during the assay operations and may lead to a crucial diagnosis process in vain. It is worthwhile to mention here that effective testing methodologies to test these devices after manufacture and during assay operations are very essential as biochips are generally used for vital biochemical and medical applications.

Generally, the testing procedure of the DMFBs is classified into structural testing and functional testing. Structural testing aims to detect the physical faults, while the functional testing focuses in identifying the faulty functional modules. One of the important testing techniques is droplet trace-based fault detection where a test stimulus droplet is moved through the testable cells, and depending on the presence of the droplet at its desired position at scheduled time, the defected cells are recognised. Such transportation of test droplets may be planned in terms of the Euler cycle or Euler path problems in an undirected or a directed graph, respectively. Sometimes, due to the unintended droplet, residual on the chip introduces particle contamination [1, 3] during assay operation that leads to physical defects afterwards. If one cell (Electrode) becomes faulty during the assay operation, even the entire assay operation may be fouled depending on the positional impact of the defective electrode(s). Thus, online and offline (e.g. Post-manufacturing) testing techniques are required to ensure system reliability and to augment the system performance [4, 5].

Now, in traditional square electrode array, we find a number of droplet trace-based testing mechanisms that are not beneficial for Triangular Electrode based Digital Microfluidic Biochip (TEDMB) [6] due to its routing constraints. In this paper, we have developed an Euler path based online testing algorithm for TEDMB. Moreover, a test planning procedure for online testing is introduced. Procedure for finding Euler circuit in a graph is presented here which runs in O(n + e), where a number of vertices and edges in the graph are, respectively, denoted by n and e. In the next section, we first discuss the types of faults that may occur in biochip and the basis of online testing as well as some already existing testing algorithms for traditional DMFB. Section “Test Planning Issues for Online Testing” formulates the problem as an Euler circuit finding problem in graph theory and we discuss our algorithm in detail. In Sect. “Conclusion”, a comparative study has been cited to explain the efficacy of our algorithm.

Classification of Faults in DMFB: Fault Modelling

Typically, the faults in DMFBs are of catastrophic and parametric [4, 5]. Catastrophic (i.e. hard) faults lead to a complete malfunction of the underlying system, whereas parametric (i.e. soft) faults may introduce a deviation in the system performance. Catastrophic faults have the highest priority for detection as they may cause complete breakdown of the system. Catastrophic faults can occur due to some physical imperfections such as (i) dielectric breakdown, (ii) short between a pair of adjacent electrodes, (iii) degradation of electrode performance, (iv) open circuit in the metal connections between the electrode and the control source and (v) defected configuration of parallel plates, to name a few. Physical defects that lead to parametric faults are deviation in geometrical parameters, particle contamination due to residual effect and deviation in viscous force acting between a droplet and filler medium.

To avoid the digression of the overall performance of the system, testing of the electrodes is a crucial issue before the chip is subjected to market. Chip-level testing is an iterative procedure where a chip is tested before or after the bioassay operation (offline testing) or a parallel testing operation may be carried on simultaneously with an assay in a time-overlapped manner. Parallel scan like testing [7] (using both single and multiple droplets) and path-based testing (Hamiltonian and Euler circuit [8, 9]) belong to offline testing.

Test Planning Issues for Online Testing

Problem Formulation

One of the most important catastrophic faults is stuck-at fault where a test stimuli droplet may be stuck at a faulty cell during the droplet movement through the electrode array from an original or customised source to a sink. The detection of all test stimuli droplets by a sensing circuit placed at a droplet sink indicates that the electrodes on the path are fault free. An efficient test plan must ensure two things: (i) no conflict of the testing operation with the normal biomedical assay and (ii) guarantee of the coverage of test droplets over all the microfluidic chip cells that are available for testing.

Here, it is worth mentioning that we consider catastrophic faults detection and we assume that every catastrophic fault in the microfluidic device affects only a single cell on the chip array. Nevertheless, some faults, like electrode shorts, affect more than one cell in the microfluidic array [1]. The fundamental idea behind the graph-theoretic testing optimization approach is to formulate the 2D chip as a directed graph followed by partitioning into sub-graphs such that each partition requires one test stimuli droplet to cover the associated portion of the chip and it can be tested independent of the other parts of the chip.

Testing by traversal generally finds a path such that the test droplet can be routed through the array visiting every cell exactly once though a path connecting all available electrodes does not exist in a chip as shown in Fig. 52.1a. Although this method ensures the fault detection concerning a single electrode, it fails to identify the faults associated with electrode-short and fluidic-open faults that influence two neighbouring electrodes, e.g. as shown in Fig. 52.1b; the test droplet path 6 → 7→8 → 9→10 → 5→4 → 3→2 → 1 is unable to detect an electrode-short present between electrodes 3 and 8. But the Hamiltonian path based tour visits each electrode just once. Thus, Hamiltonian path does not pledge to detect a fault-free microfluidic array. Therefore, a novel method for test planning is essential to solve this complication. Since this type of defect can happen in the DMFBs not only in the manufacturing (in the fabrication) process but also during the on-chip bioassay operations (e.g. owing to contamination of particles and relocation of electrode metal), the offline and online testing techniques are equally mandatory.

Fig. 52.1
figure 1

a A test droplet from the source can traverse only two electrodes, but cannot reach the sink. b Test stimuli droplet from the source can reach the sink leading two electrodes not reachable

Full size image

Here, we formulate the test planning problem into two well-known graph-theoretic problems, i.e. the ‘Euler circuit’ and ‘Euler path’ [8]. The basic idea behind this outlook is to construct an undirected graph representing the microfluidic chip array where each electrode acts as a vertex. Between any two vertices, i.e. two neighbouring electrodes, there exists an edge. Now, the problem of finding a test path is comparable to finding an Euler path of the graph. A flow-based test path for the test droplet can be acquired by using Euler’s theorem. Such a path enables to detect the shorts between any two neighbouring electrodes. As the Euler path/circuit based test technique visits all edges exactly once, it guarantees any electrode-short fault within the chip array.

Initially, we model the chip array by employing an undirected graph G = (V, E), where V is the set of microfluidic chip cells and E is the set of edge {u, v} between any two vertices u and v if there exists a connectivity between two cells represented by u and v, respectively. Euler theorem gives us the technique to traverse every edge in the undirected graph only once. For an undirected graph, Euler path exists if the graph is in connected pattern and the connected graph has exactly two odd-degree vertices. Again, an undirected graph has Euler circuit if the graph is connected and the degree of every vertex in the connected graph must be even. Now, in general the graphical representation of the 2D microfluidic chip array has more than two vertices with odd degree in nature. So, we have to retrace some of the edges such that all the edges must be visited at least once. In G, retracing signifies an additional edge between two adjacent vertices. Therefore, our objective is to minimise the number of retracing throughout the testing, i.e. the requisite number of additional edges to Eulerise the graph.

As each electrode in TEDMB has three direct neighbours, in the dual graph of the array, each vertex other than the peripheral one has degree three [6]. At the beginning of the algorithm, we identify all odd-degree vertices and transform them into even degree by adding minimum number of extra edges. For type 1 triangle, upward movement is restricted and for type 2 triangle downward movement is restricted [6]. So, there is an edge between two vertices, belonging to two adjacent rows, if and only if one vertex corresponds to a type 1 triangle and another vertex is associated with a type 2 triangle. To find an Euler circuit/path in a connected undirected graph, we use Fleury’s algorithm [4, 8].

In Fig. 52.2a, b, c, d, associated graph models for different triangular 2D arrays are shown, i.e. in the 2D m × n array four cases may occur, (i) m = odd, n = odd, (ii) m = even, n = even, (iii) m = odd, n = even and (iv) m = even, n = odd. We next model the 2D microfluidic array using undirected graphs and then modify these graphs so that the condition for possessing an Euler circuit is satisfied. Applying Fleury’s algorithm [4, 8], the complexity becomes O (n + e), where n = the number of vertices and e = the number of edges. So it requires linear time.

Fig. 52.2
figure 2

a–d corresponding graph model and Eulerisation of different-sized 2D triangular microfluidic array

Full size image

An Efficient Eulerisation Technique for Online Testing

To ensure unpredictable faulty status, online testing is performed throughout the free cells during normal bioassay operation (say, on-chip mixing in some regions). Here, the active parts of the chip along with its guard band may be considered as obstacles to the test stimuli droplets. The graph model of a triangular biochip with obstacle in it (i.e. with mixing and other operations running within the array) is not regular structure as an m × n array. As a result, Eulerising it by adding extra dummy edges for optimising test cost may not be straightforward as eulerising the graph model of m × n triangular microfluidic array, as the odd degree nodes geometrically, may be random in nature. For more than one test droplet, we partition the graph model of the microfluidic array into sub-graphs and then manipulate them individually such that there exists an Euler circuit in each sub-graph. Now, multiple test droplets are dispensed in the chip for performing the concurrent edge-tour based testing in various sections of the chip array. Thus, entire testing application time is equal to the maximum testing time among all these sub-graphs.

Let us illustrate the procedure with an example. A 10 × 10 microfluidic chip array is shown in Fig. 52.3a where two mixing operations are going on and one droplet is stored in a storage cell; hence, the active cells as well as their guard band are not accessible during this period of time. In order to test the remaining free cells, we first check the connectivity of the associated dual graph. If it is a disconnected graph, we need to deploy more than one test droplet to perform the testing properly.

Fig. 52.3
figure 3

a 10 × 10 chip array with obstacle, b Four sub-graphs G1, G2, G3, G4 constitute the graph representation of the 2D microfluidic array with mixer and storage cell along with guard bands as obstacle

Full size image

If there exist even number of odd degree vertices, we can pair them in such a way that all vertices in the graph have even degree [8]. A matching M in a graph G = (V, E) comprises pair-wise non-adjacent edges, i.e. a common vertex is not shared by any two edges [8]. Appending additional edges between a pair of non-adjacent vertices is not as easy as adding extra edges between a pair of adjacent vertices. An extra edge in the graph model connecting two non-adjacent vertices i and j signifies an order of edges formulating a path with endpoints at node i and node j.

The Euler tour must be minimised to reduce the testing time. In a graph, this kind of problem can be modelled as the classical Chinese Postman Problem [10]. For doing this, instead of locating the arbitrary matching among the odd degree vertices in the graph representation of the 2D microfluidic array, we choose the closest pairs of odd degree vertices. There may be more than one connected sub-graph in the graphical representation of the microfluidic chip array with obstacle.

We establish a complete, undirected, weighted graph G′ = (V, E). Nodes of this graph represent the vertices with odd degree where microfluidic operations are not running. The least number of edges necessary to reach node j from node i, i.e. shortest Manhattan distance between node i and node j, is symbolised by w(i, j). Then, a perfect matching with minimum weight is found in the graph G′. Perfect matching defines the matching where all vertices of the graph are matched, i.e. every vertex of the graph is incident to exactly one edge of the matching. Minimum matching in a weighted graph usually denotes the perfect matching with minimum weight, i.e. a perfect matching with the weighted sum of all the edges in the matching minimised [9]. This kind of matching is subsequently used for the Eulerisation of the sub-graph model by adding extra edges that guarantee Eulerisation having least possible additional edges. All such sub-graphs of the graph model abstracted from the 2D microfluidic chip array with obstacle are Eulerised (Fig. 52.4).

Fig. 52.4
figure 4

a In sub-graphs G1 and G2, the vertices having odd degree are labelled, b Sub-graph G1 with odd-degree vertices, c Another sub-graph G2 with odd-degree vertices

Full size image

Figure 52.3b shows that there are four sub-graphs with two sub-graphs having zero degree vertices. G1 and G2 are two sub-graphs where vertices have non-zero degree. But G3 and G4 cannot be Eulerised, since these sub-graphs have zero degree vertices. Next, as shown in Fig. 52.5a, we pair the odd-degree vertices which are close to each other in these two sub-graphs G1 and G2 and then we add extra edges to make these sub-graphs eulerize, as shown in Fig. 52.5b. Deploying the above-said algorithm, this is evidenced that required number of edges for different types of array configuration is different. Hence, it depends on the row–column combination of TEDMB as shown in Table 52.1. After performing a comparative study between the number of extra edges required to Eulerise a square electrode array and that for a TEDMB, we obtain Table 52.2.

Fig. 52.5
figure 5

a Pairing the odd-degree vertices in sub-graphs G1 and G2, b Eulerisation of the sub-graphs

Full size image
Table 52.1 Number of additional edges for eulerising the graphs for different TEDMBs
Full size table
Table 52.2 Comparative study of requisite number of additional edges between DMFB and TEDMB
Full size table

Conclusion

In triangular electrode array, Hamiltonian path based testing is not possible due to the restricted movement of droplets along vertical axis (although Hamiltonian path based test is not sufficient testing, it cannot detect electrode short), but Euler circuit based testing works. This Euler circuit based test can be used both in offline and online testings. In this paper, a graph-based droplet traversal testing algorithm has been developed. Here, we have presented an Euler path based testing for online testing that is easy to implement. Some physical failures are thus far not well identified, like those faults related with power supply or deviation of microfluidic assay operation as a consequence of unknown thermal effect or environmental temperature variation [1]. Competent modelling of faults and generation of test stimuli methods are required for the testing of biochips. Although the detection of parametric faults is challenging and may lead in break down at a later stage, catastrophic faults result in the complete abnormality of the system structure, and hence, it should have the highest priority to be detected.