# Single-target Sample Preparation

### 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.