Testing DNA code words properties of regular languages

详细信息    查看全文

• 作者：Rocco Zaccagninop>ap>p> ; p>p>zaccagnino@dia.unisa.it" class="auth_mail" title="E-mail the corresponding authorp> ; Rosalba Zizzap>ap>p> ; p>p>zizza@dia.unisa.it" class="auth_mail" title="E-mail the corresponding authorp> ; Carlo Zottoli
• 关键词：DNA computing ; Formal languages ; Regular languages ; Automata theory
• 刊名：Theoretical Computer Science
• 出版年：2015
• 出版时间：10 December 2015
• 年：2015
• 卷：608
• 期：part_P1
• 页码：84-97
• 全文大小：563 K

文摘

One aspect of DNA Computing is the possibility of using DNA molecules for solving some “complicated” computational problems. In this context, the DNA code word design problem assumes a fundamental role: given a problem encoded in DNA strands and biochemical processes, the final computation is a concatenation of the input DNA strands that must allow us to recover the solution of the given problem in terms of the input (unique decipherability). Thus the initial set of DNA strands must be a code. In addition, it should satisfy some restrictions, called here DNA properties, in order to prevent them from interacting in undesirable ways. So a new interest towards the design of efficient algorithms for testing whether a language X is a code, has arisen from (wet) DNA Computing, but, as far as we know, only when X is a finite set. In this paper we provide an algorithm for testing whether an infinite but regular set of words is a code that avoids some DNA properties among unwanted intermolecular and intramolecular hybridizations.