https://scholars.lib.ntu.edu.tw/handle/123456789/118210
標題: | Bioroute: A Network-Flow Based Routing Algorithm for Digital Microfluidic Biochips | 作者: | Yuh, Ping-Hung Yang, Chia-Lin CHIA-LIN YANG |
公開日期: | 2007 | 起(迄)頁: | 752-757 | 來源出版物: | IEEE/ACM International Conference on Computer-Aided Design | 摘要: | Due to the recent advances in microfluidics, digital microfluidic biochips are expected to revolutionize laboratory procedures. One critical problem for biochip synthesis is the droplet routing problem. Unlike traditional VLSI routing problems, in addition to routing path selection, the biochip routing problem needs to address the issue of scheduling droplets under the practical constraints imposed by the fluidic property and the timing restriction of the synthesis result. In this paper, we present the first network-flow based routing algorithm that can concurrently route a set of non-interfering nets for the droplet routing problem on biochips. We adopt a two-stage technique of global routing followed by detailed routing. In global routing, we first identify a set of non-interfering nets and then adopt the network-flow approach to generate optimal global-routing paths for the nets. In detailed routing, we present the first polynomial-time algorithm for simultaneous routing and scheduling using the global-routing paths with a negotiation-based routing scheme. The experimental results show the robustness and efficiency of our algorithm. © 2007 IEEE. |
URI: | http://ntur.lib.ntu.edu.tw//handle/246246/232558 http://ntur.lib.ntu.edu.tw/bitstream/246246/232558/-1/06.pdf |
DOI: | 10.1109/ICCAD.2007.4397356 | SDG/關鍵字: | Bioassay; Biochips; Design; Digital arithmetic; Drop formation; Drops; Fluid mechanics; Marine biology; Microarrays; Nanofluidics; Network routing; Scheduling; Scheduling algorithms; Set theory; Biochip; Computer-aided design; Detailed routing; Digital microfluidic biochips; Droplet routing; Flow based; Global routing; International conferences; Laboratory procedures; Polynomial-time algorithms; Routing and scheduling; Routing paths; Routing problems; Routing schemes; Two stages; VLSI routing; Routing algorithms |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。