BioRoute: A network-flow-based routing algorithm for the synthesis of digital microfluidic biochips
Journal
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Journal Volume
27
Journal Issue
11
Pages
1928-1941
Date Issued
2008
Author(s)
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.
Subjects
Detailed routing; Digital microfluidic biochips; Global routing; Network-flow-based algorithm
SDGs
Other Subjects
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
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
07.pdf
Size
931.1 KB
Format
Adobe PDF
Checksum
(MD5):9a86f2f72d7d25be7d1307498d256048