Single-Target Algorithms

Single-target algorithms produce exactly one droplet whose concentration value is specified by the user. We have implemented a number of these algorithms in our framework. This page does not describe the algorithms in detail; we simply list the algorithms that are available, along with a short summary and a reference to the paper that introduced each of them.

Binary Search

The Binary Search algorithm identifies a set of mixing operations that produce a droplet with a desired concentration value. Once the set of mixing operations has been computed, droplets having equal concentrations can be linked together in the Dilution Graph in order to reduce waste.

E. J. Griffith, S. Akella, and M. K. Goldberg
Performance Characterization of a Reconfigurable Planar-Array Digital Microfluidic System
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)
25(2):345-357, February, 2006

Bit Scanning

The Bit Scanning algorithm was the first to exploit the binary representation of concentration values in the 1:1 mixing model. It effectively reduces the number of internal mixing operations but may generate significant waste because each mixing step always uses one droplet of sample (100% concentration) or buffer (0% concentration).

W. Thies, J. P. Urbanski, T. Thorsen, and S. Amarasinghe
Abstraction Layers for Scalable Microfluidic Biocomputing
Natural Computing
7(2):255-275, June, 2008

Dilution and Mixing with Reduced Wastage (DMRW)

DMRW was the first single-target sample preparation algorithm to emphasize waste minimization. DMRW takes O(n) time to compute at most n sequential mix operations that can achieve a target concentration value with less than 1/(2n) error.

S. Roy, B. B. Bhattacharya, and K. Chakrabarty
Optimization of Dilution and Mixing of Biochemical Samples Using Digital Microfluidic Biochips
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)
29(11):1696-1708, November, 2010

Improved Dilution and Mixing Algorithm (IDMA)

DMRW generates less waste than Bit Scanning, it may require more mix operations. IDMA improves DMRW to optimize the re-use of intermediate droplets generated during earlier sample preparation stages. This reduces the demand for additional sample/reagent droplets and produces less waste. DMRW takes O(n) time to compute at most n sequential mix operations that can achieve a target concentration value with less than 1/(2n) error.

S. Roy, B. B. Bhattacharya, and K. Chakrabarty
Waste-Aware Dilution and Mixing of Biochemical Samples with Digital Microfluidic Biochips
Design Automation and Test in Europe (DATE)
Grenoble, France, March 14-18, 2011, pp. 1059-1064

REactant MInimization Algorithm (REMIA)

REMIA is the first sample preparation algorithm designed to minimize reactant usage. It tends to produce more waste than DMRW or IDMA, but requires fewer mixing operations. REMIA leverages two novel data structures: the Skewed Mixing Tree and the Exponential Dilution Tree.

J-D. Huang, C-H. Liu, and T-W. Chiang

Reactant Minimization during Sample Preparation on Digital Microfluidic Biochips using Skewed Mixing Trees
International Conference on Computer-Aided Design (ICCAD)
San Jose, CA, USA, November 5-8, 2012, pp. 377-383

Graph-based Optimal Reactant Minimization Algorithm (GORMA)

GORMA is an optimal reactant minimization algorithm based on Branch-and-Bound Search. It exhaustively enumerates all possible dilution graphs and selects the one that minimizes reactant usage and waste through maximal reuse of intermediate droplets.

T-W. Chiang, C-H. Liu, and J-D. Huang
Graph-Based Optimal Reactant Minimization for Sample Preparation on Digital Microfluidic Biochips
VLSI Design Automation and Test (VLSI-DAT)
Hsinchu, Taiwan, April 22-24, 2013, pp. 1-4

Min-Mix

Min-Mix is a multiple-reactant variation of the single-target concentration value sample preparation problem; all of the algorithms described above use single reactants. The Bit Scanning algorithm is a degenerate case of Min-Mix restricted to one sample and one reactant.

W. Thies, J. P. Urbanski, T. Thorsen, and S. Amarasinghe
Abstraction Layers for Scalable Microfluidic Biocomputing
Natural Computing
7(2):255-275, June, 2008

Common Dilution Operator Sharing (CoDOS)

CoDOS is another multi-reactant single-target concentration sample preparation algorithm. It represents the target concentrations as a matrix, and then identifies sub-matrices which are opportunities for sharing dilution operators. CoDOS naturally lends itself to multiple-target sample preparation as well.

C-H. Liu, H-H. Chang, T-C. Liang, and J-D. Huang
Sample Preparation for Many-Reactant Bioassay on DMFBs using Common Dilution Operation Sharing
International Conference on Computer-Aided Design (ICCAD)
San Jose, CA, USA, November 18-21, 2013, pp. 615-621

Generalized Dilution Algorithm (GDA)

GDA is a single-reactant single-target concentration sample preparation algorithm in which multiple instances of the reactant with varying concentration factors are supplied as input. The problem is formulated as a variant of the Subset-sum Problem, and is based on a Dynamic Programming heuristic. 

S. Roy, B. B. Bhattacharya, S. Ghoshal, and K. Chakrabarty
On-Chip Dilution from Multiple Concentrations of a Sample Fluid Using Digital Microfluidics
VLSI Design and Test (VDAT)
Jaipur, India, July 27-30, 2013, pp. 274-283

Contact

Please direct any questions, comments, or other inquiries to the following e-mail address: microfluidics@cs.ucr.edu

Acknowledgment

This material is based upon work supported by the National Science Foundation under Grant Numbers 1035603, 1536026, and 1545097. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.