請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9766
標題: | 數位微流體晶片之合成: 模型,擺置,和繞線 Synthesis of Digital Microfluidic Biochips: Modeling, Placement, and Routing |
作者: | Ping-Hung Yuh 喻秉鴻 |
指導教授: | 楊佳玲(Chia-Lin Yang) |
關鍵字: | 數位微流體晶片,交錯性晶片,擺置,繞線,合成,時序平面規劃,時序樹,網路流, Digital microfluidic biochips,cross-referencing biochips,placement,routing,synthesis,temporal floorplanning,T-tree,network-flow,progressive-ILP, |
出版年 : | 2008 |
學位: | 博士 |
摘要: | 由於微製造(microfabrication)技術的進步,微流體技術近年來受到很大的注意.以液珠(droplet)為基礎的微流體晶片預測會帶來實驗中生物實驗的革命.當生物晶片被用來處理更複雜的反應程序時,生物晶片的複雜度會大幅度的增加.因此,電腦補助設計(computer-aided design)是非常急迫需要的技術.
在這篇論文中,我處理生物晶片合成(synthesis)中的擺置和繞線的問題.本論文分為三個部分.首先我建立生化反應的模型.生化反應可以被模擬成一個三維的平面圖(floorplan).根據這個模型,我可以利用時序平面規劃(temporal floorplanning)的技術來處理生物晶片上的擺置(placement)的問題. 在第二部分,我利用時序平面規劃來處理生物晶片上擺置的問題.我提出了第一個以樹(tree)為基礎的三維平面規劃表示法(3D floorplan representation),叫作時序樹(T-tree).我闡述了時序樹的架構以及和其他表示法相比較下,時序樹的優點.我也證明了時序樹的解空間(solution space)和它的可達性(reachability). 接下來我提出一個以時序樹為基礎的三維平面規劃技術.為了保證反應的正確性,生化反應(assay operation)之間的先後順序必須要被保時.利用生化反應的特點,我提出了一個叢集演算法(clustering algorithm)來得到更好的擺置結果.除此之外,我也考慮了缺陷許可(defect tolerance)的議題. 在第三個部分,我提出兩個液珠繞線(droplet routing)的演算法,分別對應不同的生物晶片的架構.液珠繞線最大的難度是怎樣保證液珠在送時候的正確性.除了繞線之外,液珠繞線還需要考慮排程(scheduling)的議題.對於傳統的生物晶片,我提出了一個全域繞線(global routing)和詳細繞線(detailed routing)的方法.在全域繞線中,我提出了以網路流(network-flow)為基礎的方法.在詳細繞線中,我提出了以疊代法(iterative method)為基礎的方法來作繞線. 對於比較新的交錯參考生物晶片(cross-referencing biochips),我則利用整數線性規劃(integer linear programming)來解決液珠繞線的問題.在這篇論文中,我提出第一個直接處理液珠繞線的演算法. 我提出了一個可以得到最佳解的演算法. 因為此演算法的複雜度, 我另外提出了一個漸進式(progressive)的演算法. 此演算法每次決定液珠於下一個時間點的位置. 實驗結果顯示此漸進式的方法可以達到接近最佳解的結果. Due to the advances in the microfabrication and microelectromechanical systems, microfluidic technology has gained much attention recently. Droplet-based microfluidic biochips are expected to revolutionize biological laboratory procedures by allowing faster and more error-free assays, where droplets are biological sample carriers. As biochips are adopted for the complex procedures in molecular biology, their complexity is expected to increase due to the need of multiple and concurrent assays on a chip. Therefore, there is a pressing need of CAD support for the biochip design automation. In this dissertation, we handle the placement and routing problems in the synthesis of digital microfluidic biochips. This dissertation is divided into three parts. In the first part, we model each fundamental operation, such as droplet mixing or droplet split, as a 3D box. Therefore, the bioassay execution can be modeled as a 3D floorplan with the X (Y) dimension representing the width (height) of a biochip and the $T$ dimension representing the duration of a bioassay. A key observation, which is one of the key contributions of this dissertation, is that under such a model, the bioassay placement problem is transformed to the temporal floorplanning problem. The advantage of this model is that we can have a high flexibility to optimize both the biochip area and the assay completion time. In the second part, we devise a temporal floorplanning technique to solve the placement problem. We propose the first tree-based representation, called T-tree to solve the temporal floorplanning problem. We present the structure of T-tree and its packing method. We show the advantages of T-tree over other 3D floorplan representations when is is applied to the placement problem of biochips. We also prove the reachability and the solution of T-tree, which presents a solid theoretical foundation of T-tre. Next, we propose the T-tree based temporal floorplanning algorithm for the placement problem of biochips. To ensure the correctness of bioassay execution, we handle the temporal orderings among operations. Moreover, we also handle the storage units that are used to store the intermediate result between two data-dependent operations. To make use of the property of a bioassay, we propose a clustering algorithm to reduce problem size and to obtain better solution. We also handle the defect tolerance issue induced by manufacture. In the third part, we solve droplet routing problem on biochips. The droplet routing problem is to move a droplet from one location to another location for reaction. The main challenge of the droplet routing problem is to ensure the correctness of a bioassay; the fluidic property that avoids unexpected mixing among droplets needs to be satisfied. Unlike traditional VLSI routing, in addition to routing path selection, the droplet routing problem needs to address the issue of scheduling droplets under the practical constraints imposed by the fluidic property and the timing restriction induced by the placement result. Two droplet routing algorithms are proposed for different biochip architectures. For general biochips, we propose a two-stage routing scheme (global routing followed by detailed routing). We propose the first network-flow based routing algorithm to handle the droplet routing problem. In detailed routing, we also present the first polynomial-time algorithm using the global-routing paths. We also develop routing techniques under the more scalable cross-referencing biochip paradigm, which uses row/column addressing scheme to activate electrodes for droplet movement. We propose the first droplet routing algorithm that directly solves the problem of routing in cross-referencing biochips. The main challenge of this type of biochips is the electrode interference which prevents simultaneous movement of multiple droplets. We first present a basic integer linear programming (ILP) formulation to optimally solve the droplet routing problem. Due to its complexity, we also propose a progressive ILP scheme to determine the locations of droplets at each time step. Therefore, the problem size can be significantly reduced to a manageable size. Experimental result shows that the progressive-ILP based routing scheme can obtain a near-to-optimal solution. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9766 |
全文授權: | 同意授權(全球公開) |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-97-1.pdf | 4.56 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。