Abstract
The recent proliferation of digital microfluidic (DMF) biochips has enabled rapid on-chip implementation of many biochemical laboratory assays or protocols. Sample preprocessing, which includes dilution and mixing of reagents, plays an important role in the preparation of assays. The automation of sample preparation on a digital microfluidic platform often mandates the execution of a mixing algorithm, which determines a sequence of droplet mix-split steps (usually represented as a mixing graph). However, the overall cost and performance of on-chip mixture preparation not only depends on the mixing graph but also on the resource allocation and scheduling strategy, for instance, the placement of boundary reservoirs or dispensers, mixer modules, storage units, and physical design of droplet-routing pathways. In this article, we first present a new mixing algorithm based on a number-partitioning technique that determines a layout-aware mixing tree corresponding to a given target ratio of a number of fluids. The mixing graph produced by the proposed method can be implemented on a chip with a fewer number of crossovers among droplet-routing paths as well as with a reduced reservoir-to-mixer transportation distance. Second, we propose a routing-aware resource-allocation scheme that can be used to improve the performance of a given mixing algorithm on a chip layout. The design methodology is evaluated on various test cases to demonstrate its effectiveness in mixture preparation with the help of two representative mixing algorithms. Simulation results show that on average, the proposed scheme can reduce the number of crossovers among droplet-routing paths by 89.7% when used in conjunction with the new mixing algorithm, and by 75.4% when an earlier algorithm [Thies et al. 2008] is used.
- Mohamed Abdelgawad and Aaron R. Wheeler. 2009. The digital revolution: A new paradigm for microfluidics. Advanced Materials 21, 8, 920--925.Google ScholarCross Ref
- Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley. Google ScholarDigital Library
- Vaishnavi Ananthanarayanan and William Thies. 2010. Biocoder: A programming language for standardizing and automating biology protocols. J. Biol. Eng. 4, 1--13.Google ScholarCross Ref
- Sukanta Bhattacharjee, Ansuman Banerjee, and Bhargab B. Bhattacharya. 2012. Multiple dilution sample preparation using digital microfluidic biochips. In Proceedings of the International Symposium on Electronic System Design. 188--192. Google ScholarDigital Library
- Sukanta Bhattacharjee, Ansuman Banerjee, and Bhargab B. Bhattacharya. 2014. Sample preparation with multiple dilutions on digital microfluidic biochips. IET Comput. Digital Tech. 8, 1 49--58.Google ScholarCross Ref
- Christoph Buchheim, Markus Chimani, Dietmar Ebner, Carsten Gutwenger, Michael Jünger, GunnarW. Klau, Petra Mutzel, and René Weiskircher. 2008. A branch-and-cut approach to the crossing number problem. Discrete Optim. 5, 2, 373--388. Google ScholarDigital Library
- Christoph Buchheim, Markus Chimani, Carsten Gutwenger, Michael Jünger, and Petra Mutzel. 2013. Chapter 2: Crossings and planarization. In Handbook of Graph Drawing and Visualization, 43--85.Google Scholar
- Olca A. Çakroğlu, Cesim Erten, Omer Karataş, and Melih Sozdinler. 2007. Crossing Minimization in Weighted Bipartite Graphs. In Proceedings of the International Conference on Experimental Algorithms, Lecture Notes in Computer Science, vol. 4525. 122--135. Google ScholarDigital Library
- Krishnendu Chakrabarty and Fei Su. 2007. Digital Microfluidic Biochips: Synthesis, Testing and Reconfiguration Techniques. CRC Press.Google Scholar
- Krishnendu Chakrabarty and Tao Xu. 2010. Digital Microfluidic Biochips: Design and Optimization. CRC Press.Google Scholar
- Debalina Chatterjee, Boonta Hetayothin, Aaron R. Wheeler, Daniel J. King, and Robin L. Garrell. 2006. Droplet-based microfluidics with nonaqueous solvents and solutions. Lab Chip 6, 2, 199--206.Google ScholarCross Ref
- Ting-Wei Chiang, Chia-Hung Liu, and Juinn-Dar Huang. 2013. Graph-based optimal reactant minimization for sample preparation on digital microfluidic biochips. In Proceedings of the International Symposium on VLSI Design, Automation, and Test. 1--4.Google Scholar
- Trung Anh Dinh, Shigeru Yamashita, and Tsung-Yi Ho. 2014. A network-flow-based optimal sample preparation algorithm for digital microfluidic biochips. In Proceedings of the Asia and South Pacific Design Automation Conference. 225--230.Google ScholarCross Ref
- Michael R. Garey and David S. Johnson. 1979. Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company. Google ScholarDigital Library
- Eric J. Griffith, Srinivas Akella, and Mark K. Goldberg. 2006. Performance characterization of a reconfigurable planar-array digital microfluidic system. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 25, 2, 345--357. Google ScholarDigital Library
- B. Hadwen, G. R. Broder, D. Morganti, A. Jacobs, C. Brown, J. R. Hector, Y. Kubota, and Hywel Morgan. 2012. Programmable large area digital microfluidic array with integrated droplet sensing for bioassays. Lab Chip 12, 18, 3305--3313.Google ScholarCross Ref
- Keith E. Herold and Avraham Rasooly. 2009. Lab-on-a-Chip Technology (Vol. 1): Fabrication and Microfluidics. Caister Academic Press.Google Scholar
- Yi-Ling Hsieh, Tsung-Yi Ho, and Krishnendu Chakrabarty. 2012a. A reagent-saving mixing algorithm for preparing multiple-target biochemical samples using digital microfluidics. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 31, 11, 1656--1669. Google ScholarDigital Library
- Yi-Ling Hsieh, Tsung-Yi Ho, and Krishnendu Chakrabarty. 2012b. Design methodology for sample preparation on digital microfluidic biochips. In Proceedings of the IEEE International Conference on Computer Design. 189--194. Google ScholarDigital Library
- Yi-Ling Hsieh, Tsung-Yi Ho, and Krishnendu Chakrabarty. 2014. Biochip synthesis and dynamic error recovery for sample preparation using digital microfluidics. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 33, 2, 183--196. Google ScholarDigital Library
- Juinn-Dar Huang, Chia-Hung Liu, and Ting-Wei Chiang. 2012. Reactant minimization during sample preparation on digital microfluidic biochips using skewed mixing trees. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. 377--384. Google ScholarDigital Library
- Juinn-Dar Huang, Chia-Hung Liu, and Huei-Shan Lin. 2013. Reactant and waste minimization in multitarget sample preparation on digital microfluidic biochips. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 32, 10, 1484--1494. Google ScholarDigital Library
- S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. 1983. Optimization by simulated annealing. Science 220, 671--680.Google ScholarCross Ref
- Jon Kleinberg and Eva Tardos. 2005. Algorithm Design. Addison Wesley. Google ScholarDigital Library
- Srijan Kumar, Sudip Roy, Partha P. Chakrabarti, Bhargab B. Bhattacharya, and Krishnendu Chakrabarty. 2013. Efficient mixture preparation on digital microfluidic biochips. In Proceedings of the IEEE International Symposium on Design and Diagnostics of Electronic Circuits Systems. 205--210.Google ScholarCross Ref
- Chia-Hung Liu, Hao-Han Chang, Tung-Che Liang, and Juinn-Dar Huang. 2013. Sample preparation for many-reactant bioassay on dmfbs using common dilution operation sharing. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. 615--621. Google ScholarDigital Library
- Lingzhi Luo and Srinivas Akella. 2011. Optimal scheduling of biochemical analyses on digital microfluidic systems. IEEE Trans. Autom. Sci. Eng. 8, 1, 216--227.Google ScholarCross Ref
- Elizabeth M. Miller and Aaron R. Wheeler. 2009. Digital bioanalysis. Springer J. Analytical Bioanalytical Chem. 393, 2, 419--426.Google ScholarCross Ref
- Debasis Mitra, Sudip Roy, Sukanta Bhattacharjee, Krishnendu Chakrabarty, and Bhargab B. Bhattacharya. 2014. On-chip sample preparation for multiple targets using digital microfluidics. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 33, 8, 1131--1144.Google ScholarCross Ref
- Debasis Mitra, Sudip Roy, Krishnendu Chakrabarty, and Bhargab B. Bhattacharya. 2012. On-chip sample preparation with multiple dilutions using digital microfluidics. In Proceedings of the IEEE Annual Symposium on VLSI. 314--319. Google ScholarDigital Library
- Philip Y. Paik, Vamsee K. Pamula, and Richard B. Fair. 2003a. Rapid droplet mixers for digital microfluidic systems. Lab Chip 3, 4, 253--259.Google ScholarCross Ref
- Philip Y. Paik, Vamsee K. Pamula, Michael G. Pollack, and Richard B. Fair. 2003b. Electrowetting-based droplet mixers for microfluidic systems. Lab Chip 3, 1 28--33.Google ScholarCross Ref
- Hong Ren, Vijay Srinivasan, and Richard B. Fair. 2003. Design and testing of an interpolating mixing architecture for electrowetting-based droplet-on-chip chemical dilution. In Proceedings of the International Solid-State Sensors, Actuators and Microsystems Conference. 619--622.Google Scholar
- R. Bruce Richter and Carsten Thomassen. 1997. Relations between crossing numbers of complete and complete bipartite graphs. Am. Math. Monthly 104, 2, 131--137.Google ScholarCross Ref
- Sudip Roy, Bhargab B. Bhattacharya, Partha P. Chakrabarti, and Krishnendu Chakrabarty. 2011b. Layout-aware solution preparation for biochemical analysis on a digital microfluidic biochip. In Proceedings of the International Conference on VLSI Design. 171--176. Google ScholarDigital Library
- Sudip Roy, Bhargab B. Bhattacharya, and Krishnendu Chakrabarty. 2010. Optimization of dilution and mixing of biochemical samples using digital microfluidic biochips. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 29, 11, 1696--1708. Google ScholarDigital Library
- Sudip Roy, Bhargab B. Bhattacharya, and Krishnendu Chakrabarty. 2011a. Waste-aware dilution and mixing of biochemical samples with digital microfluidic biochips. In Proceedings of the Design, Automation Test in Europe Conference Exhibition. 1059--1064.Google ScholarCross Ref
- Sudip Roy, Bhargab B. Bhattacharya, Sarmishtha Ghoshal, and Krishnendu Chakrabarty. 2014a. An optimal two-mixer dilution engine with digital microfluidics for low-power applications. ASP J. Low Power Electronics 10, 3, 1--12.Google Scholar
- Sudip Roy, Bhargab B. Bhattacharya, Sarmishtha Ghoshal, and Krishnendu Chakrabarty. 2014b. High-throughput dilution engine for sample preparation on digital microfluidic biochips. IET Comput. Digital Tech. 8, 4, 163--171.Google ScholarCross Ref
- Sudip Roy, Bhargab B. Bhattacharya, Sarmishtha Ghoshal, and Krishnendu Chakrabarty. 2014c. Theory and analysis of generalized mixing and dilution of biochemical fluids using digital microfluidic biochips. ACM J. Emerg. Technol. Comput. Syst. 11, 1, 2.1--2.33. Google ScholarDigital Library
- Sudip Roy, Partha P. Chakrabarti, Srijan Kumar, Bhargab B. Bhattacharya, and Krishnendu Chakrabarty. 2013. Routing-aware resource allocation for mixture preparation in digital microfluidic biochips. In Proceedings of the IEEE Annual Symposium on VLSI. 1--6.Google ScholarCross Ref
- Marcus Schaefer. 2013. The graph crossing number and its variants: A survey. Electronic J. Combinatorics: Dynamic Surveys, 21.Google Scholar
- Ramakrishna Sista, Zhishan Hua, Prasanna Thwar, Arjun Sudarsan, Vijay Srinivasan, Allen E. Eckhardt, Michael G. Pollack, and Vamsee K. Pamula. 2008. Development of a digital microfluidic platform for point of care testing. Lab Chip 8, 12, 2091--2104.Google ScholarCross Ref
- Fei Su and Krishnendu Chakrabarty. 2004. Architectural-level synthesis of digital microfluidics-based biochips. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. 223--228. Google ScholarDigital Library
- Fei Su and Krishnendu Chakrabarty. 2008. High-level synthesis of digital microfluidic biochips. ACM J. Emerg. Technol. Comput. Syst. 3, 4, 1--32.Google ScholarDigital Library
- Kozo Sugiyama, Shojiro Tagawa, and Mitsuhiko Toda. 1981. Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst. Man Cybern. 11, 2, 109--125.Google ScholarCross Ref
- Roberto Tamassia. 2013. Handbook of Graph Drawing and Visualization. Chapman & Hall/CRC. Google ScholarDigital Library
- Hsih Yin Tan, Weng Keong Loke, Yong Teng Tan, and Nam-Trung Nguyen. 2008. A lab-on-a-chip for detection of nerve agent sarin in blood. Lab Chip 8, 6, 885--891.Google ScholarCross Ref
- William Thies, John Paul Urbanski, Todd Thorsen, and Saman Amarasinghe. 2008. Abstraction layers for scalable microfluidic biocomputing. Natural Computing 7, 2, 255--275. Google ScholarDigital Library
- Yang Zhao and Krishnendu Chakrabarty. 2009. Cross-contamination avoidance for droplet routing in digital microfluidic biochips. In Proceedings of the Design, Automation Test in Europe Conference Exhibition. 1290--1295. Google ScholarDigital Library
- Yang Zhao and Krishnendu Chakrabarty. 2010. Synchronization of washing operations with droplet routing for cross-contamination avoidance in digital microfluidic biochips. In Proceedings of the IEEE/ACM Design Automation Conference. 635--640. Google ScholarDigital Library
- Antoine Zoghbi and Ivan Stojmenović. 1998. Fast algorithms for generating integer partitions. Int. J. Comput. Math. 70, 2 319--332.Google ScholarCross Ref
Index Terms
Layout-Aware Mixture Preparation of Biochemical Fluids on Application-Specific Digital Microfluidic Biochips
Recommendations
Error-Correcting Sample Preparation with Cyberphysical Digital Microfluidic Lab-on-Chip
Digital (droplet-based) microfluidic technology offers an attractive platform for implementing a wide variety of biochemical laboratory protocols, such as point-of-care diagnosis, DNA analysis, target detection, and drug discovery. A digital ...
Theory and analysis of generalized mixing and dilution of biochemical fluids using digital microfluidic biochips
Digital microfluidic (DMF) biochips are recently being advocated for fast on-chip implementation of biochemical laboratory assays or protocols, and several algorithms for diluting and mixing of reagents have been reported. However, all methods for such ...
Demand-Driven Single- and Multitarget Mixture Preparation Using Digital Microfluidic Biochips
Special Section on Advances in Physical Design Automation and Regular PapersRecent studies in algorithmic microfluidics have led to the development of several techniques for automated solution preparation using droplet-based digital microfluidic (DMF) biochips. A major challenge in this direction is to produce a mixture of ...
Comments