High-level synthesis of digital microfluidic biochips

ABSTRACT

Microfluidic biochips offer a promising platform for massively parallel DNA analysis, automated drug discovery, and real-time biomolecular recognition. Current techniques for full-custom design of droplet-based “digital” biochips do not scale well for concurrent assays and for next-generation system-on-chip (SOC) designs that are expected to include microfluidic components. We propose a system design methodology that attempts to apply classical high-level synthesis techniques to the design of digital microfluidic biochips. We focus here on the problem of scheduling bioassay functions under resource constraints. We first develop an optimal scheduling strategy based on integer linear programming. However, because the scheduling problem is NP-complete, we also develop two heuristic techniques that scale well for large problem instances. A clinical diagnostic procedure, namely multiplexed in-vitro diagnostics on human physiological fluids, is first used to illustrate and evaluate the proposed method. Next, the synthesis approach is applied to a protein assay, which serves as a more complex bioassay application. The proposed synthesis approach is expected to reduce human effort and design cycle time, and it will facilitate the integration of microfluidic components with microelectronic components in next-generation SOCs.

REFERENCES

• 1: Emile Aarts , Jan Korst, Simulated annealing and Boltzmann machines: a stochastic approach to combinatorial optimization and neural computing, John Wiley & Sons, Inc., New York, NY, 1989
• 2: Advanced Liquid Logic, Inc. www.liquid-logic.com.
• 3: Brian A. A. Antao , Arthur J. Brodersen, Techniques for Synthesis of Analog Integrated Circuits, IEEE Design & Test, v.9 n.1, p.8-18, January 1992 [doi>10.1109/54.124513]
• 4: Bean, J. C. 1994. Genetics and random keys for sequencing and optimization. ORSA J. Comput. 6, 154--160.
• 5: Berkelaar, M. lpsolve. Eindhoven University of Technology, Eindhoven, Netherlands. ftp://ftp.ics.ele.tue.nl/pub/lp_solve.
• 6: Böhringer, K. F. 2004. Towards optimal strategies for moving droplets in digital microfluidic systems. In Proceedings of the IEEE International Conference on Robotics and Automation. 1468--1474.
• 7: Burns, M. A., Johnson, B. N., Brahmasandra, S. N., and Handique, K. 1998. An integrated nanoliter DNA analysis device. Science 282, 484--487.
• 8: Raul Camposano, Behavioral synthesis, Proceedings of the 33rd annual conference on Design automation, p.33-34, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240524]
• 9: Cho, S. K., Fan, S. K., Moon, H., and Kim, C. J. 2002. Toward digital microfluidic circuits: Creating, transporting, cutting and merging liquid droplets by electrowetting-based actuation. In Proceedings of the IEEE Conference on Micro-Electro-Mechanical Systems. 32--52.
• 10: CoventorWare. Micro-electro-mechanical systems. http://www.coventor.com.
• 11: S. K. De , N. R. Aluru, Physical And Reduced-Order Dynamic Analysis of MEMS, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.270, November 09-13, 2003 [doi>10.1109/ICCAD.2003.114]
• 12: Ding, J., Chakrabarty, K., and Fair, R. B. 2001. Scheduling of microfluidic operations for reconfigurable two-dimensional electrowetting arrays. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Sys. 20, 1463--1468.
• 13: Richard B. Fair , Andrey Khlystov , Tina D. Tailor , Vladislav Ivanov , Randall D. Evans , Vijay Srinivasan , Vamsee K. Pamula , Michael G. Pollack , Peter B. Griffin , Jack Zhou, Chemical and Biological Applications of Digital-Microfluidic Devices, IEEE Design & Test, v.24 n.1, p.10-24, January 2007 [doi>10.1109/MDT.2007.8]
• 14: Fair, R. B., Khlystov, A., Srinivasan, V., Pamula, V. K., and Weaver, K. N. 2004. Integrated chemical/biochemical sample collection, pre-concentration, and analysis on a digital microfluidic lab-on-a-chip platform. In Proceedings of the SPIE Lab-on-a-Chip: Platforms, Devices, and Applications. L. A. Smith and D. Sobek, Eds. 5591, 113--124.
• 15: Fair, R. B., Srinivasan, V., Paik, P., Ren, H., and Pamula, V. K. 2003. Electrowetting-based on-chip sample processing for integrated microfluidics. In Proceedings of the IEEE International Electronic Devices Meeting (IEDM). 32.5.1--32.5.4.
• 16: Fedder, G. K. and Q. Jing, Q. 1999. A hierarchical circuit-level design methodology for microelectromechinal system. IEEE Trans. Circ. Syst. II. 46, 1309--1315.
• 17: Gallardo, B. S., Gupta, V. K., Eagerton, F. D., Jong, L. I., Craig, V. S., Shah, R. R., and Abbott, N. L. 1999. Electrochemical principles for active control of liquids on submillimeter scales. Science 283, 57--60.
• 18: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 19: Griffith, E. and Akella, S. 2004. Coordinating multiple droplets in planar array digital microfluidics systems. In Proceedings of the Workshop on the Algorithmic Foundations of Robotics.
• 20: Hull, H. F., Danila, R., and Ehresmann, K. 2003. Smallpox and bioterrorism: Public-health responses. J. Lab. Clin. Medicine 142, 221--228.
• 21: Ichimura, K., Oh, S., and Nakagawa, M. 2000. Light-driven motion of liquids on a photoresponsive surface. Science 288, 1624--1626.
• 22: International Technology Roadmap for Semiconductors (ITRS). http://public.itrs.net/Files/2003ITRS/Home2003.htm.
• 23: Jones, T. B., Gunji, M., Washizu, M., and Feldman, M. J. 2001. Dielectrophoretic liquid actuation and nanodroplet formation. J. Appl. Phys. 89, 1441--1448.
• 24: Andrew B. Kahng , Ion Mandoiu , Sherief Reda , Xu Xu , Alex Z. Zelikovsky, Evaluation of Placement Techniques for DNA Probe Array Layout, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.262, November 09-13, 2003 [doi>10.1109/ICCAD.2003.65]
• 25: Yu-Kwong Kwok , Ishfaq Ahmad, Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM Computing Surveys (CSUR), v.31 n.4, p.406-471, Dec. 1999 [doi>10.1145/344588.344618]
• 26: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 27: Mukherjee, T. and Fedder, G. K. 1998. Design methodology for mixed-domain systems-on-a-chip {MEMS design}. In Proceedings of the IEEE Conference on VLSI System Level Design. 96--101.
• 28: Paik, P., Pamula, V. K., and Fair, R. B. 2003. Rapid droplet mixers for digital microfluidic systems. Lab on a Chip 3, 253--259.
• 29: Pamula, K., Srinivasan, V., Chakrapani, H., Fair, R. B., and Toone, E. J. 2005. A droplet-based lab-on-a-chip for colorimetric detection of nitroaromatic explosives. In Proceedings of the IEEE Conference on Micro-Electro-Mechanical Systems. 722--725.
• 30: A. J. Pfeiffer , T. Mukherjee , S. Hauan, Simultaneous design and placement of multiplexed chemical processing systems on microchips, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.229-236, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382577]
• 31: Pollack, M. G. 2001. Electrowetting-based microactuation of droplets for digital microfluidics. Ph.D. thesis, Duke University.
• 32: Pollack, M. G., Fair, R. B., and Shenderov, A. D. 2000. Electrowetting-based actuation of liquid droplets for microfluidic applications. Appl. Phys. Lett. 77, 1725--1726.
• 33: Pollack, M. G., Shenderov, A. D., and Fair, R. B. 2002. Electrowetting-based actuation of droplets for integrated microfluidics. Lab on a Chip 2, 96--101.
• 34: Ren, H. and Fair, R. B. 2002. Micro/nano liter droplet formation and dispensing by capacitance metering and electrowetting actuation. Technical Digest of IEEE-NANO, 36--38.
• 35: Andrew J. Ricketts , Kevin Irick , N. Vijaykrishnan , Mary Jane Irwin, Priority scheduling in digital microfluidics-based biochips, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 36: Sammarco, T. S. and Burns, M. A. 1999. Thermocapillary pumping of discrete droplets in microfabricated analysis devices. Amer. Inst. Chem. Engin. J. 45, 350--366.
• 37: Schulte, T. H., Bardell, R. L., and Weigl, B. H. 2002. Microfluidic technologies in clinical diagnostics. Clinica Chimica Acta 321, 1--10.
• 38: Senturia, S. 1987. Microfabricated structures for the measurement of mechanical properties and adhesion of thin films. In Proceedings of the International Conference on Sold-State Sensors and Actuators (Transducers). 11--16.
• 39: Shapiro, H., Moon, H., Garrell, R., and Kim, C. J. 2003. Modeling of electrowetted surface tension for addressable microfluidic systems: dominant physical effects, material dependences, and limiting phenomena. In Proceedings of the IEEE Conference on Micro-Electro-Mechanical Systems. 201--205.
• 40: Silicon Biosystems. What is DEPArray^TM? http://www.siliconbiosystems.com/technology/DEPArray.htm.
• 41: Spears, W. M. and Dejong, K. A. 1991. On the virtues of parameterized uniform crossover. In Proceedings of the International Conference on Genetic Algorithms. 230--236.
• 42: M. Srinivas , Lalit M. Patnaik, Genetic algorithms: A Survey, Computer, v.27 n.6, p.17-26, June 1994 [doi>10.1109/2.294849]
• 43: Srinivasan, V., Pamula, V. K., and Fair, R. B. 2004. An integrated digital microfluidic lab-on-a-chip for clinical diagnostics on human physiological fluids. Lab on a Chip, 310--315.
• 44: Srinivasan, V., Pamula, V. K., Paik, P., and Fair, R. B. 2004. Protein stamping for MALDI mass spectrometry using an electrowetting-based microfluidic platform. In Proceedings of the SPIE. 5591, 26--32.
• 45: Srinivasan, V., Pamula, V. K., Pollack, M. G., and Fair, R. B. 2003. Clinical diagnostics on human whole blood, plasma, serum, urine, saliva, sweat, and tears on a digital microfluidic platform. In Proceedings of the International Conference on Micro Total Analysis Systems. 1287--1290.
• 46: Fei Su , Krishnendu Chakrabarty, Module placement for fault-tolerant microfluidics-based biochips, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.3, p.682-710, July 2006
• 47: Su, F., Chakrabarty, K., and Fair, R. B. 2006. Microfluidics-based biochips: technology issues, implementation platforms, and design automation challenges. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 25, 211--223.
• 48: Fei Su , William Hwang , Krishnendu Chakrabarty, Droplet routing in the synthesis of digital microfluidic biochips, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 49: Fei Su , Krishnendu Chakrabarty, Concurrent Testing of Droplet-Based Microfluidic Systems for Multiplexed Biomedical Assays, Proceedings of the International Test Conference on International Test Conference, p.883-892, October 26-28, 2004
• 50: Su, F., Ozev, S., and Chakrabarty, K. 2005. Ensuring the operational health of droplet-based microelectrofluidic biosensor systems. IEEE Sensors 5, 763--773.
• 51: Thorsen, T., Maerkl, S., and Quake, S. 2002. Microfluidic large-scale integration. Science 298, 580--584.
• 52: van der Woerd, M., Ferree, D., and Pusey, M. 2003. The promise of macromolecular crystallization in microfluidic chips. J. Struct. Biol. 142, 180--187.
• 53: Venkatesh, S. and Memish, Z. A. 2003. Bioterrorism: A new challenge for public health. Int. J. Antimicrobial Agents 21, 200--206.
• 54: Verpoorte, E. and De Rooij, N. F. 2003. Microfluidics meets MEMS. In Proceedings of the IEEE. 91, 930--953.
• 55: Walker, R. A. and Camposano, R. 1991. A Survey of High-Level Synthesis Systems. Kluwer Academic Publishers, Boston, MA.
• 56: Washizu, M. 1998. Electrostatic actuation of liquid droplets for microreactor applications. IEEE Trans. Indus. Appl. 34, 732--737.
• 57: Zeng, J. and Korsmeyer, F. T. 2004. Principles of droplet electrohydrodynamics for lab-on-a-chip. Lab on a Chip 4, 265--277.
• 58: Zhang, T., Chakrabarty, K., and Fair, R. B. 2002. Microelectrofluidic Systems: Modeling and Simulation. CRC Press, Boca Raton, FL.
• 59: Zhao, Y. and Cho, S. K. 2006. Microparticle sampling by electrowetting-actuated droplet sweeping. Lab on a Chip 6, 137--144.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
High-level synthesis, biochips, microfluidics, scheduling, system-on-chip