Abstract
Significant researches are going on for high performance droplet routing in Digital Microfluidic Biochip (DMFB). This chapter elaborates an ant colony optimization based droplet routing technique for high performance design in DMFB. The method is divided into two phases. (1) In the first phase, two dedicated ants generated from each source of the droplets traverse the rectilinear path between the source-target pairs and deposit pheromone to construct rectangular bounding box. Initial bounding box helps in restricted ant movements in the next phase. (2) In the second phase, real routing path is generated. Detour and stalling phenomena are incurred to resolve routing conflict. The method has explored both single ant and multiple ant systems to address detours from the conflicting zone in search for the best possible route towards destination. The method has been simulated on several existing benchmarks and comparative results are quite encouraging.
TopIntroduction
Digital microfluidic biochip (DMFB) revolutionizes the medical diagnosis process rendering multiple tasks executed on a single chip. Microfluidic based biochips are presently aiding different pathological experimentations and many biochemical laboratory procedures due to their advantages of automation, cost diminution, portability, and competence (Pamula, Srinivasan & Fair, 2004). Growing trends of demand and need for incorporation of multiple-functionality makes the design process complex and costly for digital microfluidic biochip. It has laid a scope for optimization in computer aided design and test before on-chip fabrication. In present days it is a thriving field for researchers and they are exploring different design aspects to deliver a fully customized biochip (Fair, Su & Chakrabarty, 2006). Digital microfluidic biochip is a small test cites which comprises an array of electrodes sandwiched between two parallel plates. The droplets are manipulated (stored, transported, mixed or reacted) over the electrodes by changing the voltage of two adjacent electrodes and droplets are transported from one electrode to the next by electro-wetting on dielectric (EWOD) technique (Pamula et al., 2004) (Figure 1). Droplet routing is one of the fundamental issues in design of DMFB and major variants in this field are direct addressing mode, cross-referencing mode and pin-constrained droplet routing and design (Chakrabarty, 2010). Mostly, geometry level synthesis of biochip design involves droplet routing, and all the problems are formulated as complex optimization problems, which are NP hard in nature (Su, Ozev & Chakrabarty, 2004; De Micheli, 1994).
Researchers and CAD developers propose several models to solve those optimization problems. Mostly explored field is integer linear program (ILP) solver. ILP solver is a deterministic process which can provide solutions even for hard bioassay protocols. Meta heuristic search procedures are modern in their nature and are merely deployed in the field of biochip design automation. Some works exploring meta-heuristic techniques, named tabu search (TS) and simulated annealing (SA), are found in (Paul, Elena & Madsen, 2009; Xiao & Young, 2010) respectively. Droplet routing in digital microfluidic biochip can be modeled as a combinatorial optimization (CO) problem, and aim of this work is to solve the CO problem using a Meta heuristic strategy named ant colony optimization (ACO). ACO is basically a probabilistic model that uses stochastic search procedure to generate solution (Chun, Huang & Hao, 2009).
Key Terms in this Chapter
Wash Droplet: Mainly water droplets are strategically routed in between two consecutive uses of any electrode to minimize the risk of cross contamination. This type of droplet is familiar as wash droplet.
Digital Microfluidic Biochip (DMFB): This second generation biochip or which is the modern technology. Fluidic operations are manipulated by electrowetting mechanisms or dielectrophoresis. They are capable of multiple operations at same time instance.
Bioassay Protocol: Several pathological operations are transfigured in to biochip operations. In order to accomplish this, information on sample operations is structured in a sequence compatible for on chip operations. This sequence is known as bioassay protocol. Normally biochemists provide the master input regarding the pathological operations which are then codified in the form of bioassay protocol.
Cross Contamination: Performance optimization of digital microfluidic biochip often require reuse of same electrodes by different test fluids at different time interval. In such cases, succeeding fluid may get contaminated through the residue left by its preceding fluid. This type of contamination is familiar as cross contamination and this often causes in erroneous results at the detector.
Three Pin Net: In some of the digital microfluidic biochip operations two different test droplets coming from two different source electrodes are merged at a designated electrode and then the merged droplet is routed to a specific target electrode. These types of operational requirements come with the details of two different source locations along with a target location. They are known as three pin net.
Dielectrophoresis: Dielectrophoresis (DEP) is a phenomenon in which a force is exerted on a dielectric particle when it is subjected to a non-uniform electric field. This force does not require the particle to be charged. All particles exhibit dielectrophoretic activity in the presence of electric fields. However, the strength of the force depends strongly on the medium and particles' electrical properties, on the particles' shape and size, as well as on the frequency of the electric field.
Cross Referencing Biochip: It is row – column or two dimensional array addressing scheme for the electrodes of digital microfluidic biochip. Total number of addressing pin required is remarkably less in compare to direct addressing scheme but operations are complex and require extra caution to avoid unwanted mixing.
Biochip Operations: There are three basic operations in biochip. Those are dispensing, routing and detection. Apart from these some important operations are mixing, splitting and garbage collection.
Direct Addressing Mode Biochip: Individual electrodes are controlled via separately designated pins. Number of address pins required are same as number of electrodes. It is easy to operate but design is heavy and complex due to huge pin requirement.
Source Reservoir: Reservoir associated or connected externally to some of the electrodes of biochip and it contains samples of fluids and chemicals required to carry out designated tests. Fluids and chemical droplets are dispensed from these source reservoirs at the beginning of operations.
Droplet Routing: Test droplets are open transported from a specified location to another location as per the bioassay protocol. Transmission of droplets over the biochip is known as droplet routing.
Two Pin Net: In some of the digital microfluidic biochip operations droplets are dispensed at a specific location (known as source location) and then they are routed towards a designated terminal location (known as target location). These types of operational requirements come with the information of source location and corresponding target location. They are known as two pin net.
Continuous Fluid Flow Based Biochip: This is called first generation biochip. Fluids were circulated by external mechanical micro pumps by combination of capillary forces and electro kinetic mechanisms. This generation couldn’t support multiple droplet operations and was less effective.
Electrowetting: The electrowetting effect has been defined as the change in solid-electrolyte contact angle due to an applied potential difference between the solid and the electrolyte. The phenomenon of electrowetting can be understood in terms of the forces that result from the applied electric field.
Waste Reservoir: A few reservoirs are associated with the biochip for collection of post operative samples and residues. These post operative samples are called waste and the reservoir is called waste reservoir.