跳到主要內容

臺灣博碩士論文加值系統

(44.200.168.16) 您好!臺灣時間:2023/03/21 14:50
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:李育瑛
研究生(外文):Li, Yu-Ying
論文名稱:針對數位微流體生物晶片於時間限制下之反應物最小化樣本製備技術
論文名稱(外文):Time-Constrained Sample Preparation Algorithm for Reactant Minimization on DMFBs
指導教授:黃俊達黃俊達引用關係
指導教授(外文):Huang, Juinn-Dar
口試委員:何宗易劉建男黃俊達
口試委員(外文):Ho, Tsung-YiLiu, Chien-NanHuang, Juinn-Dar
口試日期:2018-08-30
學位類別:碩士
校院名稱:國立交通大學
系所名稱:電子研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2018
畢業學年度:107
語文別:英文
論文頁數:55
中文關鍵詞:數位微流體生物晶片樣本製備技術實驗室整合晶片時間限制反應物最小化
外文關鍵詞:digital microfluidic biochipsample preparationlab-on-a-chiptime-constrainedreactant minimization
相關次數:
  • 被引用被引用:0
  • 點閱點閱:148
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
樣本製備程序(sample preparation)乃各種生化反應中不可或缺的步驟之一。在過去幾年中已經有許多研究結果發表,用以解決在數位微流體生物晶片(digital microfluidic biochips, DMFBs)上反應物、稀釋/混合反應的次數或產生的廢液最小化等問題。涉及減少反應物的相關演算法基本上都需要付出額外的稀釋/混合反應的次數,但是在大部分關注反應物最小化的演算法中很少會將製備時間納入考量。本篇論文提出的演算法,緩衝液珠插入和位移演算法,簡稱BISA,是第一個針對數位微流體生物晶片於時間限制下之反應物最小化的樣本製備技術演算法。此演算法使用緩衝液珠插入和緩衝液珠插入位移兩項操作,藉由液珠擺放的位置來修改製備程序,達成在不違背時間限制的前提下將反應物使用量最小化。實驗結果顯示,BISA在反應物使用量方面可以比最快的演算法BS平均減少33%。當與用量少的演算法REMIA比較時,我們可以使用更少的(5%)稀釋/混合反應的次數在相同的反應物使用量下完成樣本製備程序。實際上,這是反應物使用量和稀釋/混合反應的次數之間取捨(trade-off)的結果。因此,我們的演算法是目前針對數位微流體生物晶片於時間限制下將反應物最小化樣本製備技術的最佳方案。
Sample preparation is one of essential steps in most biochemical reactions. Many studies have been published during the past few years for tackling down the problem of reactant, operation, or waste minimization on digital microfluidic biochips (DMFBs). However, those algorithms focusing on reactant minimization also incur numerous extra mixing operations at the same time. That is, most reactant minimization algorithms do not consider the operation count issue. In this work, we propose a Buffer Insertion and Shifting Algorithm (BISA), which is the first time-constrained method for sample preparation on DMFBs. The proposed algorithm performs both buffer insertion and buffer shifting operations to manipulate the dilution process for reactant minimization under the given time constraint. Experimental results demonstrate that BISA can reduce the reactant consumption by 33% over the fastest known algorithm, BS. When compared against one of the best reactant minimization algorithms, REMIA, BISA can reduce the number of mixing operations by 5% while keeping the reactant consumption unchanged. As a matter of fact, BISA can perform trade-offs between reactant consumption and mixing operation count. Hence, to the best of our knowledge, BISA is currently the best method for time-constrained reactant minimization sample preparation on DMFBs.
摘 要 i
Abstract ii
誌 謝 iii
Contents iv
List of Tables vi
List of Figures vii
Chapter 1 Introduction 1
Chapter 2 Preliminaries 6
2.1 Sample Preparation 6
2.2 Mixing Models 8
2.3 Dilution Graph 10
2.4 Exponential and Interpolated Dilution 12
Chapter 3 Previous Works 16
3.1 Bit-scanning Method 17
3.2 REMIA 18
Chapter 4 Problem Description 20
4.1 Motivation 20
4.2 Problem Formulation 24
Chapter 5 Proposed Algorithm 25
5.1 Algorithm Overview 25
5.2 Single Buffer insertion 26
5.3 Single Buffer shifting 29
5.4 Multi-buffer manipulation 33
5.5 Total Operations Calculation 39
Chapter 6 Experimental Results 40
6.1 Environment Setup 40
6.2 Results and Analyses 40
6.2.1 BISA against previous works 41
6.2.2 Trade-off between reactant usage and operations 42
6.2.3 Greedy against exhausted search 48
Chapter 7 Conclusion 50
References 51
[1] R. Daw and J. Finkelstein, “Insight: Lab on a chip,” Nature, vol. 442, no. 7101, pp. 367-418, Jul. 2006.
[2] S. J. Lee and S. Y. Lee, “Micro total analysis system (μ-TAS) in biotechnology,” Appl. Microbiol. Biotechnol., vol. 64, no. 3, pp. 289–299, Jan. 2004.
[3] A. Arora, G. Simone, G. B. Salieb-Beugelaar, J. T. Kim, and A. Manz, “Latest developments in micro total analysis systems,” Analytical Chemistry., vol. 82, no. 12, pp. 4830-4847, 2010.
[4] D. Mark, S. Haeberle, G. Roth, F. von Stetten, and R. Zengerle, “Microfluidic lab-on-a-chip platforms: requirements, characteristics and applications,” Chem. Soc. Rev., vol. 39, no. 3, pp. 1153–1182, Jan. 2010.
[5] M. G. Pollack, R. B. Fair, and A. D. Shenderov, “Electrowetting-based actuation of liquid droplets for microfludic applications,” Applied Physics Letters, vol. 77, no. 11, pp. 1725-1726, Sep. 2000.
[6] P. Paik, V. K. Pamula, and R. B. Fair, “Rapid droplet mixers for digital microfludic systems,” Lab on a Chip, vol. 3, no. 4, pp. 253-259, Sep. 2003.
[7] V. Srinivasan, V. Pamula, and R. Fair, “An integrated digital microfluidic lab-on-a-chip for clinical diagnostics on human physiological fluids,” Lab on a Chip, vol. 4 no. 4, pp. 310-315, May 2004.
[8] T.-Y. Ho, K. Chakrabarty, and P. Pop, “Digital microfludic biochips: recent research and emerging challenges,” in Proceeding of IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis, 2011, pp. 335-343.
[9] T.-Y. Ho, J. Zeng, and K. Chakrabarty, “Digital microfluidic biochips: a vision for functional diversity and more than Moore,” in Proceeding of IEEE/ACM International Conference on Computer-Aided Design, 2010, pp. 578–585.
[10] M. Alistar, E. Maftei, P. Pop, and J. Madsen, “Synthesis of biochemical applications on digital microfluidic biochips with operation variability,” in Proceeding of Symposium on Design, Test, Integration and Packaging of MEMS/MOEMS, 2010, pp. 350–357.
[11] L. Luo and S. Akella, “Optimal scheduling of biochemical analyses on digital microfluidic systems,” IEEE Transactions on Automation Science and Engineering, vol. 8, no. 1, pp. 216–227, Jan. 2011.
[12] P.-H. Yuh, C.-L. Yang, and Y.-W. Chang, “Placement of defect-tolerant digital microfluidic biochips using the T-tree formulation,” ACM Journal on Emerging Technologies in Computing Systems, vol. 3, no. 3, pp. 13:1–13:32, Nov. 2007.
[13] Z. Xiao and E. F. Y. Young, “Placement and routing for cross-referencing digital microfluidic biochips,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 30, no. 7, pp. 1000–1010, Jul. 2011.
[14] M. Cho and D. Z. Pan, “A high-performance droplet routing algorithm for digital microfluidic biochips,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 10, pp. 1714–1724, Oct. 2008.
[15] Y. Zhao and K. Chakrabarty, “Co-optimization of droplet routing and pin assignment in disposable digital microfluidic biochips,” in Proceeding of ACM International Symposium on Physical Design, 2011, pp. 69–76.
[16] C.-Y. Lin and Y.-W. Chang, “Cross-contamination aware design methodology for pin-constrained digital microfluidic biochips,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 30, no. 6, pp. 817–828, Jun. 2011.
[17] T.-W. Huang, S.-Y. Yeh, and T.-Y. Ho, “A network-flow based pin-count aware routing algorithm for broadcast-addressing EWOD chips,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 30, no. 12, pp. 1786–1799, Dec. 2011.
[18] P. Roy, H. Rahaman, R. Bhattacharya, and P. Dasgupta, “A best path selection based parallel router for DMFBs,” in Proceeding of IEEE International Symposium on Electronic System Design, 2011, pp. 176–181.
[19] D. Mitra, S. Ghoshal, H. Rahaman, K. Chakrabarty, and B. B. Bhattacharya, “On residue removal in digital microfluidic biochips,” in Proceeding of ACM Great Lakes Symposium on VLSI, 2011, pp. 391–394.
[20] K. Chakrabarty, “Design automation and test solutions for digital microfluidic biochips,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 57, no. 1, pp. 4–17, Jan. 2010.
[21] S. Saha, A. Chakraborti, and S. Roy, “An efficient single-fault detection technique for micro-fluidic based biochips,” in Proceeding of IEEE International Conference on Advances in Computer Engineering, 2010, pp. 10–14.
[22] G. M. Walker, N. Monteiro-Riviere, J. Rouse, and A. T. O'Neill, “A linear dilution microfluidic device for cytotoxicity assays,” Lab on a Chip, vol. 7, no. 2, pp. 226–232, Oct. 2007.
[23] H. Ren, V. Srinivasan, and R. B. Fair, “Design and testing of an interpolating mixing architecture for electrowetting-based droplet-on-chip chemical dilution,” in Proceeding of IEEE International Conference on Solid-State Sensors, Actuators and Microsystems (TRANSDUCERS), 2003, pp. 619–622.
[24] H. Moon, A. R. Wheeler, R. L. Garrell, J. A. Loo, and C. J. Kim, “An integrated digital microfluidic chip for multiplexed proteomic sample preparation and analysis by MALDI-MS,” Lab on a Chip, vol. 6, no. 9, pp. 1213–1219, Jul. 2006.
[25] K. A. Kalanick, Phlebotomy Technician Specialist, 2nd Edition. Delmar Cengage Learning, 2011.
[26] J. M. Butler, Fundamentals of Forensic DNA Typing.Academic Press, 2009.
[27] E. J. Griffith, S. Akella, and M. K. Goldberg, “Performance characterization of a reconfigurable planar-array digital microfluidic system,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 2, pp. 345–357, Feb. 2006.
[28] T. Xu, V. K. Pamula, and K. Chakrabarty, “Automated, accurate, and inexpensive solution-preparation on a digital microfluidic biochip,” in Proceeding of IEEE Biomedical Circuits and Systems Conference, 2008, pp. 301–304.
[29] W. Thies, J. P. Urbanski, T. Thorsen, and S. Amarasinghe, “Abstraction layers for scalable microfluidic biocomputing,” Natural Computing, vol. 7, no. 2, pp. 255–275, May 2008.
[30] S. Roy, B. B. Bhattacharya, and K. Chakrabarty, “Optimization of dilution and mixing of biochemical samples using digital microfluidic biochips,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 29, no. 11, pp. 1696–1708, Nov. 2010.
[31] S. Roy, B. B. Bhattacharya, and K. Chakrabarty, “Waste-aware dilution and mixing of biochemical samples with digital microfluidic biochips,” in Proceeding of IEEE/ACM Design, Automation & Test in Europe Conference & Exhibition, 2011, pp. 1059–1064.
[32] Y.-L. Hsieh, T.-Y. Ho, and K. Chakrabarty, “On-chip biochemical sample preparation using digital microfluidics,” in Proceeding of IEEE Biomedical Circuits and Systems Conference, 2011, pp. 297–300.
[33] S. Roy, B. B. Bhattacharya, P. P. Chakrabarti, and K. Chakrabarty, “Layout-aware solution preparation for biochemical analysis on a digital microfluidic biochip,” in Proceeding of IEEE International Conference on VLSI Design, 2011, pp. 171–176.
[34] J.-D. Huang, C.-H. Liu, and T.-W. Chiang, “Reactant minimization during sample preparation on digital microfluidic biochips using skewed mixing trees,” in Proceeding of IEEE/ACM International Conference on Computer-Aided Design, 2012.
[35] Y.-L. Hsieh, T.-Y. Ho, and K. Chakrabarty, “A reagent-saving mixing algorithm for preparing multiple-target biochemical samples using digital microfluidics,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 31, no. 11, pp. 1656–1669, Nov. 2012.
[36] J.-D. Huang, C.-H. Liu, and H.-S. Lin, “Reactant and waste minimization in multitarget sample preparation on digital microfluidic biochips,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 32, no. 10, pp. 1484–1494, Oct. 2013.
[37] C.-H. Liu, H.-H. Chang, T.-C. Liang, and J.-D. Huang, “Sample preparation for many-reactant bioassay on DMFBs using common dilution operation sharing,” in Proc. IEEE/ACM Int. Conf. Comput.-Aided Design, 2013, pp. 615–621.
[38] D. Mitra, S. Roy, K. Chakrabarty, and B. B. Bhattacharya, “On-chip sample preparation with multiple dilutions using digital microfluidics,” in Proc. IEEE Comput. Soc. Annu. Symp. VLSI, 2012, pp. 314–319.
[39] C.-H. Liu, T.-W. Chiang, and J.-D. Huang, “Reactant minimization in sample preparation on digital microfluidic biochips,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 34, no. 9, pp. 1429–1440, Sep. 2015.
[40] Y.-L. Hsieh, T.-Y. Ho, and K. Chakrabarty, “Biochip synthesis and dynamic error recovery for sample preparation using digital microfluidics,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 33, no. 2, pp. 183–196, Feb. 2014.
[41] D. A. Huffman, “A method for the construction of minimum redundancy codes,” in Proceeding of the Institute of Radio Engineers, 1952, pp. 1098–1101.
電子全文 電子全文(網際網路公開日期:20230903)
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊