於微電極點陣列型數位微流體生物晶片中應用分數拆解法實現反應物用量最小化之樣本製備技術

Sample Preparation for Reactant Minimization on MEDA-Based DMFBs using Partial Fraction Decomposition

温仁弘(Ren-Hong Wen)

指導教授 ： 黃俊達

國立交通大學/電機學院/電子工程系所/碩士(2019年)

摘要

樣本製備程序(sample preparation)是各種生化反應中相當重要的一個環節，目地是將原始生物樣本或反應試劑依照此程序進行混合或是調配，以獲得所需要的目標濃度(target concentration)。近年來，有眾多針對樣本製備程序所發展的演算法陸陸續續被提出，其中最多人重視的是反應物使用量的最佳化(reactant minimization)，而這些演算法也都有不錯的表現，但他們大多採取適用於一般數位微流體生物晶片上的(1:1)混合模型。然而生物晶片架構持續演進，新一代以微電極點陣列(MEDA)為基礎之數位微流體生物晶片(DMFB)強勢誕生，而這個新架構提供了不同於以往的(m:n)混合模型。研究人員開始發展針對新混合模型的樣本製備程序，目標其中當然也包含了反應物使用量的最小化。但隨著混合模型的增加，可行解之數量呈指數爆炸上升，使得必須在特定限制範圍下才能執行完畢，導致丟失好的解決方案或甚至無法達成。而在本篇論文中，我們提出了一個目標濃度精準度可調及其表示分數的選擇及拆分機制，可以系統化的產生所有可行解，另外針對產生出的可行解計算增益以判斷其優劣，以篩選出可控數量的較佳解，最後再搭配液珠共用機制以達成反應物使用量最小化。實驗結果顯示，使用我們的演算法在不同目標濃度精準度要求下皆能保證得到可行解，且無論目標液珠所需的數量多寡，我們的演算法在反應物使用量最小化上明顯勝過既有演算法，最多可節省50.2%，且產生一組解最多亦僅需幾分鐘。實驗結果顯示我們所開發的新演算法和現有演算法相比，不但可靠、結果優異且具有效率。

關鍵字

樣本製備 ； 微電極點陣列 ； 數位微流體生物晶片 ； 分數拆解法

並列摘要

Sample preparation, regarded as one of the significant processes in most biochemical reactions, is carried out via mixing biological samples or reactants to produce a solution with the given target concentration. In recent years, many sample preparation methods have been proposed, in which reactant minimization is one of the common optimization objectives. A greater part of these deal with sample preparation under the (1:1) mixing model in digital microfluidic biochips (DMFBs) and perform quite well. However, Micro-Electronic-Dot-Array(MEDA)-based DMFBs with the (m:n) mixing model has been announced. Some reactant minimization algorithms utilizing this new mixing model have already been proposed. Under this new mixing model, the number of feasible solutions raises exponentially; that is, without special care, an algorithm may not be able to find good solutions in a reasonable runtime or even cannot finish at all. In this thesis, we propose a new sample preparation algorithm for reactant minimization on MEDA-based DMFBs. It first generates a set of all feasible fractions to represent the given target concentration. Then, a set of candidate solutions are derived through partial fraction decomposition. A gain of every candidate solution is further calculated. Our algorithm merely preserves a limited number of candidate solutions with highest gains throughout the process to avoid runtime explosion. Finally, droplet sharing is performed for further reactant minimization. Experimental results show that our method guarantees to produce a solution for a given target concentration just in few minutes. Moreover, it outperforms all existing methods in terms of reactant minimization and the reduction is up to 50.2%. Therefore, it is convincing that the proposed algorithm is currently the most promising solution for reactant minimization in sample preparation on MEDA-based DMFBs.

並列關鍵字

Sample Preparation ； Reactant Minimization ； MEDA ； DMFB ； Partial Fraction Decomposition

參考文獻

[1] P. Paik et al., “Rapid droplet mixers for digital microuidic systems, ” Lab on a Chip, vol. 3, no. 4, pp. 253–259, 2003.

[2] W. Thies, J. P. Urbanski, T. Thorsen, and S. Amarasinghe, “Abstraction layers for scalable microuidic biocomputing, ” Natural Computing, vol. 7, no. 2, pp. 255–275, 2008.

[3] J.-D. Huang, C.-H. Liu, and T.-W. Chiang, “Reactant min- imization during sample preparation on digital microuidic biochips using skewed mixing trees, ” in Proc. ICCAD, pp. 377–383, 2012.

[4] C.-H. Liu et al., “Sample preparation for many-reactant bioassay on dmfbs using common dilution operation sharing, ” in Proc. ICCAD, pp. 615–621, 2013.

[5] G. Wang, D. Teng, and S.-K. Fan, “Digital microuidic operations on micro-electrode dot array architecture, ” IET Nanobiotechnology, vol. 5, no. 4, pp. 152–160, 2011.