臺灣博碩士論文加值系統

由於微製造(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.

Chinese Abstract ii
Abstract iv
List of Tables xi
List of Figures xii
Chapter 1. Introduction 1
1.1 Introduction to Biochips . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Microarray . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2 Microfluidic Biochips . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Digital Microfluidic Biochips . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Synthesis of Biochips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Overview of this Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4.1 Modeling of Bioassay Execution . . . . . . . . . . . . . . . . . . . 14
1.4.2 Placement of Digital Microfluidic Biochips . . . . . . . . . . . . . . 14
1.4.3 Droplet Routing on General Biochips . . . . . . . . . . . . . . . . 15
1.4.4 Droplet Routing on Cross-referencing Biochips . . . . . . . . . . . 15
1.5 Organization of this Dissertation . . . . . . . . . . . . . . . . . . . . . . . 16
Chapter 2. Related Works 17
2.1 Placement of Biochips . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Droplet Routing on General Biochips . . . . . . . . . . . . . . . . . . . . 19
2.3 Droplet Routing on Cross-referencing Biochips . . . . . . . . . . . . . . . 20
Chapter 3. Modeling of Bioassay Execution 22
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2 Schematic View of Digital Microfluidic Biochips . . . . . . . . . . . . . . 23
3.3 Bioassay Execution Illustration . . . . . . . . . . . . . . . . . . . . . . . 24
3.4 Modeling of Bioassay Execution . . . . . . . . . . . . . . . . . . . . . . . 25
Chapter 4. Placement of Digital Micro fluidic Biochips 27
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.3 The T-tree Representation . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.3.1 Review of Existing 3D Floorplan Representations . . . . . . . . . . 32
4.3.2 The T-tree Representation . . . . . . . . . . . . . . . . . . . . . . 34
4.3.3 Solution Space and Reachability . . . . . . . . . . . . . . . . . . . 46
4.4 T-tree Based Biochip Placement . . . . . . . . . . . . . . . . . . . . . . . 48
4.5 The Floorplanning Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 53
4.5.1 Clustering of Generation and Reconfigurable Operations . . . . . . 53
4.5.2 Perturbations for Biochip Placement . . . . . . . . . . . . . . . . . 56
4.5.3 Placement of Optical Detectors . . . . . . . . . . . . . . . . . . . . 58
4.5.4 Cost Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.5.5 Feasibility Detection and Tree Reconstruction . . . . . . . . . . . . 59
4.6 Defect Tolerance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.7 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
Chapter 5. Droplet Routing on General Biochips 78
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.1.1 The Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.2 Routing on Biochips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.2.1 Droplet Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.2.2 Routing Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.2.3 Modeling the Routing Constraints . . . . . . . . . . . . . . . . . . 85
5.2.4 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.3 Biochip Routing Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.3.1 Routing Algorithm Overview . . . . . . . . . . . . . . . . . . . . . 88
5.3.2 Net Criticality Calculation . . . . . . . . . . . . . . . . . . . . . . 89
5.3.3 Global Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.3.4 Detailed Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3.5 Timing-Aware Routing . . . . . . . . . . . . . . . . . . . . . . . . 104
5.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Chapter 6. Droplet Routing on Cross-referencing Biochips 111
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.1.1 The Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.2 Routing on Cross-Referencing Biochips . . . . . . . . . . . . . . . . . . . 114
6.2.1 Electrode Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.2.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.3 ILP Formulation for Droplet Routing . . . . . . . . . . . . . . . . . . . . 116
6.3.1 Basic ILP Formulation . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.3.2 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 123
6.4 Progressive-ILP Routing Scheme . . . . . . . . . . . . . . . . . . . . . . . 123
6.4.1 Progressive Routing Algorithm Overview . . . . . . . . . . . . . . 123
6.4.2 Progressive-ILP Formulation . . . . . . . . . . . . . . . . . . . . . 124
6.4.3 Droplet Movement Cost . . . . . . . . . . . . . . . . . . . . . . . . 128
6.4.4 Handling 3-pin Nets . . . . . . . . . . . . . . . . . . . . . . . . . . 130
6.4.5 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 130
6.4.6 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
6.5 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
Chapter 7. Concluding Remarks and Future Work 135
7.1 Modeling of Bioassay Execution . . . . . . . . . . . . . . . . . . . . . . . 136
7.2 Placement of Digital Micro fluidic Biochips . . .. . . . . . . . 136
7.3 Droplet Routing on General Biochips . . . . . . . . . . . . 137
7.4 Droplet Routing on Cross-referencing Biochips . . . . . . . . . . 138
Bibliography 139

[1] Advanced liquid logic, http://www.liquid-logic.com.
[2] http://www.gnu.org/software/glpk/.
[3] Silicon biosystems, http://www.siliconbiosystems.com/.
[4] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, New Jersey, 1993.
[5] K. Bazargan, R. Kastner, and M. Sarrafzadeh. Fast template placement for reconfigurable computing systems. IEEE Design and Test of Computers-Special Issue on Reconfigurable Computing, 17(1):68-83, January 2000.
[6] K. F. Böhringer. Modeling and controlling parallel tasks in droplet-based microfluidic systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pages 334-343, February 2006.
[7] S. Brenner, S. R. Williams, E. H. Vermaas, T. Storck, K. Moon, C. McCollum, J.-I. Mao, S. Luo, J. J. Kirchner, S. Eletr, R. B. DuBridge, T. Burcham, and G. Albrecht. In vitro cloning of complex mixtures of DNA on microbeads: Physical separation of differentially expressed CDNAs. National Academy of Sciences, 97(4):1165-1170, 2000.
[8] Y.-C. Chang, Y.-W. Chang, G.-M. Wu, and S.-W. Wu. B*-trees: A new representation for non-slicing floorplans. In Proceedings of ACM/IEEE Design Automation Conference, pages 458-463, June 2000.
[9] L. Cheng, L. Deng, and M. D. F. Wang. Floorplanning for 3-D VLSI design. In Proceedings of ACM/IEEE Asia South Pacific Design Automation Conference, pages 405-411, July 2005.
[10] M. Cho and D. Z. Pan. Boxrouter: a new global router based on box expansion and progressive ILP. In Proceedings of ACM/IEEE Design Automation Conference, pages 373-378, July 2006.
[11] S. K. Cho, S. K. Fan, H. Moon, and C. J. kim. Toward digital microfluidic circuits: Creating, transporting, cutting and merging liquid droplets by electrowetting-based actuation. In Proceedings of IEEE International Conference on Micro Electro Mechanical Systems, pages 32-52, 2002.
[12] C. T. Culbertson, S. C. Jacobson, and J. M. Ramsey. Microchip devices for high-efficiency separations. Analytical Chemistry, 72:5814-5819, December 2000.
[13] J. Ding, K. Chakrabarty, and R. B. Fair. Scheduling of microfluidic operations for reconfigurable two-dimensional electrowetting arrays. IEEE Transaction on Computer Aided Design of Integrated Circuits and Systems, 20(12):1463-1468, 2001.
[14] W. E. Dougherty and D. E. Thomas. Unifying behavioral synthesis and physical design. In Proceedings of ACM/IEEE Design Automation Conference, pages 756-761, June 2000.
[15] C. A. Emrich, H. J. Tian, I. L. Medintz, and R. A. Mathies. Microfabricated 384-lane capillary array electrophoresis bioanalyzer for ultra-high-throughput genetic analysis. Analytical Chemistry, pages 5076-5083, October 2002.
[16] R. B. Fair, V. Srinivasan, H. Ren, P. Paik, V. Pamula, and M. Pollack. Electrowetting-based on-chip sample processing for integrated microfluidics. In Proceeding of IEEE International Electron Device Meeting, pages 32.5.1-32.5.4, December 2003.
[17] S. P. Fekete, E. KÄohler, and J. Teich. Optimal fpga module placement with temporal precedence constraints. In Proceedings of ACM/IEEE Design, Automation, and Test in Europe, pages 658-665, March 2001.
[18] J. Gong, S.-K. Fan, and C.-J. Kim. Portable digital microfluidics platform with active but disposable lab-on-chip. In Proceedings of IEEE International Conference on Micro Electro Mechanical Systems, pages 355-358, January 2004.
[19] B. Goplen and S. Sapatnekar. E±cient thermal placement of standard cells in 3d ics using a force directed approach. Proceedings of International Conference on Computer Aided Design, pages 86-89, November 2003.
[20] E. J. Gri±th, S. Akella, and M. K. Goldberg. Performance characterization of a reconfigurable planar-array digital micro°uidic system. IEEE Transactions
on Computer-Aided Design of Integrated Circuits and Systems, pages 345-357, February 2006.
[21] Z. P. Gu, J. Wang, R. P. Dick, and H. Zhou. Incremental exploration of the combined physical and behavioral design space. In Proceedings of ACM/IEEE
Design Automation Conference, pages 208-213, June 2005.
[22] P.-N. Guo, C.-K. Cheng, and T. Yoshimura. An O-tree representation of non-slicing foorplans and its application. In Proceedings of ACM/IEEE Design
Automation Conference, pages 268-273, June 1999.
[23] M. Handa and R. Vemuri. A fast algorithm for finding maximal empty rectangles for dynamic fpga placement. In Proceedings of Design, Automation and Test in Europe, pages 744-745, February 2004.
[24] P. Hilton and J. Pederson. Catalan numbers, their generalization, and their uses. Mathematical Intelligencer, 13:64-75, 1991.
[25] ITRS. The international technology roadmap for semiconductors: http://public.itrs.net/.
[26] C. Jurinke, D. van den Boom, C. Cantor, and H. Koster. The use of massarray technology for high throughput genotyping. Advances in Biochemical Engineering/Biotechnology, 77:57-74, 2002.
[27] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671-680, May 1983.
[28] E. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston, 1976.
[29] J.-M. Lin and Y.-W. Chang. TCG: A transitive closure graph-based representation for non-slicing floorplans. In Proceedings of IEEE/ACM Design Automation Conference, pages 764-769, June 2001.
[30] S. W. Mahfoud and D. E. Goldberg. Parallel recombinative simulated annealing: a genetic algorithm. Parallel Computing, 21:1-28, 1995.
[31] L. McMurchie and C. Ebeling. Pathfinder: a negotiation-based performance-driven router for fpgas. In Proceedings of ACM/IEEE International Symposium on Field-programmable Gate Array, pages 111-117, Feb. 1995.
[32] K. Mehlhorn and S. NÄaher. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press, 1999.
[33] R. D. Mohring. Graphs and Orders: the role of graphs in the theory of ordered sets and its application. D. Reidel Publishing Company, 1984.
[34] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani. Rectangle-packing-based module placement. In Proceedings of ACM/IEEE international conference on Computer-aided design, pages 472-479, November 1995.
[35] S. Mutlu, F. Svec, C. H. Mastrangelo, J. M. J. Frechet, and Y. B. Gianchandani. Enhanced electro-osmotic pumping with liquid bridge and field effect flow rectification. In Proceedings of IEEE International Conference on Micro Electro Mechanical Systems, pages 850-853, 2004.
[36] S. T. Obenaus and T. H. Szymanski. Gravity: Fast placement for 3-d vlsi. ACM Transactions on Design Automation of Electronic Systems, 8(3):298-315, July 2003.
[37] 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 1990.
[38] M. G. Pallock, A. D. Shenderov, and R. B. Fair. Electrowetting-based actuation of droplets for integrated micro°uidics. Lab on a Chip, 2(1):96-101, 2002.
[39] A. J. Ricketts, K. Irick, N. Vijaykrishnan, and M. J. Irwin. Priority scheduling in digital microfluidics-based biochips. In Proceedings of ACM/IEEE Design, Automation, and Test in Europe, pages 472-479, November 1995.
[40] T. H. Schulte, R. L. Bardell, and B. H. Weigl. Microfluidic technologies in clinical diagnostics. Clinica Chimica Acta, 321(1-2):1-10, July 2002.
[41] G. N. Somero. Proteins and temperature. Annu. Rev. Physiol., 57:43{68, 1995.
[42] V. Srinivasan, V. Pamula, and R. Fair. A droplet-based microfluidic lab-on-a-chip for glucose detection. Analytica Chimica Acta, 507(1):145-150, 2004.
[43] 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, 4(4):310-315, 2004.
[44] V. Srinivasan, V. Pamula, P. Paik, and R. Fair. Protein stamping for maldi mass spectrometry using an electrowetting-based microfluidic platform. In Proceedings of International Society for Optical Engineering, pages 26-32, November 2004.
[45] V. Srinivasan, V. K. Pamula, M. G. Pollack, and R. B. Fair. A digital microfluidic biosensor for multianalyte detection. In Proceedings of International Conference on Micro Electro Mechanical Systems, pages 327-330, January 2003.
[46] 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, November 2004.
[47] F. Su and K. Chakrabarty. Design of fault-tolerant and dynamically-reconfigurable micro°uidic biochips. In Proceedings of ACM/IEEE Design, Automation, and Test in Europe, pages 1202-1207, March 2005.
[48] F. Su and K. Chakrabarty. Unified high-level synthesis and module placement for defect-tolerant microfluidic biochips. In Proceedings of ACM/IEEE Design Automation Conference, pages 825-830, June 2005.
[49] F. Su, K. Chakrabarty, and R. B. Fair. Micrpfluidic-based biochips: Technology issues, implementation platforms, and design-automation challenges. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25(4):211-223, February 2006.
[50] 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, March 2006.
[51] T. Thorsen, S. Maerkl, and S. Quake. Microfluidic large-scale integration. Science, 298(5593):580-584, October 2002.
[52] E. Verpoorte and N. F. D. Rooij. Micro°uidics meets mems. Proceedings of IEEE, 91(6):930-953, June 2003.
[53] P. Watts and S. J. Haswell. The application of micro reactors for organic synthesis. Chemical Society Reviews, 34:235-246, 2005.
[54] D. F.Wong and C. L. Liu. A new algorithm for floorplan design. In Proceedings of ACM/IEEE Design Automation Conference, pages 101-107, June 1996.
[55] J.-Y. Wuu, T.-C. Chen, and Y.-W. Chang. SoC test scheduling using the b*-tree based foorplanning technique. In Proceedings of ACM/IEEE Asia South Pacific Design Automation Conference, pages 1188-1191, January 2004.
[56] Y. Xia, M. Chrzanowska-Jeske, B. Wang, and M. Jeske. Using a distributed rectangle bin-packing approach for core-based soc test scheduling with power constraints. In Proceeding of ACM/IEEE International Conference on
Computer-Aided Design, pages 100-105, November 2003.
[57] T. Xu and K. Chakrabarty. A cross-referencing-based droplet manipulation method for high-throughput and pin-constrained digital microfluidic arrays. In Proceedings of ACM/IEEE Design, Automation, and Test in Europe, pages
552-557, April 2007.
[58] 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, October 2007.
[59] T. Xu, P. Thwar, V. Srinivasan, V. K. Pamula, and K. Chakrabarty. Droplet routing in the synthesis of sigital microfluidic biochips. In IEEE-NIH Life Science Systems and Applications Workshop, pages 140-143, November 2007.
[60] H. Yamazaki, K. Sakanushi, S. Nakatake, and Y. Kajitani. 3d-packing by meta data structure and packing heuristics. IEICE Transaction on Fundamental of Electronics, Communication and Computer Science, E83-A(4):639-645, April 2000.
[61] J.-Y. Yoon and R. L. Garrell. Preventing biomolecular adsorption on electrowetting-based biofluidic chips. Analytical Chemistry, 75(19):5097-5102, October 2003.
[62] 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, June 2008.
[63] P.-H. Yuh, C.-L. Yang, and Y.-W. Chang. Temporal foorplanning using the T-tree formulation. In Proceedings of ACM/IEEE International Conference on Computer-Aided Design, pages 300-305, November 2004.
[64] 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, July 2006.
[65] 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, November 2007.
[66] P.-H. Yuh, C.-L. Yang, Y.-W. Chang, and H.-L. Chang. Temporal floorplanning using 3D-subTCG. In Proceedings of ACM/IEEE Asia and South Pacific Design Automation Conference, pages 725-730, January 2004.
[67] Y. Zhao and S. Cho. Microparticle sampling by electrowetting-actuated droplet sweeping. Lab on a Chip, 6(1):137-144, 2006.