Biomedical Engineering Reference
In-Depth Information
1. Given a set of target solutions
Ts
(
Ts
1
,
Ts
2
,
Ts
3
, …,
Ts
m
), identify the
types of reagents contained in
R
(
R
1
,
R
2
,
R
3
, …,
R
n
).
2. Determine the set of stock solutions
Ss
(
Ss
1
,
Ss
2
,
Ss
3
, …,
Ss
n
) following
the mapping
R
i
↔
Ss
i.
3. For each type of stock solution
Ss
i
, identify the set of target solutions
TsR
i
that contain the corresponding reagent
R
i
.
4. Determine the modulation resolution for stock solution
Ss
i
using the
equation
modulation resolution
=
GCD
(
TsR
i
), when GCD refers to the
greatest common divisor. The Euclidean algorithm is used to com-
pute the GCD [73].
5. Determine the concentration for each solution using Equation 6.2.
6. Calculate the number of droplets dispensed from each stock solu-
tion reservoir for each type of target solution using Equation 6.3.
7. Check if the total number of droplets dispensed from different stock
solution reservoirs exceeds the capacity of the mixing reservoir.
If yes, go to step 8; otherwise, the algorithm terminates.
8. Identify the stock solution that dispenses the most droplets into the
mixing reservoir in preparing the target solution. Double the con-
centration of that stock solution. Then go to step 6.
Assume that the total number of target solutions is
m
, and
n
types of reagents
are contained. Step 1 scans the target solution set and records different
reagents. It takes O(
n
+
m
) time. Step 2 carries out one-to-one mapping and
takes O(
n
+
m
) time. For step 3, in the worst case, each target solution contains
all types of reagents. Therefore, this step takes O(
nm
) time. According to the
Euclidean algorithm, Step 4 takes O(
n
log
10
C
max
) time where
C
max
is the larg-
est value of the concentrations [73]. For most bioassays, the concentrations
can be represented using 4 digits, that is, k < 10000. Therefore, Step 4 takes
O(4
n
) = O(
n
) time. Step 5 takes O(
n
) time. For Step 6, in the worst case, each
target solution contains all types of reagents. Thus, this step takes O(
nm
)
time. Step 7 takes O(
n
+
m
) time. Step 8 looks for the stock solution that dis-
penses the most droplets into the mixing reservoir in preparing the target
solution, which takes O(
n
) time.
For the entire algorithm, in the best case, Step 8 is never reached. The algo-
rithm takes O(
n
+
m+n
+
m+nm+n+n+n+m+nm+n
) = O (
nm
) t i m e. I n t h e wo r s t c a s e,
for every target solution, the total number of droplets dispensed from differ-
ent stock solution reservoirs exceeds the capacity of the mixing reservoir.
Steps 6-8 are executed for each target solution, that is, m times. Therefore, the
entire solution-preparation planning algorithm takes O(
nm
2
) time.
We next address the complexity of the fluidic operation; in the best case,
the preparation of a single target solution requires only one iteration of the
mixing-and-dispensing operation. No extra dilution is needed. The entire
preparation plan takes
m
mixing-and-dispensing operations. In the worst
