A routability-driven flow routing algorithm for programmable microfluidic devices

Biochips that are made of Micro Electro Mechanical Systems (MEMS) are concerned by everyone in recent years. The advantages of biochips are high accuracy and fast reaction rate with only a small volume consumption of samples and reagents. Among various types of biochips, flow-based microfluidic biochips receive much attention recently, especially the programmable microfluidic device (PMD). PMDs are capable of performing multitude functions in one platform without requiring any hardware modifications. As the size of chips increase, flow routing becomes more complicated. Traditional method to manually control multiple flows is inefficient and it may not have feasible assay completion time. Fortunately, PMDs has high potential to route flows with pure software programs to overcome the drawbacks of traditional methods. However, naive software program that simply minimizing assay completion time may cause flow-congestion problems and unexpected mixing between different assays, i,e., fluidic constraint. To conduct a viable experiment, a feasible program should not only minimize assay completion time but also consider congestion problems and fluidic constraint. Therefore, we formulate the flow routing problem and propose a routability-driven flow routing algorithm which considers the fluidic constraint and minimizes the assay completion time on PMDs.