Hairpin Languages
Hairpin Languages
复制标题
发夹语言
DOI：
10.1142/s0129054101000904
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
T. Yokomori
中科院分区：
文献类型：
--
作者：
G. Paun;G. Rozenberg;T. Yokomori
具有发夹结构的分子形成线性非分支分子的自然延伸，并且它们已经用于DNA计算的实验工作中。在本文中，我们介绍和调查类字符串语言（因此语言建模的线性DNA分子集），由字符串，可以（折叠本身和）形成发夹。我们使用语言理论技术对这些类的复杂性进行分类。我们还讨论了发夹分子在DNA计算中的进一步用途。1. D N A计算中的发夹语言Adleman在[1]中报道的DNA计算中的第一个实验中使用的分子是线性无分支DNA分子。本文所开创的DNA计算领域已经发展得非常快，到今天它已经是一个蓬勃发展的跨学科研究领域。DNA计算的重要发展之一是使用了更多的参与分子，这些分子基本上通过自组装过程来执行特定的计算。这些分子中的一些是相当复杂的和“定制的”（参见，例如，[5]，[7]，[8]，[15]，[14]）。837在t。J. F.来吧。斯克岛2001.12：837847.请于2015年1月24日由UN IV E R SI T Y O F N E W E N G L A N D L IB R A R IE S发送。因为你太天真了。838 G. Paun，G.罗森伯格公司Yokomori具有发夹结构的分子形成了线性非分支分子的自然延伸，因为发夹是由线性分子自身折叠而产生的。发夹分子在DNA计算中有很多应用，例如[12]。单链DNA分子的“发夹形成”在解决3SAT问题中的应用在[12]中得到证明。其主要思想可以解释如下。由于问题的目标是决定是否有一个一致的布尔分配满足一个给定的布尔公式在3-CNF，一个必须消除不一致的布尔分配从所有可能的分配的随机池。一个关键的观察是，不是一个给定的公式布尔赋值，可以考虑一个字符串的文字称为文字字符串，是通过选择一个文字从每个子句组成。然后，公式是可满足的，如果有一个文字串，不涉及任何变量及其否定。换句话说，从所有可能的文字字符串的初始随机池中，可以消除那些涉及某些变量及其否定的字符串。如果每个变量都是由一个单链DNA序列编码的，该序列与编码它的否定的序列互补，那么那些包含至少一对互补文字的文字串可以形成发夹，而其他文字串（对应于满足赋值）保持非发夹形式。因此，发夹结构在此用于选择“溶液分子”。发夹计算能力的另一个证明可以在基于自组装YAC的分子计算模型的理论工作中找到（[16]）。与其他基于自组装原理的计算模型不同，该模型接收模型接受的输入字符串（如图灵机计算）。每个线性文法计算规则由一个二维块编码，计算过程由这些块的线性组合表示。YAC通过生成许多编码这些计算的长单链分子来模拟给定输入的所有可能的计算，并且在最终计算过程中评估输入，其中“发夹形成”有效地用于仅选择“有效（成功）计算过程”。应该注意的是，上面提到的两个计算模型共享一个共同的计算模式（其遵循称为“过滤”的一般计算策略，并且在[9]中通过“雕刻计算”在语言理论术语中形式化）：（i）首先制备分子的初始随机池，（ii）然后从池中仅提取具有（或不具有）发夹形成的目标分子。这就引出了下面的问题：一般什么样的问题可以用这样的模式来计算？换句话说：这个计算模式有多强大？对这个问题的研究使人们考虑一组含有潜在发夹结构的互补序列的弦分子，也就是说，一组含有一对互补序列的弦。本文考虑了几种类型的“发夹语言”，并研究其语言理论的复杂性（使用乔姆斯基层次）。本文的结构如下。第2节给出了简要说明。在第3节中，我们用公式表示t中的类型。J. F.来吧。斯克岛2001.12：837847.请于2015年1月24日由UN IV E R SI T Y O F N E W E N G L A N D L IB R A R IE S发送。因为你太天真了。发夹语言839发夹语言，我们将调查和建立基本发夹语言的语言理论复杂性。由于“发夹过滤”是通过取发夹语言的补语来形式化的，所以在第四节中我们研究了基本发夹语言的补语。在第5节中，我们讨论了发夹语言在YAC模型中的使用。在第6节中，我们概述了使用发夹计算解决汉密尔顿路径问题。
Molecules with hairpin structure(s) form a natural extension of linear non-branched molecules, and they have been already used in experimental work in DNA computing. In this paper we introduce and investigate classes of string languages (hence languages modeling the sets of linear DNA molecules), consisting of strings which can (fold on itself and) form hairpins. We classify the complexity of these classes using language-theoretic techniques. We also discuss a further use of hairpin molecules in DNA computing. 1. Hairpin Languages in D N A Computing The molecules used in the first experiment in DNA computing reported by Adleman in [1] were linear non-branching DNA molecules. The area of DNA computing initiated by this paper has grown very much, and by today it is a thriving interdisciplinary research area. One of the important developments in DNA computing was the use of more involved molecules, which do perform specific computations essentially through the process of self-assembly. Some of these molecules are quite sophisticated and "custom made" (see, e.g., [5], [7], [8], [15], [14]). 837 In t. J. F ou nd . C om pu t. Sc i. 20 01 .1 2: 83 784 7. D ow nl oa de d fr om w w w .w or ld sc ie nt if ic .c om by U N IV E R SI T Y O F N E W E N G L A N D L IB R A R IE S on 0 1/ 24 /1 5. F or p er so na l u se o nl y. 838 G. Paun, G. Rozenberg & T. Yokomori Molecules with hairpin structure(s) form a natural extension of linear nonbranched molecules, because a hairpin results from a linear molecule that folds on itself. Hairpin molecules found quite many applications in DNA computing see, for instance, [12]. The use of "hairpin formation" of single-stranded DNA molecules in solving 3SAT problems is demonstrated in [12]. The main idea can be explained as follows. Since the goal of the problem is to decide whether or not there is a consistent Boolean assignment satisfying a given Boolean formula in 3-CNF, one has to eliminate inconsistent Boolean assignments from the random pool of all possible assignments. A key observation is that, instead of a Boolean assignment to a given formula, one can consider a string of literals called a literal string that is composed by selecting one literal from each clause. Then, a formula is satisfiable if there is a literal string that does not involve any variable together with its negation. In other words, from the initial random pool of all possible literal strings one can eliminate those which involve some variable together with its negation. If each variable is encoded by a single-stranded DNA sequence complementary to that encoding its negation, then those literal strings involving-at least one pair of complementary literals can form a hairpin, while other literal strings (corresponding to satisfying assignments) remain in a non-hairpin form. Thus, the hairpin structure is used here o select "solution molecules". Another demonstration of the power of hairpin computation can be found in a theoretical work on the model of molecular computing based on self-assembly YAC ([16]). Unlike other models of computation based on the self-assembly principle, this model receives an input string to be accepted by the model (like a Turing machine computation). Each linear grammar-like rule of computation is encoded by a two dimensional block, and a computation process is represented by a linear composition of those blocks. YAC simulates all possible computations for the given input, by generating many long single-stranded molecules encoding these computations, and the input is evaluated during the final computation process, where "hairpin formation" is effectively used to select only "valid (successful) computation processes". It should be noted that the two computation models mentioned above share a common computation schema (which follows the general computation strategy called "filtering" and formalized in language theoretic terms by "computing by carving" in [9]): (i) first preparing the initial random pool of molecules, (ii) then extracting only target molecules with (or without) hairpin formation from the pool. This leads to the following question: what sort of problems in general can be computed by such a schema? In other words: how powerful is this computation schema? Investigating this question leads one to consider sets of string molecules which contain complementary sequences of potential hairpin formations, that is, the set of strings containing a pair of complementary subsequences. This paper considers several types of such "hairpin languages" and investigates their language theoretic complexity (using the Chomsky hierarchy). The paper is organized as follows. Brief preliminaries are given in Section 2. In Section 3 we formulate the types In t. J. F ou nd . C om pu t. Sc i. 20 01 .1 2: 83 784 7. D ow nl oa de d fr om w w w .w or ld sc ie nt if ic .c om by U N IV E R SI T Y O F N E W E N G L A N D L IB R A R IE S on 0 1/ 24 /1 5. F or p er so na l u se o nl y. Hairpin Languages 839 of hairpin languages that we will investigate and establish the language theoretic complexity of the basic hairpin languages. Since "filtering by hairpin" is formalized through taking the complements of hairpin languages, the complements of our basic hairpin languages are investigated in Section 4. In Section 5 we discuss the use of hairpin languages in the YAC model. In Section 6 we outline the use of hairpin computation for solving the Hamiltonian path problem.