Parallel Biomolecular Computation: Models and Simulations
Parallel Biomolecular Computation: Models and Simulations
复制标题
并行生物分子计算：模型和模拟
DOI：
10.1007/pl00008272
复制
发表时间：
1999
期刊：
影响因子：
1.1
通讯作者：
J. Reif
中科院分区：
文献类型：
--
作者：
J. Reif
抽象的。本文关注分子尺度大规模并行计算技术的发展，我们将其称为分子并行性。虽然这乍一看似乎纯粹是科幻小说，但 Adleman [Ad1] 已经在解决哈密顿路径问题中采用了分子并行性，并在小图 DNA 实验室实验中成功测试了他的技术。 Lipton [L] 表明，使用长度为 O(n log n) 碱基对的 DNA，可以在 O(n) 实验室步骤中找到大小为 n 的布尔表达式的令人满意的输入。 Adleman 和 Lipton 最近在分子并行性方面的工作仅考虑了 NP 搜索问题的解决方案，并没有提供通过纯分子手段快速执行冗长计算的方法；实验步骤的数量与模拟表达式的大小线性相关。有关分子并行性的最新研究，请参阅 [Re3]；有关分子并行性的广泛调查，请参阅 [Re4]。我们的目标是通过使用分子并行性快速执行冗长的计算。我们希望通过或多或少的传统生物技术工程技术，在少量实验室步骤内使用短 DNA 链来执行这些生物分子计算。本文描述了在明确定义的生物分子计算抽象模型的背景下实现这一目标的技术。尽管我们的结果仅具有理论意义，但由于需要大量的分子并行性（即大试管体积），我们相信我们的理论模型和结果可能是后续更实际工作的基础，就像在并行计算领域所做的那样。我们提出了两种生物分子计算的抽象模型。第一个模型是并行关联内存 (PAM) 模型，是一个非常高级的模型，其中包括并行关联匹配 (PA-Match) 操作，该模型似乎提高了分子并行性的能力，超出了 Lipton 之前考虑的操作 [L]。我们通过 PAM 模型对传统的顺序和并行计算模型进行了一些模拟。每个模拟都在大小为 O(s) 的字母表上使用长度为 O(s) 的字符串（对应于长度为 O(s log s) 碱基对的 DNA）。使用非 PA-Match 的 O(s log s) PAM 操作（或假设连接操作的 O(s) 操作）和 t PA-Match 操作，我们可以： 1. 模拟具有空间限制 s 和时间限制 2O(s) 的非确定性图灵机计算，其中 t = O(s) ， 2. 模拟具有时间限制 D、M 个存储单元和处理器限制 P 的 CREW PRAM，其中 s = O( log (PM)) 且 t = O(D+s)，
3. 找到可在 s 空间中构造、具有 n 个输入、无界扇出和深度 D 的布尔电路的满足输入，其中 t = O(D+s)。
我们还提出了重组 DNA (RDNA) 模型，它是一个低级模型，允许对非常容易理解的重组 DNA 操作进行抽象操作，并为 DNA 的相关结构特性提供一种表示（我们称之为复合体）。对于长度为 s 的长串的 PA-Match 操作无法通过重组 DNA 技术直接通过 DNA 中的一步互补配对来实现；尽管如此，我们证明这种匹配操作可以在 RDNA 模型中进行模拟，通过长度为 2 的子串（对应于对数长度 DNA 子序列）的互补配对的多个步骤，减速时间为 O(s)。 PAM 模型的其他每个操作都可以在我们的 RDNA 模型中执行，而不会减慢速度。我们进一步表明，随着进一步的 O(s)/ log (1/ε) 减速，即使某些重组 DNA 操作（例如分离）可能以 ε 的概率出错，模拟也可以以 1/2 的概率正确完成。我们还观察到 PRAM 以及分子模型的图灵机可以进行有效的模拟。
Abstract. This paper is concerned with the development of techniques for massively parallel computation at the molecular scale, which we refer to as molecular parallelism. While this may at first appear to be purely science fiction, Adleman [Ad1] has already employed molecular parallelism in the solution of the Hamiltonian path problem, and successfully tested his techniques in a lab experiment on DNA for a small graph. Lipton [L] showed that finding the satisfying inputs to a Boolean expression of size n can be done in O(n) lab steps using DNA of length O(n log n) base pairs. This recent work by Adleman and Lipton in molecular parallelism considered only the solution of NP search problems, and provided no way of quickly executing lengthy computations by purely molecular means; the number of lab steps depended linearly on the size of the simulated expression. See [Re3] for further recent work on molecular parallelism and see [Re4] for an extensive survey of molecular parallelism. Our goal is to execute lengthy computations quickly by the use of molecular parallelism. We wish to execute these biomolecular computations using short DNA strands by more or less conventional biotechnology engineering techniques within a small number of lab steps. This paper describes techniques for achieving this goal, in the context of well defined abstract models of biomolecular computation. Although our results are of theoretical consequence only, due to the large amount of molecular parallelism (i.e., large test tube volume) required , we believe that our theoretical models and results may be a basis for more practical later work, just as was done in the area of parallel computing. We propose two abstract models of biomolecular computation. The first, the Parallel Associative Memory (PAM) model, is a very high-level model which includes a Parallel Associative Matching (PA-Match) operation, that appears to improve the power of molecular parallelism beyond the operations previously considered by Lipton [L]. We give some simulations of conventional sequential and parallel computational models by our PAM model. Each of the simulations use strings of length O(s) over an alphabet of size O(s) (which correspond to DNA of length O(s log s) base pairs). Using O(s log s) PAM operations that are not PA-Match (or O(s) operations assuming a ligation operation) and t PA-Match operations, we can: 1. simulate a nondeterministic Turing Machine computation with space bound s and time bound 2O(s), with t = O(s) , 2. simulate a CREW PRAM with time bound D, with M memory cells, and processor bound P, where here s = O( log (PM)) and t = O(D+s),
3. find the satisfying inputs to a Boolean circuit constructible in s space with n inputs, unbounded fan-out, and depth D, where here t = O(D+s).
We also propose a Recombinant DNA (RDNA) model which is a low-level model that allows operations that are abstractions of very well understood recombinant DNA operations and provides a representation, which we call the complex , for the relevant structural properties of DNA. The PA-Match operation for lengthy strings of length s cannot be feasibly implemented by recombinant DNA techniques directly by a single step of complementary pairing in DNA; nevertheless we show this Matching operation can be simulated in the RDNA model with O(s) slowdown by multiple steps of complementary pairing of substrings of length 2 (corresponding to logarithmic length DNA subsequences). Each of the other operations of the PAM model can be executed in our RDNA model, without slowdown. We further show that, with a further O(s)/ log (1/ε) slowdown, the simulations can be done correctly with probability 1/2 even if certain recombinant DNA operations (e.g., Separation) can error with a probability ε. We also observe efficient simulations can be done by PRAMs and thus Turing Machines of our molecular models.