On the overlap assembly of strings and languages

详细信息    查看全文

• 作者：Srujan Kumar Enaganti ; Oscar H. Ibarra ; Lila Kari ; Steffen Kopecki
• 关键词：Formal language operations ; DNA computing ; Overlap assembly ; Combinatorial libraries
• 刊名：Natural Computing
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：16
• 期：1
• 页码：175-185
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Theory of Computation; Evolutionary Biology; Processor Architectures; Artificial Intelligence (incl. Robotics); Complex Systems;
• 出版者：Springer Netherlands
• ISSN：1572-9796
• 卷排序：16

文摘

This paper investigates properties of the binary string and language operation overlap assembly which was defined by Csuhaj-Varjú, Petre and Vaszil as a formal model of the linear self-assembly of DNA strands: The overlap assembly of two strings, xy and yz, which share an “overlap” y, results in the string xyz. The study of overlap assembly as a formal language operation is part of ongoing efforts to provide a formal framework and rigorous treatment of DNA-based information and DNA-based computation. Other studies along these lines include theoretical explorations of splicing systems, insertion/deletion systems, substitution, hairpin extension, hairpin reduction, superposition, overlapping catenation, conditional concatenation, contextual intra- and intermolecular recombinations, template guided recombination, as well as directed extension by PCR. In this context, we investigate overlap assembly and its properties: closure properties of basic language families under this operation, decision problems, as well as the possible use of iterated overlap assembly to generate combinatorial DNA libraries.