skip to main content
research-article

Layout-Aware Mixture Preparation of Biochemical Fluids on Application-Specific Digital Microfluidic Biochips

Published:24 June 2015Publication History
Skip Abstract Section

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.

References

  1. Mohamed Abdelgawad and Aaron R. Wheeler. 2009. The digital revolution: A new paradigm for microfluidics. Advanced Materials 21, 8, 920--925.Google ScholarGoogle ScholarCross RefCross Ref
  2. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. Vaishnavi Ananthanarayanan and William Thies. 2010. Biocoder: A programming language for standardizing and automating biology protocols. J. Biol. Eng. 4, 1--13.Google ScholarGoogle ScholarCross RefCross Ref
  4. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  5. 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 ScholarGoogle ScholarCross RefCross Ref
  6. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  7. 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 ScholarGoogle Scholar
  8. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  9. Krishnendu Chakrabarty and Fei Su. 2007. Digital Microfluidic Biochips: Synthesis, Testing and Reconfiguration Techniques. CRC Press.Google ScholarGoogle Scholar
  10. Krishnendu Chakrabarty and Tao Xu. 2010. Digital Microfluidic Biochips: Design and Optimization. CRC Press.Google ScholarGoogle Scholar
  11. 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 ScholarGoogle ScholarCross RefCross Ref
  12. 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 ScholarGoogle Scholar
  13. 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 ScholarGoogle ScholarCross RefCross Ref
  14. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  15. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  16. 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 ScholarGoogle ScholarCross RefCross Ref
  17. Keith E. Herold and Avraham Rasooly. 2009. Lab-on-a-Chip Technology (Vol. 1): Fabrication and Microfluidics. Caister Academic Press.Google ScholarGoogle Scholar
  18. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  19. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  20. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  21. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  22. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  23. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. 1983. Optimization by simulated annealing. Science 220, 671--680.Google ScholarGoogle ScholarCross RefCross Ref
  24. Jon Kleinberg and Eva Tardos. 2005. Algorithm Design. Addison Wesley. Google ScholarGoogle ScholarDigital LibraryDigital Library
  25. 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 ScholarGoogle ScholarCross RefCross Ref
  26. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  27. 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 ScholarGoogle ScholarCross RefCross Ref
  28. Elizabeth M. Miller and Aaron R. Wheeler. 2009. Digital bioanalysis. Springer J. Analytical Bioanalytical Chem. 393, 2, 419--426.Google ScholarGoogle ScholarCross RefCross Ref
  29. 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 ScholarGoogle ScholarCross RefCross Ref
  30. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  31. 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 ScholarGoogle ScholarCross RefCross Ref
  32. 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 ScholarGoogle ScholarCross RefCross Ref
  33. 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 ScholarGoogle Scholar
  34. 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 ScholarGoogle ScholarCross RefCross Ref
  35. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  36. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  37. 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 ScholarGoogle ScholarCross RefCross Ref
  38. 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 ScholarGoogle Scholar
  39. 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 ScholarGoogle ScholarCross RefCross Ref
  40. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  41. 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 ScholarGoogle ScholarCross RefCross Ref
  42. Marcus Schaefer. 2013. The graph crossing number and its variants: A survey. Electronic J. Combinatorics: Dynamic Surveys, 21.Google ScholarGoogle Scholar
  43. 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 ScholarGoogle ScholarCross RefCross Ref
  44. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  45. Fei Su and Krishnendu Chakrabarty. 2008. High-level synthesis of digital microfluidic biochips. ACM J. Emerg. Technol. Comput. Syst. 3, 4, 1--32.Google ScholarGoogle ScholarDigital LibraryDigital Library
  46. 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 ScholarGoogle ScholarCross RefCross Ref
  47. Roberto Tamassia. 2013. Handbook of Graph Drawing and Visualization. Chapman & Hall/CRC. Google ScholarGoogle ScholarDigital LibraryDigital Library
  48. 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 ScholarGoogle ScholarCross RefCross Ref
  49. William Thies, John Paul Urbanski, Todd Thorsen, and Saman Amarasinghe. 2008. Abstraction layers for scalable microfluidic biocomputing. Natural Computing 7, 2, 255--275. Google ScholarGoogle ScholarDigital LibraryDigital Library
  50. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  51. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  52. Antoine Zoghbi and Ivan Stojmenović. 1998. Fast algorithms for generating integer partitions. Int. J. Comput. Math. 70, 2 319--332.Google ScholarGoogle ScholarCross RefCross Ref

Index Terms

  1. Layout-Aware Mixture Preparation of Biochemical Fluids on Application-Specific Digital Microfluidic Biochips

              Recommendations

              Comments

              Login options

              Check if you have access through your login credentials or your institution to get full access on this article.

              Sign in

              Full Access

              • Published in

                cover image ACM Transactions on Design Automation of Electronic Systems
                ACM Transactions on Design Automation of Electronic Systems  Volume 20, Issue 3
                June 2015
                345 pages
                ISSN:1084-4309
                EISSN:1557-7309
                DOI:10.1145/2796316
                • Editor:
                • Naehyuck Chang
                Issue’s Table of Contents

                Copyright © 2015 ACM

                Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

                Publisher

                Association for Computing Machinery

                New York, NY, United States

                Publication History

                • Published: 24 June 2015
                • Accepted: 1 January 2015
                • Revised: 1 November 2014
                • Received: 1 July 2014
                Published in todaes Volume 20, Issue 3

                Permissions

                Request permissions about this article.

                Request Permissions

                Check for updates

                Qualifiers

                • research-article
                • Research
                • Refereed

              PDF Format

              View or Download as a PDF file.

              PDF

              eReader

              View online with eReader.

              eReader