Biomedical Engineering Reference
In-Depth Information
predicate of the form "Tag(
i
) =
v
" is not applied directly (since PCR and similar
methods do not allow this) by instead applying the OR of selective predicates of
the form "Tag(
i
) =
u
" for all possible
u
in
D
i
that are not equal to
v
). These selec-
tion operations can be executed by the use of recombinant DNA operations, ap-
plying and improving on logical processing methods developed in the field of
DNA computing. Furthermore, one can provide the additional operation of se-
lective amplification of the DNA populations. If these amplification operations
are also executed, the logical selection and amplification operations result in a
test tube whose selected DNA is vastly amplified. After the amplification proc-
ess is completed, the output strands should vastly predominate all other strands
of the Biomolecular Database. Other database operations that can be imple-
mented by biochemical operations include database unions and limited joins
(50).
3.9.1. Scalability of Our Query Processing
These operations can be executed in a scalable way. The required volume
never grows significantly; the volume is a fixed linear function of the number of
elements of the database. (The constant multiple here is the degree of redun-
dancy with which DNA strands are used to store database elements; we expect
that one can allow between a few hundred and possibly as few as 10 DNA
strands to encode a given database element.) The number of required DNA hy-
bridization steps grows only linearly with the size of the query formula. So the
time for executing a query grows just linearly with the length of the query for-
mula, which in practice is of very modest size (as compared to the size of the
database, which can be enormous)—say 20 or so variables. Hence the key time
limitation is the time for DNA hybridization. But DNA hybridization time is
nearly invariant of the size of the database even if the hybridization is execution
on an enormous amount of DNA (up to extremely large database sizes, say 10
15
).
However, there are considerable technical challenges in the design of the proto-
cols—for example, biological data strands may be originally dsDNA while
search protocols would function best with ssDNA (hence the protocols need to
either form ssDNA or be modified appropriately). A key additional technical
challenge in scaling the technology is the scale and number of resulting molecu-
lar biology reactions, requiring many tedious laboratory steps, particularly in the
case of extremely large database sizes. This can be addressed by subsequent
automation. We discuss two distinct methods for logical query processing: the
first uses primer-extension techniques on solid support, previously developed
(47) to solve SAT problems, and the other uses solution-based PCR amplifica-
tion techniques. The second has greater potential for scalability due to the fact
that it is solution based (so the chemistry operates in 3D, rather than being con-
