Synthesis of Digital Microfluidic Biochips with Reconfigurable Operation Execution

Microfluidic biochips are an alternative to conventional biochemical laboratories, and are able to integrate on-chip all the necessary functions for biochemical analysis. The “digital” biochips are manipulating liquids not as a continuous flow, but as discrete droplets on a two-dimensional array of electrodes. The main objective of this thesis is to develop top-down synthesis techniques for digital microfluidic biochips. So far, researchers have assumed that operations are executing on virtual modules of rectangular shape, formed by grouping adjacent electrodes, and which have a fixed placement on the microfluidic array. However, operations can actually execute by routing the droplets on any sequence of electrodes on the biochip. Thus, we have proposed a routing-based model of operation execution, and we have developed several associated synthesis approaches, which progressively relax the assumption that operations execute inside fixed rectangular modules. The proposed synthesis approaches consider that i) modules can dynamically move during their execution and ii) can have non-rectangular shapes. iii) We have relaxed the assumption that all electrodes are occupied during the operation execution, by taking into account the position of droplets inside modules. Finally, iv) we have eliminated the concept of virtual modules and have allowed the droplets to move on the chip on any route. In this context, we have also shown how contamination can be avoided. We have extensively evaluated the proposed approaches using several real-life case studies and synthetic benchmarks. The experiments show that by considering the dynamically reconfigurable nature of microfluidic operations, significant improvements can be obtained, decreasing the biochemical application completion times, reducing thus the biochip area and implementation costs.