https://scholars.lib.ntu.edu.tw/handle/123456789/341034
Title: | BioRoute: A network-flow-based routing algorithm for the synthesis of digital microfluidic biochips | Authors: | Yuh, Ping-Hung YAO-WEN CHANG CHIA-LIN YANG |
Keywords: | Detailed routing; Digital microfluidic biochips; Global routing; Network-flow-based algorithm | Issue Date: | 2008 | Journal Volume: | 27 | Journal Issue: | 11 | Start page/Pages: | 1928-1941 | Source: | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems | Abstract: | Due to 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 very large scale integration routing problems, in addition to routing path selection, the biochip routing problem needs to address the issue of scheduling droplets under practical constraints imposed by the fluidic property and timing restriction of synthesis results. In this paper, we present the first network-flow-based routing algorithm that can concurrently route a set of noninterfering 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 noninterfering nets and then adopt the network-flow approach to generate optimal global-routing paths for 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. Our algorithm targets at both the minimization of cells used for routing for better fault tolerance and minimization of droplet transportation time for better reliability and faster bioassay execution. Experimental results show the robustness and efficiency of our algorithm. © 2008 IEEE. |
URI: | http://www.scopus.com/inward/record.url?eid=2-s2.0-54949138053&partnerID=MN8TOARS http://scholars.lib.ntu.edu.tw/handle/123456789/341034 |
ISSN: | 02780070 | DOI: | 10.1109/TCAD.2008.2006140 | SDG/Keyword: | Algorithms; Bioassay; Biochips; Boolean functions; Computer networks; Digital arithmetic; Drop formation; Drops; Fault tolerance; Marine biology; Microarrays; Microfluidics; Network protocols; Optimization; Quality assurance; Reliability; Scheduling; Scheduling algorithms; Sensor networks; Set theory; Critical problems; Detailed routing; Digital microfluidic biochips; Droplet routing; Global routing; Laboratory procedures; Network-flow-based algorithm; Practical; Routing; Routing and scheduling; Routing paths; Routing problems; Routing schemes; Synthesis of; Time algorithms; Timing restrictions; Transportation times; Very large scale integration routing; Routing algorithms |
Appears in Collections: | 電子工程學研究所 |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.