A progressive-ILP based routing algorithm for cross-referencing biochips.
Journal
Proceedings of the 45th Design Automation Conference, DAC 2008, Anaheim, CA, USA, June 8-13, 2008
Pages
284-289
Date Issued
2008
Author(s)
Abstract
Due to recent advances in microfluidics technology, digital microfluidic biochips and their associated CAD problems have gained much attention, most of which has been devoted to direct-addressing biochips. In this paper, we solve the droplet routing problem under the more scalable cross-referencing biochip paradigm, which uses row/column addressing scheme to activate electrodes. 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. Experimental results demonstrate the efficiency and effectiveness of our progressive ILP scheme on a set of practical bioassays.
SDGs
Type
conference paper