Sudip Roy
Krishnendu Chakrabarty
Abstract
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 automatic sample preparation suffer from a drawback that they assume the availability of input fluids in pure form, that is, each with an extreme concentration factor (CF) of 100%. In many real-life scenarios, the stock solutions consist of samples/reagents with multiple CFs. No algorithm is yet known for preparing a target mixture of fluids with a given ratio when its constituents are supplied with random concentrations. An intriguing question is whether or not a given target ratio is feasible to produce from such a general input condition. In this article, we first study the feasibility properties for the generalized mixing problem under the (1:1) mix-split model with an allowable error in the target CFs not exceeding 1 2d, where the integer d is user specified and denotes the desired accuracy level of CF. Next, an algorithm is proposed which produces the desired target ratio of N reagents in ONd mix-split steps, where N ( ≥ 3) denotes the number of constituent fluids in the mixture. The feasibility analysis also leads to the characterization of the total space of input stock solutions from which a given target mixture can be derived, and conversely, the space of all target ratios, which are derivable from a given set of input reagents with arbitrary CFs. Finally, we present a generalized algorithm for diluting a sample S in minimum (1:1) mix-split steps when two or more arbitrary concentrations of S (diluted with the same buffer) are supplied as inputs. These results settle several open questions in droplet-based algorithmic microfluidics and offer efficient solutions for a wider class of on-chip sample preparation problems.
- M. Abdelgawad and A. R. Wheeler. 2009. The digital revolution: A new paradigm for microfluidics. Adv. Mater. 21, 920--925.Google Scholar
Cross Ref
- S. Bhattacharjee, A. Banerjee, and B. 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
- S. Bhattacharjee, A. Banerjee, and B. B. Bhattacharya. 2014. Sample preparation with multiple dilutions on digital microfluidic biochips. IET Comput. Digital Tech. 8, 1, 49--58.Google ScholarCross Ref
- S. Bhattacharjee, A. Banerjee, T.-Y. Ho, K. Chakrabarty, and B. B. Bhattacharya. 2013. Algorithms for producing linear dilution gradient with digital microfluidics. CoRR abs/1307.1251.Google Scholar
- K. Chakrabarty and T. Xu. 2010. Digital Microfluidic Biochips: Design and Optimization.Google Scholar
- D. Chatterjee, B. Hetayothin, A. R. Wheeler, D. J. King, and R. L. Garrell. 2006. Droplet-based microfluidics with nonaqueous solvents and solutions. Lab-on-a-Chip 6, 199--206.Google ScholarCross Ref
- T.-W. Chiang, C.-H. Liu, and J.-D. 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
- S. K. Cho, H. M., and C.-J. Kim. 2003. Creating, transporting, cutting, and merging liquid droplets by electrowetting-based actuation for digital microfluidic circuits. J. Microelectromechanical Syst. 12, 1, 70--80.Google ScholarCross Ref
- N. J. Cira, J. Y. Ho, M. E. Dueck, and D. B. Weibel. 2012. A self-loading microfluidic device for determining the minimum inhibitory concentration of antibiotics. Lab-on-a-Chip 12, 6, 1052--1059.Google ScholarCross Ref
- T. A. Dinh, S. Yamashita, and T.-Y. 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
- R. B. Fair. 2007. Digital microfluidics: Is a true lab-on-a-chip possible? Microfluid. Nanofluid. 3, 245--281.Google ScholarCross Ref
- R. B. Fair, A. Khlystov, T. D. Tailor, V. Ivanov, R. D. Evans, P. B. Griffin, V. Srinivasan, V. K. Pamula, M. G. Pollack, and J. Zhou. 2007. Chemical and biological applications of digital-microfluidic devices. IEEE Des. Test Comput. 24, 1, 10--24. Google ScholarDigital Library
- Y. Fouillet, D. Jary, C. Chabrol, P. Claustre, and C. Peponnet. 2008. Digital microfluidic design and optimization of classic and new fluidic functions for lab on a chip systems. Microfluid. Nanofluid. 4, 3, 159--165.Google ScholarCross Ref
- M. R. Garey and D. S. Johnson. 1979. Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company. Google ScholarDigital Library
- E. J. Griffith, S. Akella, and M. K. Goldberg. 2006. Performance characterization of a reconfigurable planar-array digital microfluidic system. IEEE Trans. CAD 25, 2, 345--357. Google ScholarDigital Library
- K. E. Herold and A. Rasooly. 2009. Lab-on-a-Chip Technology (Vol. 1): Fabrication and Microfluidics. Caister Academic Press.Google Scholar
- Y.-L. Hsieh, T.-Y. Ho, and K. Chakrabarty. 2012. A reagent-saving mixing algorithm for preparing multiple-target biochemical samples using digital microfluidics. IEEE Trans. CAD 31, 11, 1656--1669. Google ScholarDigital Library
- Y.-L. Hsieh, T.-Y. Ho, and K. Chakrabarty. 2014. Biochip synthesis and dynamic error recovery for sample preparation using digital microfluidics. IEEE Trans. CAD 33, 2, 183--196. Google ScholarDigital Library
- J.-D. Huang, C.-H. Liu, and T.-W. Chiang. 2012. Reactant minimization during sample preparation on digital microfluidic biochips using skewed mixing trees. In Proceedings of the IEEE International Conference on Computer-Aided Design. 377--384. Google ScholarDigital Library
- J.-D. Huang, C.-H. Liu, and H.-S. Lin. 2013. Reactant and waste minimization in multitarget sample preparation on digital microfluidic biochips. IEEE Trans. CAD 32, 10, 1484--1494. Google ScholarDigital Library
- T.-W. Huang and T.-Y. Ho. 2011. A two-stage ILP-based droplet routing algorithm for pin-constrained DMF biochips. IEEE Trans. CAD 30, 2, 215--228. Google ScholarDigital Library
- T.-W. Huang, C.-H. Lin, and T.-Y. Ho. 2010. A contamination aware droplet routing algorithm for the synthesis of digital microfluidic biochips. IEEE Trans. CAD 19, 11, 1682--1695. Google ScholarDigital Library
- M. J. Jebrail and A. R. Wheeler. 2009. Digital microfluidic method for protein extraction by precipitation. Anal. Chim. Acta 81, 1, 330--335.Google ScholarCross Ref
- J. Kleinberg and E. Tardos. 2005. Algorithm Design. Addison-Wesley. Google ScholarDigital Library
- S. Kumar, S. Roy, P. P. Chakrabarti, B. B. Bhattacharya, and K. Chakrabarty. 2013. Efficient mixture preparation on digital microfluidic biochips. In Proceedings of the IEEE 16th International Symposium on Design and Diagnostics of Electronic Circuits & Systems. 205--210.Google Scholar
- K. Lee, C. Kim, B. Ahn, R. Panchapakesan, A. R. Full, L. Nordee, J. Y. Kang, and K. W. Oh. 2009. Generalized serial dilution module for monotonic and arbitrary microfluidic gradient generators. Lab-on-a-Chip 9, 709--717.Google ScholarCross Ref
- C. C.-Y. Lin and Y.-W. Chang. 2011. Cross-contamination aware design methodology for pin-constrained digital microfluidic biochips. IEEE Trans. CAD 30, 6, 817--828. Google ScholarDigital Library
- C.-H. Liu, H.-H. Chang, T.-C. Liang, and J.-D. 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
- V. N. Luk and A. R. Wheeler. 2009. A Digital Microfluidic Approach to Proteomic Sample Processing. Analytica Chimica Acta 81, 11, 4524--4530.Google Scholar
- Y. Luo, K. Chakrabarty, and T.-Y. Ho. 2013. Error recovery in cyberphysical digital microfluidic biochips. IEEE Trans. CAD 32, 1, 59--72. Google ScholarDigital Library
- Y. Luo, T.-Y. Ho, and K. Chakrabarty. 2012. Dictionary-based error recovery in cyberphysical digital-microfluidic biochips. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. 369--376. Google ScholarDigital Library
- E. Maftei, P. Pop, and J. Madsen. 2012. Routing-based synthesis of digital microfluidic biochips. Des. Automation Embed. Syst. 16, 1, 19--44. Google ScholarDigital Library
- E.M. Miller and A. R.Wheeler. 2009. Digital bioanalysis. Anal. Bioanal. Chem. 393, 2, 419--426.Google ScholarCross Ref
- D. Mitra, S. Roy, K. Chakrabarty, and B. B. Bhattacharya. 2012. On-chip sample preparation with multiple dilutions using digital microfluidics. In Proceedings of the IEEE International Symposium on VLSI. 314--319. Google ScholarDigital Library
- H. Ren, V. Srinivasan, and R. B. Fair. 2003. Design and testing of an interpolating mixing architecture for electrowetting-based droplet-on-chip chemical dilution. In Proceedings of the International Conference on Solid-State Sensors, Actuators and Microsystems. 619--622.Google Scholar
- S. Roy, B. B. Bhattacharya, P. P. Chakrabarti, and K. 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
- S. Roy, B. B. Bhattacharya, and K. Chakrabarty. 2010. Optimization of dilution and mixing of biochemical samples using digital microfluidic biochips. IEEE Trans. CAD 29, 11, 1696--1708. Google ScholarDigital Library
- S. Roy, B. B. Bhattacharya, and K. Chakrabarty. 2011a. Waste-aware dilution and mixing of biochemical samples with digital microfluidic biochips. In Proceedings of the Conference and Exhibition on Design, Automation and Test in Europe. 1059--1064.Google Scholar
- S. Roy, B. B. Bhattacharya, S. Ghoshal, and K. Chakrabarty. 2013a. High-throughput dilution engine for sample preparation on digital microfluidic biochips. IET Comput. Digital Tech.Google Scholar
- S. Roy, B. B. Bhattacharya, S. Ghoshal, and K. Chakrabarty. 2013b. On-chip dilution from multiple concentrations of a sample fluid using digital microfluidics. In Proceedings of the International Symposium on VLSI Design and Test. 1--9.Google Scholar
- S. Roy, P. P. Chakrabarti, S. Kumar, B. B. Bhattacharya, and K. Chakrabarty. 2013c. Routing-aware resource allocation for mixture preparation in digital microfluidic biochips. In Proceedings of the International Symposium on VLSI. 1--6.Google Scholar
- R. Sista, Z. Hua, P. Thwar, A. Sudarsan, V. Srinivasan, A. E. Eckhardt, M. G. Pollack, and V. K. Pamula. 2008. Development of a digital microfluidic platform for point of care testing. Lab-on-a-Chip 8, 12, 2091--2104.Google ScholarCross Ref
- S. Sugiura, K. Hattori, and T. Kanamori. 2010. Microfluidic serial dilution cell-based assay for analyzing drug dose response over a wide concentration range. Anal. Chem. 82, 19, 8278--8282.Google ScholarCross Ref
- J. Talsma. 2013. Drug Shortages Still at Crisis Levels. http://drugtopics.modernmedicine.com/drug-topics/news/drug-shortages-still-crisis-levels?page=full.Google Scholar
- H. Y. Tan, W. K. Loke, Y. T. Tan, and N.-T. Nguyen. 2008. A lab-on-a-chip for detection of nerve agent sarin in blood. Lab-on-a-Chip 8, 6, 885--891.Google ScholarCross Ref
- W. Thies, J. P. Urbanski, T. Thorsen, and S. Amarasinghe. 2008. Abstraction layers for scalable microfluidic biocomputing. Natural Computing 7, 2, 255--275. Google ScholarDigital Library
- C. L. Ventola. 2011. The drug shortage crisis in the United States: Causes, impact, and management strategies. Pharm. Therapeutics 36, 11, 740--742, 749--757.Google Scholar
- H. A. Yusuf, S. J. Baldock, P. R. Fielden, N. J. Goddard, S. Mohr, and B. J. T. Brown. 2009. Systematic linearisation of a microfluidic gradient network with unequal solution inlet viscosities demonstrated using glycerol. Microfluid. Nanofluid. 8, 5, 587--598.Google ScholarCross Ref
Index Terms
- Theory and analysis of generalized mixing and dilution of biochemical fluids using digital microfluidic biochips
Recommendations
Architectural Design of Flow-Based Microfluidic Biochips for Multi-Target Dilution of Biochemical Fluids
Microfluidic technologies enable replacement of time-consuming and complex steps of biochemical laboratory protocols with a tiny chip. Sample preparation (i.e., dilution or mixing of fluids) is one of the primary tasks of any bioprotocol. In real-life ...
Layout-Aware Mixture Preparation of Biochemical Fluids on Application-Specific Digital Microfluidic Biochips
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 ...
Multiple Dilution Sample Preparation Using Digital Microfluidic Biochips
ISED '12: Proceedings of the 2012 International Symposium on Electronic System DesignDigital microfluidic (DMF) biochips offer a versatile platform for implementing several laboratory based biochemical protocols. These tiny chips can electrically control the dynamics of nanoliter volume of discrete fluid droplets on an electrode array ...
Comments