  Digital microfluidic (DMF) biochips are now being extensively used to
automate several biochemical laboratory protocols such as clinical analysis,
point-of-care diagnostics, and polymerase chain reaction (PCR). In many
biological assays, e.g., in bacterial susceptibility tests, samples and
reagents are required in multiple concentration (or dilution) factors,
satisfying certain "gradient" patterns such as linear, exponential, or
parabolic. Dilution gradients are usually prepared with continuous-flow
microfluidic devices; however, they suffer from inflexibility,
non-programmability, and from large requirement of costly stock solutions. DMF
biochips, on the other hand, are shown to produce, more efficiently, a set of
random dilution factors. However, all existing algorithms fail to optimize the
cost or performance when a certain gradient pattern is required. In this work,
we present an algorithm to generate any arbitrary linear gradient, on-chip,
with minimum wastage, while satisfying a required accuracy in the concentration
factor. We present new theoretical results on the number of mix-split
operations and waste computation, and prove an upper bound on the storage
requirement. The corresponding layout design of the biochip is also proposed.
Simulation results on different linear gradients show a significant improvement
in sample cost over three earlier algorithms used for the generation of
multiple concentrations.
