Information Technology Reference
In-Depth Information
Let
m
be the total number of mix-split steps in a dilution/mixing tree. For a dilution
tree,
m
is equal to
d
, whereas a mixing tree of height
d
can have at most (2
d
−
1)mix-
split steps. A scheduled dilution/mixing tree provides the sequence of mix-split steps
with timing assignment and the mixer allocation to its non-leaf nodes. Let
M
lb
be the
number of mixers required for minimum-time (
d
time cycles) completion of executing
a mixing tree as computed in [17]. After scheduling a mixing tree with
M
lb
mixers, the
mixing tree can be executed in
d
time cycles, whereas with a fewer number of mixers
it will take more time to complete. From Fig. 1 it is evident that for a dilution tree,
M
lb
=1and for a mixing tree,
M
lb
>
1.Let
I
be an array of integers denoting the total
number of droplets of each input fluid required to produce two target droplets and
W
be the total number of waste droplets generated during dilution/mixing.
2.1
Prior Work
In the literature, there exist several dilution algorithms —
GAG
[5],
twoWayMix
[6],
DMRW
[7],
IDMA
[8],
MTC
[13],
REMIA
[14], and several mixing algorithms —
Min-
Mix
[6],
RMA
[9],
RSM
[12] and
MTCS
[15]. Griffith et al. [5] proposed the first dilution
algorithm
GAG
to determine a dilution graph for producing target droplets from the pure
input fluids. Thies et al. [6] presented a dilution algorithm
twoWayMix
that represents
the target
CF C
t
as a
d
-bit binary fraction to determine the dilution tree with an ac-
curacy level of
d
(e.g., Fig. 1(a)). Two other dilution algorithms, namely
DMRW
[7]
and
IDMA
[8], can be used to produce a desired target
CF
from two arbitrary concen-
trations of a sample. However, none of the existing algorithms is capable of producing
a target concentration of a sample from three or more arbitrary concentrations of the
same fluid. Other dilution algorithms presented in [13, 14] consider the problem of pro-
ducing multiple target concentrations from the supply of two pure input fluids and do
not discuss about generalized dilution from multiple arbitrary concentrations. Thies et
al. [6] first proposed a mixing algorithm
Min-Mix
to determine the mixing tree of height
d
for a target ratio of
N
input fluids using
Nd
-bit binary fractions (see Fig. 1(b)). Roy
et al. [9] proposed a mixing algorithm
RMA
that determines the mixing tree for a target
ratio using a ratio-decomposition based technique. Another mixing algorithm
RSM
[12]
determines a mixing graph for multiple target ratios of input fluids using a similar tech-
nique as ratio-decomposition. In [15], a mixing algorithm
MTCS
has been presented
that determines a mixing tree with some common subtrees for producing droplets with
the target ratio of
CF
s.
2.2
Motivation of Our Work
In sample preparation with DMF, a reagent with multiple
CF
s may be available as a by-
product (or waste) of other protocols. These droplets may be reused to produce a target
CF
. However, there exists no dilution/mixing algorithm that determines the correct
mix-split sequence to produce the desired
CF
from a supply of three or more arbitrary
CF
s of the same fluid. This problem was mentioned as one of the open problems by
Thies et al. [6]. This motivates us to formulate a more generalized dilution algorithm,
which can be used for this purpose.
