Information Technology Reference
In-Depth Information
this as a subset-sum problem (SSP) and present a heuristic algorithm based on pseudo-
polynomial time dynamic programming approach [16]. This solves an open problem
posed by Thies et al. [6]. We report simulation results on a data set to demonstrate the
efficiency of the proposed method for various objective functions.
The remainder of the paper is organized as follows. Section 2 provides the related
prior work and motivation of our work. Section 3 deals with the scheme for generalized
dilution from multiple (
two
or
more
) arbitrary concentrations of the same sample fluid.
Finally, conclusions are drawn in Section 4.
2
Automatic Dilution and Mixing
In this paper, we consider the (1:1) mix-split model, in which a unit-volume droplet
of a biofluid
x
1
of
CF
=
C
1
is mixed with a unit-volume droplet of another biofluid
x
2
of
CF
=
C
2
to produce a mixture of
CF
=
C
1
+
C
2
; it is then split equally into
two unit-volume droplets. One (1:1) mix operation and a subsequent balanced split are
together referred to as a
mix-split step
; the two droplets, thus produced, may be used in
the next step or one of them is discarded as a
waste droplet
if not needed. A
dilution
or
mixing tree
is a binary tree where each leaf node represents an input fluid, and an
internal node denotes a (1:1) mix-split step between two input (or intermediate) fluid
droplets. If a target mixture with a certain ratio of its constituents is to be prepared from
a supply of input fluids each with
CF
=1, such that the error in each constituent
CF
does not exceed
1
2
d
+1
, then a mixing tree of depth
d
is needed to depict the complete
mix-split process. Dilution is a special case of mixing of only two input fluids (sample
and buffer). A dilution tree of depth 5 that produces two target droplets (black nodes)
of
CF
=
2
32
from a sample (
CF
= 100%) and a buffer fluid (
CF
=0%)isshown
in Fig. 1(a). The intermediate and waste droplets, which are generated in the process,
are also shown in different shades. The protocol to mix five input fluids with a ratio
of 3:3:3:5:2 (all supplied with 100%
CF
), is depicted by a mixing tree of depth 4 as
shown in Fig. 1(b).
Inputs:
Level
Level
CF
Inputs:
4
5
27
32
11
16
3
8
3
4
1
2
CF
x
i
CF
A
C
h
= 100%
Target Ratio:
3:3:3:5:2
CF
D
C
=0%
3
4
x
1
=0
.
0011
2
x
2
=0
.
0011
2
x
3
=0
.
0011
2
A
CF
C
t
=
2
32
=0
.
11011
2
3
2
A
x
4
2
x
4
=0
.
0101
2
1
Output Parameters:
x
5
=0
.
0010
2
D
x
3
x
5
x
1
x
2
1
d
m
W
I
(
A, D
)
0
Output Parameters:
A
x
3
x
4
x
1
x
2
d
m
W
I
(
x
1
,x
2
,x
3
,x
4
,x
5
)
0
D
A
(a)
(b)
27
32
≡
0
.
11011
2
), the dilution tree obtained by
twoWayMix
[6] using sample fluid
A
(
CF
=1)andbuffer
D
(
CF
=0). (b) For target ratio
3:3:3:5:2, the mixing tree obtained by
Min-Mix
[6] using five input fluids all with
CF
=1.
Fig. 1.
(a) For target
CF C
t
=84
.
375% (
≈
