Multiple-Target Algorithms

Multiple-target algorithms produce several droplets whose desired concentration values are 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.

Multi-Target MinMix

The Multi-Target MinMix algorithm creates and prunes a Dilution Tree to reduce the number of steps and the amount of waste produced during multi-target sample preparation.

S. Bhattacharjee, A. Banerjee, and B. B. Bhattacharya
Multiple Dilution Sample Preparation Using Digital Microfluidic Biochips
International Symposium on Electronic System Design (ISED)
Kolkata, India, December 19-22, 2012, pp. 188-192

Reagent Saving Mixing Algorithm (RSMA)

RSMA tries to minimize reagent consumption while limiting waste production. It also tries to reduce sample preparation time through concurrent sample preparation, thereby increasing the amount of operation-level parallelism available in the Dilution Graph.

Y-L. Hsieh, T-Y. Ho, and K. Chakrabarty
A Reagent-Saving Mixing Algorithm for Preparing Multiple-Target Biochemical Samples Using Digital Microfluidics
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)
31(11):1656-1669, November, 2012

WAste Recycling Algorithm (WARA)

WARA uses the REMIA single-target sample preparation algorithm to create a mixing tree that minimization reactant consumption for each target concentration. It then looks for opportunities to recycle waste droplets produced by one tree by reusing them in other trees.

J-D. Huang, C-H. Liu, and H-S. Lin
Reactant and Waste Minimization in Multitarget Sample Preparation on Digital Microfluidic Biochips
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)
32(10):1484-1494, October, 2013

de Bruijn Graph Traversal Algorithm

The problem of multi-target sample preparation with no intermediate storage is formulated as an Asymmetric Traveling Salesman Problem on a de Bruijn Graph. The drawback is that limiting storage does not facilitate reuse of  intermediate product droplets, and leads to significant waste.

D. Mitra, S. Roy, S. Bhattacharjee, K. Chakrabarty, and B. B. Bhattacharya
On-Chip Sample Preparation for Multiple Targets Using Digital Microfluidics
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)
33(8):1131-1144, August, 2014

Linear Dilution Gradient

By restricting the multiple target concentration values to a Linear Gradient, it is possible to generate a Linear Dilution Tree that produces no waste. The approach can generalize to non-linear dilution gradients but may produce some waste in those cases.

S. Bhattacharjee, A. Banerjee, T-Y. Ho, K. Chakrabarty, and B. B. Bhattacharya
On Producing Linear Dilution Gradient of a Sample with a Digital Microfluidic Biochip
International Symposium on Electronic System Design (ISED)
Singapore, December 12-13, 2013, pp. 77-81

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.