{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T15:11:07Z","timestamp":1784646667804,"version":"3.55.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,9,13]],"date-time":"2021-09-13T00:00:00Z","timestamp":1631491200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Linz Institute of Technology"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2022,1,31]]},"abstract":"<jats:p>\n            Microfluidic lab-on-chips offer promising technology for the automation of various biochemical laboratory protocols on a minuscule chip. Sample preparation (SP) is an essential part of any biochemical experiments, which aims to produce dilution of a sample or a mixture of multiple reagents in a certain ratio. One major objective in this area is to prepare dilutions of a given fluid with different concentration factors, each with certain volume, which is referred to as the demand-driven multiple-target (DDMT) generation problem. SP with microfluidic biochips requires proper sequencing of mix-split steps on fluid volumes and needs storage units to save intermediate fluids while producing the desired target ratio. The performance of SP depends on the underlying mixing algorithm and the availability of on-chip storage, and the latter is often limited by the constraints imposed during physical design. Since DDMT involves several target ratios, solving it under storage constraints becomes even harder. Furthermore, reduction of mix-split steps is desirable from the viewpoint of accuracy of SP, as every such step is a potential source of volumetric split error. In this article, we propose a storage-aware DDMT algorithm that reduces the number of mix-split operations on a digital microfluidic lab-on-chip. We also present the layout of the biochip with\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            -storage cells and their allocation technique for\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            . Simulation results reveal the superiority of the proposed method compared to the state-of-the-art multi-target SP algorithms.\n          <\/jats:p>","DOI":"10.1145\/3474392","type":"journal-article","created":{"date-parts":[[2021,9,13]],"date-time":"2021-09-13T22:50:18Z","timestamp":1631573418000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Demand-Driven Multi-Target Sample Preparation on Resource-Constrained Digital Microfluidic Biochips"],"prefix":"10.1145","volume":"27","author":[{"given":"Sudip","family":"Poddar","sequence":"first","affiliation":[{"name":"Institute for Integrated Circuits, Johannes Kepler University Linz, Linz, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sukanta","family":"Bhattacharjee","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Indian Institute of Technology Guwahati, Guwahati, West Bengal, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shao-Yun","family":"Fang","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, National Taiwan University of Science and Technology, Taipei, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tsung-Yi","family":"Ho","sequence":"additional","affiliation":[{"name":"Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"B. B.","family":"Bhattacharya","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Indian Institute ofTechnology Kharagpur, Kharagpur, West Bengal, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,9,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.vlsi.2018.01.002"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/jac\/48.suppl_1.5"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1049\/iet-cdt.2013.0053"},{"key":"e_1_2_1_4_1","unstructured":"S. Bhattacharjee B. B. Bhattacharya and K. Chakrabarty. 2019. Algorithms for Sample Preparation with Microfluidic Lab-on-Chip. River Publishers.  S. Bhattacharjee B. B. Bhattacharya and K. Chakrabarty. 2019. Algorithms for Sample Preparation with Microfluidic Lab-on-Chip. River Publishers."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2016.2597225"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2019.2907911"},{"key":"e_1_2_1_7_1","volume-title":"Retrieved","year":"2017","unstructured":"Bio-protocol. 2017 . Home Page . Retrieved August 10, 2020 from http:\/\/www.bio-protocol.org\/Default.aspx. Bio-protocol. 2017. Home Page. Retrieved August 10, 2020 from http:\/\/www.bio-protocol.org\/Default.aspx."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.talanta.2010.05.046"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"K. Chakrabarty and F. Su. 2007. Digital Microfluidic Biochips: Synthesis Testing and Reconfiguration Techniques. CRC Press Boca Raton FL.  K. Chakrabarty and F. Su. 2007. Digital Microfluidic Biochips: Synthesis Testing and Reconfiguration Techniques. CRC Press Boca Raton FL.","DOI":"10.1201\/9781420008302"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of DATE. 1525\u20131530","author":"Chen Z.","unstructured":"Z. Chen , X. Huang , W. Guo , B. Li , T. Ho , and U. Schlichtmann . 2019. Physical synthesis of flow-based microfluidic biochips considering distributed channel storage . In Proceedings of DATE. 1525\u20131530 . Z. Chen, X. Huang, W. Guo, B. Li, T. Ho, and U. Schlichtmann. 2019. Physical synthesis of flow-based microfluidic biochips considering distributed channel storage. In Proceedings of DATE. 1525\u20131530."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1039\/c2lc21204h"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/cbic.200700536"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2014.6742894"},{"key":"e_1_2_1_14_1","first-page":"5754","article-title":"Microfluidics-based lab-on-chip systems in DNA-based biosensing: An overview","volume":"11","author":"Dutse S. W.","year":"2011","unstructured":"S. W. Dutse and N. A. Yusof . 2011 . Microfluidics-based lab-on-chip systems in DNA-based biosensing: An overview . Lab Chip 11 , 6 (2011), 5754 \u2013 5768 . S. W. Dutse and N. A. Yusof. 2011. Microfluidics-based lab-on-chip systems in DNA-based biosensing: An overview. Lab Chip 11, 6 (2011), 5754\u20135768.","journal-title":"Lab Chip"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDT.2007.8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/VLSI-DAT.2019.8742025"},{"key":"e_1_2_1_17_1","first-page":"504","article-title":"A note on dilution systems","volume":"5","author":"Ingram G.","year":"1962","unstructured":"G. Ingram . 1962 . A note on dilution systems . Immunology 5 , 4 (1962), 504 \u2013 510 . G. Ingram. 1962. A note on dilution systems. Immunology 5, 4 (1962), 504\u2013510.","journal-title":"Immunology"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2012.2202396"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2013.2284010"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429384.2429464"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2013.2263035"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2021.3054689"},{"key":"e_1_2_1_23_1","volume-title":"Retrieved","author":"BM.","year":"2020","unstructured":"I BM. n.d. ILOG CPLEX Optimizer . Retrieved October 10, 2020 from http:\/\/www-01.ibm.com\/software\/integration\/optim ization\/cplex-optimizer\/. IBM. n.d. ILOG CPLEX Optimizer. Retrieved October 10, 2020 from http:\/\/www-01.ibm.com\/software\/integration\/optim ization\/cplex-optimizer\/."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1039\/c1lc20449a"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1097\/01.CCM.0000217961.75225.E9"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1039\/B813582G"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2019.2942002"},{"key":"e_1_2_1_28_1","first-page":"6050","article-title":"Adaptive droplet routing in digital microfluidic biochips using deep reinforcement learning","volume":"119","author":"Liang T.-C.","year":"2020","unstructured":"T.-C. Liang , Z. Zhong , Y. Bigdeli , T.-Y. Ho , K. Chakrabarty , and R. Fair . 2020 . Adaptive droplet routing in digital microfluidic biochips using deep reinforcement learning . In Proceedings of ICML , Vol. 119. 6050 \u2013 6060 . T.-C. Liang, Z. Zhong, Y. Bigdeli, T.-Y. Ho, K. Chakrabarty, and R. Fair. 2020. Adaptive droplet routing in digital microfluidic biochips using deep reinforcement learning. In Proceedings of ICML, Vol. 119. 6050\u20136060.","journal-title":"Proceedings of ICML"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2020.2994267"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/3130379.3130400"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3061639.3062334"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2010.2053201"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/541643"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1113324109"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2014.2323200"},{"key":"e_1_2_1_36_1","first-page":"758","article-title":"A combinatorial problem","volume":"49","author":"de Bruijn N.","year":"1946","unstructured":"N. de Bruijn . 1946 . A combinatorial problem . Proceedings of Koninklijke Nederlandse Akademie Van Wetenschappen Te Amsterdam 49 , 7 (1946), 758 \u2013 764 . N. de Bruijn. 1946. A combinatorial problem. Proceedings of Koninklijke Nederlandse Akademie Van Wetenschappen Te Amsterdam 49, 7 (1946), 758\u2013764.","journal-title":"Proceedings of Koninklijke Nederlandse Akademie Van Wetenschappen Te Amsterdam"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1038\/nrd3799"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1038\/nchem.1046"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1039\/B307628H"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414061"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2898999"},{"key":"e_1_2_1_42_1","unstructured":"S. Poddar R. Wille H. Rahaman and B. B. Bhattacharya. 2019. Dilution with digital microfluidic biochips: How unbalanced splits corrupt target-concentration. arXiv:1901.00353.  S. Poddar R. Wille H. Rahaman and B. B. Bhattacharya. 2019. Dilution with digital microfluidic biochips: How unbalanced splits corrupt target-concentration. arXiv:1901.00353."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2018.2864263"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2010.2061790"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of DATE. 1059\u20131064","author":"Roy S.","unstructured":"S. Roy , B. B. Bhattacharya , and K. Chakrabarty . 2011. Waste-aware dilution and mixing of biochemical samples with digital microfluidic biochips . In Proceedings of DATE. 1059\u20131064 . S. Roy, B. B. Bhattacharya, and K. Chakrabarty. 2011. Waste-aware dilution and mixing of biochemical samples with digital microfluidic biochips. In Proceedings of DATE. 1059\u20131064."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1049\/iet-cdt.2013.0060"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2593069.2593119"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.msec.2008.12.009"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10544-006-7706-6"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1186\/1746-4811-10-6"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aca.2015.12.008"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1021\/ja0354566"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1039\/b403280m"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-006-9032-6"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2017.2760628"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1039\/c1lc20123a"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.bios.2020.112291"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3474392","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3474392","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:49Z","timestamp":1750191529000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3474392"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,13]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1,31]]}},"alternative-id":["10.1145\/3474392"],"URL":"https:\/\/doi.org\/10.1145\/3474392","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,13]]},"assertion":[{"value":"2021-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}