考慮針腳減免及交叉污染迴避的數位微流體生物晶片設計方法

Design Methodology for Digital Microfluidic Biochips Considering Pin-Count Reduction and Cross-Contamination Avoidance

林宭宇(Cliff Chiung-Yu Lin)

指導教授 ： 張耀文

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2009年)

https://doi.org/10.6342/NTU.2009.01348

摘要

數位微流體生物晶片(digital microfluidic biochips) 新近興起為實驗室流程之熱門替代選擇。當實務應用在高度整合的生物晶片上傳輸及操作多種相異的液滴時，兩個關鍵的設計考量分別為針腳減免及交叉污染迴避。

關於針腳減免，既有文獻多採用後置加工的方式，基於初始擺置以及液滴傳輸路徑結果，對相容電極進行針腳共用；然而，此類共用演算法的品質無可避免地受限於其初始擺置以及液滴傳輸路徑結果。在本論文中我們針對針腳受限之生物晶片呈現了一個全面的設計流程用以解決針腳數量的問題。所提出的流程用以最佳化化驗所需時間以及所使用的針腳數目，共包含三個主要步驟：﹙一﹚考慮針腳數的階段指派、﹙二﹚考慮針腳數的設備指派、及﹙三﹚受導引的擺置、液滴傳輸及針腳指派。於階段指派及設備指派兩步驟，我們提供了整數線性規劃的模型以及有效的解空間限縮方式。實驗結果展示我的演算法的效率，且相較於既有文獻的方法有效減少了55-57%之針腳數。

關於交叉污染迴避，在此論文我們也提供了第一個針對針腳受限生物晶片上交叉污染問題的自動化設計流程。我們指認了交叉污染迴避所渴望的性質並對這此性質下所可能發生的交叉污染進行分類。為了解決這些類別的交叉污染，我們提出了﹙一﹚最小化傳輸路徑交錯之擺置、液滴傳輸演算法，及﹙二﹚清洗液滴的調度及傳輸方法。此方法只需一個額外控制針腳且對目前設計中不影響化驗所需時間。對於實務應用的實驗亦驗證了我們演算法的有效性及可擴性。

關鍵字

設計自動化 ； 數位微流體生物晶片 ； 針腳限制 ； 交叉污染 ； 演算法

並列摘要

Digital microfluidic biochips have emerged as a popular alternative for laboratory experiments. Pin-count reduction and cross-contamination avoidance are key design considerations for practical applications with different droplets being transported and manipulated on highly integrated biochips.

For pin-count reduction, most previous works approach the problem by postprocessing the placement and routing solutions to share compatible control signals; however, the quality of such sharing algorithms is inevitably limited by the placement and routing solutions. We present in this thesis a comprehensive pinconstrained biochip design flow that addresses the pin-count issue at all design stages. The proposed flow consists of three major stages: (1) pin-count aware stage assignment that partitions the reactions in the given bioassay into execution stages, (2) pin-count aware device assignment that determines a specific device used for each reaction, and (3) guided placement, routing, and pin assignment that utilize the pin-count saving properties from the stage and device assignments to optimize the assay time and pin count. For both the stage and device assignments, exact ILP formulations and effective solution-space reduction schemes are proposed to minimize the assay time and pin count. Experimental results show the efficiency of our algorithms/flow and a 55–57% pin-count reduction over the state-of-the-art algorithms/flow.

For cross-contamination avoidance, we also present in this thesis the first design automation flow that considers the cross-contamination problem on pinconstrained biochips. We recognize the desirable properties for cross-contamination avoidance and classify the cross contaminations that can happen with the properties. To cope with these cross contaminations, we propose (1) placement and routing algorithms that minimize the number of crossings among routing paths, and (2) wash droplet scheduling and routing methods that require only one extra control pin and zero assay completion time overhead for general bioassays. Experimental results show the effectiveness and scalability of our algorithms for practical bioassays.

並列關鍵字

design automation ； digital microfluidic biochip ； pin-constrained ； crosscontamination ； algorithm

參考文獻

[2] K. F. B‥ohringer. Modeling and controlling parallel tasks in droplet-based microfluidic systems. IEEE Trans. Comput.-Aided Design Integr Circuits Syst., 25(2):334–344, 2006.

[3] M. Cho and D. Z. Pan. A high-performance droplet router for digital microfluidic biochips. In Proceedings of ACM International Symposium on Physical Design, pages 200–206, April 2008.

[4] J. Ding, K. Chakrabarty, and R. B. Fair. Scheduling of microfluidic operations for reconfigurable two-dimensional electrowetting arrays. IEEE Trans. Comput.-Aided Design Integr Circuits Syst., 20:1463–1468, 2001.

[5] P. Eades and N. C. Wormald. Edge crossings in drawings of bipartite graphs. Algorithmica, 11:379–403, 1994.

[6] R. B. Fair, V. Srinivasan, H. Ren, P. Paik, V. Pamula, and M. Pollack. Electrowetting-based on-chip sample processing for integrated microfluidics. In IEDM Technical Digest, pages 32.5.1–32.5.4, 2003.