請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/42751
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 張耀文(Yao-Wen Chang) | |
dc.contributor.author | Hsin-Lun Kao | en |
dc.contributor.author | 高新綸 | zh_TW |
dc.date.accessioned | 2021-06-15T01:21:57Z | - |
dc.date.available | 2012-07-29 | |
dc.date.copyright | 2009-07-29 | |
dc.date.issued | 2009 | |
dc.date.submitted | 2009-07-23 | |
dc.identifier.citation | [1] K. F. Bohringer. Modeling and controlling parallel tasks in droplet-based microfluidic systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25(2):334-343, February 2006.
[2] K. Chakrabarty and R. Thewes. Guest editors' introduction: Biochips and integrated biosensor platforms. IEEE Design & Test of Computers, 24(1):8-9,Jan.-Feb. 2007. [3] H.-A. Choi, K. Nakajima, and C. S. Rim. Graph bipartization and via minimization. SIAM Journal on Discrete Mathematics, 2(1):38-47, February 1989. [4] V. Deolalikar, M. R. Mesarina, J. Recker, and S. Pradhan. Perturbative time and frequency allocations for RFID reader networks. In Proceedings of Workshop on Emerging Directions in Embedded and Ubiquitous Computing, pages 392-402, Secaucus, NJ, USA, August 2006. [5] J. Ding, K. Chakrabarty, and R. B. Fair. Reconfigurable microfluidic system architecture based on two-dimensional electrowetting arrays. In Proceedings of International Conference on Modeling and Simulation of Microsystems, pages 181-185, Danville, CA, USA, March 2001. [6] R. B. Fair, V. Srinivasan, H. Ren, P. Paik, V. K. Pamula, and M. G. Pollack. Electrowetting-based on-chip sample processing for integrated microfluidics. In 5051 Technical Digest of IEEE International Electron Devices Meeting, pages 32.5.1-32.5.4, Washington D.C., USA, December 2003. [7] S.-K. Fan, C. Hashi, and C.-J. Kim. Manipulation of multiple droplets on NxM grid by cross-reference EWOD driving scheme and pressure-contact packaging. In Proceedings of the IEEE Conference on Micro Electro Mechanical Systems, pages 694-697, Los Angles, CA, USA, January 2003. [8] B. S. Gallardo, V. K. Gupta, F. D. Eagerton, L. I. Jong, V. S. Craig, R. R. Shah, and N. L. Abbott. Electrochemical principles for active control of liquids on submillimeter scales. Science, 283(5398):57-60, January 1999. [9] J. Gong and C.-J. Kim. Direct-referencing two-dimensional-array digital microfluidics using multilayer printed circuit board. Journal of Micro Electro Mechanical Systems, 17(2):257-264, April 2008. [10] E. J. Griffith, S. Akella, and M. K. Goldberg. Performance characterization of a reconfigurable plannar-array digital microfluidic system. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25(2):345-357, February 2006. [11] T. B. Jones, M. Gunji, M. Washizu, and M. J. Feldman. Dielectrophoretic liquid actuation and nanodroplet formation. Journal of Applied Physics, 89(2):1441-1448, January 2001. [12] A. B. Kahng, S. Vaya, and A. Zelikovsky. New graph bipartizations for double-exposure, bright field alternating phase-shift mask layout. In Proceedings of the Asia South Pacific Design Automation Conference, pages 133-138, Yokohama, Japan, January 2001.52 [13] P. Paik, V. K. Pamula, and R. B. Fair. Rapid droplet mixers for digital microfluidic systems. Lab on a Chip, 3(4):253{259, September 2003. [14] R. Pal, M. Yang, R. Lin, B. N. Johnson, N. Srivastava, S. Z. Razzacki, K. J. Chomistek, D. C. Heldsinger, R. M. Haque, V. M. Ugaz, P. K. Thwar, Z. Chen,K. Alfano, M. B. Yim, M. Krishnan, A. O. Fuller, R. G. Larson, D. T. Burke, and M. A. Burns. An integrated micro°uidic device for in°uenza and other genetic analyses. Lab on a Chip, 5(10):1024-1032, July 2005. [15] A. Panconesi and M. Sozio. Fast hare: A fast heuristic for single individual SNP haplotype reconstruction. In Proceedings of International Workshop on Algorithms in Bioinformatics, pages 266-277, October 2004. [16] B. A. Reed, K. Smith, and A. Vetta. Finding odd cycle transversals. Operation Research Letters, 32(4):299-301, January 2004. [17] R. Rizzi, V. Bafna, S. Istrail, and G. Lancia. Practical algorithms and fixed-parameter tractability for the single individual SNP haplotyping problem. In Proceedings of the International Workshop on Algorithms in Bioinformatics, pages 29-43, September 2002. [18] C. Situma, M. Hashimoto, and S. A. Soper. Merging microfluidics with microarray-based bioassays. Biomolecular Engineering, 23(5):213-231, 2006. [19] F. Su and K. Chakrabarty. Architectural-level synthesis of digital microfluidics-based biochips. In Proceedings of ACM/IEEE International Conference on Computer-Aided Design, pages 223-228, San Jose, CA, USA, November 2004. [20] F. Su and K. Chakrabarty. Uni‾ed high-level synthesis and module placement for defect-tolerant microfluidic biochips. In Proceedings of ACM/IEEE Design Automation Conference, pages 825-830, Anaheim, CA, USA, June 2005.53 [21] F. Su, W. Hwang, and K. Chakrabarty. Droplet routing in the synthesis of digital microfluidic biochips. In Proceedings of ACM/IEEE Design, Automation, and Test in Europe, pages 323-328, Munich, Germany, March 2006. [22] A. Torkkeli, J. Saarilahti, A. Haara, H. Harma, T. Soukka, and P. Tolonen. Electrostatic transportation of water droplets on superhydrophobic surfaces. In Proceedings of IEEE International Conference on Micro Electro Mechanical Systems, pages 475-478, Interlaken, Switzerland, January 2001. [23] T. Xu and K. Chakrabarty. A cross-referencing-based droplet manipulation method for high-throughput and pin-constrained digital micro°uidic arrays. In Proceedings of ACM/IEEE Design, Automation, and Test in Europe, pages 552-557, Nice, France, April 2007. [24] T. Xu and K. Chakrabarty. Droplet-trace-based array partitioning and a pin assignment algorithm for the automated design of digital microfluidic biochips. In Proceedings of IEEE/ACM International Conference on Hardware/Software Codesign and System Synthesis, pages 112-117, Atlanta, GA, USA, October 2007. [25] T. Xu and K. Chakrabarty. Broadcast electrode-addressing for pin-constrained multi-functional digital microfluidic biochips. In Proceedings of ACM/IEEE Design Automation Conference, pages 173-178, Anaheim, CA, USA, June 2008. [26] T. Xu and K. Chakrabarty. A droplet-manipulation method for achieving high-throughput in cross-referencing-based digital micro°uidic biochips. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 27(11):1905-1917, November 2008. [27] T. Xu, K. Chakrabarty, and V. K. Pamula. Design and optimization of a digital micro°uidic biochip for protein crystallization. In Proceedings of ACM/IEEE International Conference on Computer-Aided Design, pages 297-301, San Jose, CA, USA, November 2008. [28] M. Yannakakis. Node-and edge-deletion NP-complete problems. In Proceedings of ACM Symposium on Theory of Computing, pages 253-264, San Diego, CA, USA, May 1978. [29] P.-H. Yuh, S. S. Sapatnekar, C.-L. Yang, and Y.-W. Chang. A progressive-ILP based routing algorithm for cross-referencing biochips. In Proceedings of ACM/IEEE Design Automation Conference, pages 284-289, Anaheim, CA, USA, June 2008. [30] P.-H. Yuh, C.-L. Yang, and Y.-W. Chang. Temporal floorplanning using the T-tree formulation. In Proceedings of ACM/IEEE International Conference on Computer-Aided Design, pages 300{305, San Jose, CA, USA, November 2004. [31] P.-H. Yuh, C.-L. Yang, and Y.-W. Chang. Placement of digital microfluidic biochips using the T-tree formulation. In Proceedings of ACM/IEEE Design Automation Conference, pages 931-934, San Francisco, CA, USA, July 2006. [32] P.-H. Yuh, C.-L. Yang, and Y.-W. Chang. BioRoute: A network-flow based routing algorithm for digital microfluidic biochips. In Proceedings of ACM/IEEE International Conference on Computer-Aided Design, pages 447-452, San Jose, CA, USA, November 2007. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/42751 | - |
dc.description.abstract | 由於生物微機電系統(bio-MEMS)的迅速發展,數位微流體生物晶片(digital microfluidic biochips)的規模和設計的複雜性,預計在不久的將來會有爆炸性的成長。因此電腦輔助設計強有力的支持,將在生物晶片的未來發展中扮演重要的角色。而在數位微流體生物晶片的多層設計階段中,液滴繞線是一項關鍵的挑戰。繞線必須安排每一個液滴的運動軌跡和考量其間的時間順序,因此具有極高的複雜性且對生物晶片性能具有重大的影響。在此篇論文中,我們提出了第一個交錯參考(cross-referencing)微流體晶片上的統合液滴操作演算法,能夠同時在液滴混合和液滴澆線問題上作最佳化處理。此演算法以創新的元件活化圖(cell-activation graph)為基礎,可以在真實世界的生物晶片上同時執行液滴行動和液滴澆線,並且保證其生物反應的正確性。此外,演算法比之最先進的繞線演算法只有一半的運行時間並進一步提高繞線性能。在規模更大、複雜度更高的測試中,我們的繞線演算法更展現出高度的可擴展性和可繞性。 | zh_TW |
dc.description.abstract | From rapid development in bio-MEMS, the scale of a digital microfluidic biochip and the design complexity are expected to explode in the near future, thus requiring strong CAD support as VLSI industry has taken for granted. Among multiple synthesis stages of a digital microfluidic biochip, droplet routing which schedules the droplet movements in a time-multiplexed manner is a critical challenge due to the complex control constraints on different biochip architectures. We propose the first unified droplet manipulation algorithm to cope with the droplet manipulation problem on cross-referencing microfluidic biochips. Based on a novel graph model called cell-activation graph (CAG), the proposed method simultaneously performs droplet operations and droplet routing and guarantee the functional correctness of bioassays. It further improves the routing performance by 15% with only half of the runtime as compared with the state-of-the-art router. Experimental results on real-life benchmarks show that our algorithm achieves higher routability and scalability than previous droplet routing methods. | en |
dc.description.provenance | Made available in DSpace on 2021-06-15T01:21:57Z (GMT). No. of bitstreams: 1 ntu-98-R96921031-1.pdf: 3176818 bytes, checksum: 5461925e972a2135f1761bc9fbf857fa (MD5) Previous issue date: 2009 | en |
dc.description.tableofcontents | Acknowledgements . i
Abstract (Chinese) . ii Abstract . iii List of Figures . vii List of Tables . x Chapter 1. Introduction . 1 1.1 Microarrays . . 1 1.2 Microfluidic Biochips . . 2 1.2.1 Continuous-Flow Microfluidic Biochips . . 2 1.2.2 Digital Microfluidic Biochips . . 3 1.3 Previous Works on Droplet Routing . . 6 1.3.1 Graph-Based Routing . . 7 1.3.2 ILP-Based Routing . . 8 1.4 Unified Droplet Manipulation . . 9 1.5 Contributions . . 11 1.6 Thesis Organization . . 12 Chapter 2. Problem Formulation . 13 Chapter 3. Algorithm . 20 3.1 The Graph-Based Algorithm Overview . . 20 3.2 Cell-Activation Graph Definition . . 22 3.3 CAG Construction Procedure . . 22 v3.3.1 Properties of the CAG . . 26 3.3.2 Droplet Reachability Estimation . . 28 3.4 CAG Improvement . . 29 3.4.1 Dynamic-CAG . . 29 3.4.2 Routability Enhancement . . 32 3.5 Graph Bipartization Algorithm . . 34 3.5.1 Optimality . . 36 3.6 Complexity Analysis . . 37 3.6.1 Numbers of Elements in the CAG . . 37 3.6.2 Time Complexity . . 38 Chapter 4. Experimental Results . 41 Chapter 5. Conclusions . 48 Bibliography . 50 | |
dc.language.iso | en | |
dc.title | 交錯參考微流體晶片的統合液滴操作演算法 | zh_TW |
dc.title | A Unified Droplet Manipulation Algorithm on Cross-Referencing Microfluidic Biochips | en |
dc.type | Thesis | |
dc.date.schoolyear | 97-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 江介宏(Jie-Hong Roland Jiang),陳宏明(Hung-Ming Chen),麥偉基(Wai-Kei Mak) | |
dc.subject.keyword | 數位微流體生物晶片,交錯參考生物晶片,液滴繞線,液滴行動,圖形二分化, | zh_TW |
dc.subject.keyword | digital microfluidic biochips,cross-referencing biochips,droplet routing,droplet operations,graph bipartization, | en |
dc.relation.page | 54 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2009-07-24 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-98-1.pdf 目前未授權公開取用 | 3.1 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。