Efficient mixture preparation on digital microfluidic biochips

Digital microfluidic biochips are recently being developed for on-chip implementation of biochemical laboratory assays. Existing mixing algorithms determine the mixing tree or mixing graph from a given target ratio of several biochemical fluids for on-chip mixture preparation. We present an algorithm to determine a reduced mixing tree by sharing the common subtrees within itself. We observe two transformations that preserve the semantics of the tree: (a) permutation of leaf nodes (input fluids/reagents) within the same level of a mixing tree, and (b) level-shifting of a leaf node to the next lower level by duplicating its appearance. The proposed algorithm utilizes both the intermediate droplets obtained after a split operation when a pair of identical subtrees are identified under permutation of leaf nodes at the same level. Simulation results for a large set of target ratios show that our algorithm reduces the mean values of the total number of mix-split steps, waste droplets and the number of mixer modules required for earliest completion by 16%, 29% and 12% over Min-Mix and by 22%, 34% and 20% over RMA, respectively. Moreover, it reduces the number of checkpoint insertions required for dynamic error recovery against incorrect mix-split steps during mixture preparation.