A computação com DNA é um campo da Bioinformática que, através da manipulação de seqüências de DNA, busca a solução de problemas. Em 1994, o matemático Leonard Adleman, utilizando operações biológicas e manipulação de seqüências de DNA, solucionou uma instância de um problema intratável pela computação convencional, estabelecendo assim, o início da computação com DNA. Desde então, uma série de problemas combinatoriais vem sendo solucionada através deste modelo de programação. Este trabalho analisa a computação com DNA, com o objetivo de traçar algumas linhas básicas para quem deseja programar nesse ambiente. Para isso, são apresentadas algumas vantagens e desvantagens da computação com DNA e, também, alguns de seus métodos de programação encontrados na literatura. Dentre os métodos estudados, o método de filtragem parece ser o mais promissor e, por isso, uma metodologia de programação, através deste método, é estabelecida. Para ilustrar o método de Filtragem Seqüencial, são mostrados alguns exemplos de problemas solucionados a partir deste método. / DNA computing is a field of Bioinformatics that, through the manipulation of DNA sequences, looks for the solution of problems. In 1994 the mathematician Leonard Adleman, using biological operations and DNA sequences manipulation, solved an instance of a problem considered as intractable by the conventional computation, thus establishing the beginning of the DNA computing. Since then, a series of combinatorial problems were solved through this model of programming. This work studies the DNA computing, aiming to present some basic guide lines for those people interested in this field. Advantages and disadvantages of the DNA computing are contrasted and some methods of programming found in literature are presented. Amongst the studied methods, the filtering method appears to be the most promising and for this reason it was chosen to establish a programming methodology. To illustrate the sequential filtering method, some examples of problems solved by this method are shown.

A área de biologia computacional está vivendo um crescimento rápido causado pela revolução no estudo de genômas e pelo avanço das técnicas de manipulação do material genético. Com essas novas tecnologias para manipulação de seqüências, a importância de achar uma solução eficiente para os problemas chamados de intratáveis também cresceu, pois muitos problemas envolvidos na análise de DNA pertencem a essa classe de problemas. Uma abordagem para achar essas soluções é usar o próprio DNA para realizar computação, aproveitando o paralelismo massivo utilizado em operações que manipulam seqüências de DNA. Isto é estudado na área de computação com DNA. Esse trabalho propõe um modelo formal para representar a estrutura da molécula de DNA e das operações que são realizadas com ela em laboratório. Este modelo ajuda a preencher a necessidade de uma descrição matemática que possa ser usada para analisar algoritmos baseados em DNA, assim como possibilitar a simulaç~o desses algoritmos em um computador. Foi utilizada a teoria de gramáticas de grafos, uma linguagem de especificação formal, para modelar as seqüências de DNA e suas I operações. O trabalho apresenta um estudo da estrutura da molécula de DNA, deScrevendo suas características e as principais operações que são realizadas para sua manipulação em laboratório. Uma descrição da teoria de Gramática de Grafos e sua aplicação também é apresentada. Para validação do modelo proposto as especificações resultantes foram adaptadas para o formato L-systems, outra linguagem de especificação formal, permitindo realizar a simulação da especificação no ambiente L-Studio. / The area of computational biology is living a fast growth, fed with a revolution in the study of genomes and with the advance in the techniques of genetic material manipulation. With these new technologies for manipulation of sequences, the relevance of finding efficient solution to the so-called computer intractable problems has also grown, because many problems involved in analyzing DNA belong to this class of problems. One approach to find such solutions is to use DNA itself to perform computations, taking advantage of the massive parallelism involved in operations that manipulate DNA sequences. This is what is studied in the area ofDNA computing. This work proposes a formal model to represent the DNA structure and the operations performed in laboratory with it. This model helps to fill the need of a mathematical description that can be used to analyze DNA-based algorithms, as well as for simulating such algorithms in a computer. We use graph grammars, a formal specification language, to model the DNA sequences and operations. The work presents a study of the DNA molecule structure, describing its features and the main operations performed for manipulation in laboratory. A description of the theory of Graph Grammars and its application are presented too. To validate the proposed model, the resulting DNA-graph grammar specifications are then translated into the L-systems format, another formal specification language, allowing for the simulation of the specifications using the L-Studio environment.

A área de biologia computacional está vivendo um crescimento rápido causado pela revolução no estudo de genômas e pelo avanço das técnicas de manipulação do material genético. Com essas novas tecnologias para manipulação de seqüências, a importância de achar uma solução eficiente para os problemas chamados de intratáveis também cresceu, pois muitos problemas envolvidos na análise de DNA pertencem a essa classe de problemas. Uma abordagem para achar essas soluções é usar o próprio DNA para realizar computação, aproveitando o paralelismo massivo utilizado em operações que manipulam seqüências de DNA. Isto é estudado na área de computação com DNA. Esse trabalho propõe um modelo formal para representar a estrutura da molécula de DNA e das operações que são realizadas com ela em laboratório. Este modelo ajuda a preencher a necessidade de uma descrição matemática que possa ser usada para analisar algoritmos baseados em DNA, assim como possibilitar a simulaç~o desses algoritmos em um computador. Foi utilizada a teoria de gramáticas de grafos, uma linguagem de especificação formal, para modelar as seqüências de DNA e suas I operações. O trabalho apresenta um estudo da estrutura da molécula de DNA, deScrevendo suas características e as principais operações que são realizadas para sua manipulação em laboratório. Uma descrição da teoria de Gramática de Grafos e sua aplicação também é apresentada. Para validação do modelo proposto as especificações resultantes foram adaptadas para o formato L-systems, outra linguagem de especificação formal, permitindo realizar a simulação da especificação no ambiente L-Studio. / The area of computational biology is living a fast growth, fed with a revolution in the study of genomes and with the advance in the techniques of genetic material manipulation. With these new technologies for manipulation of sequences, the relevance of finding efficient solution to the so-called computer intractable problems has also grown, because many problems involved in analyzing DNA belong to this class of problems. One approach to find such solutions is to use DNA itself to perform computations, taking advantage of the massive parallelism involved in operations that manipulate DNA sequences. This is what is studied in the area ofDNA computing. This work proposes a formal model to represent the DNA structure and the operations performed in laboratory with it. This model helps to fill the need of a mathematical description that can be used to analyze DNA-based algorithms, as well as for simulating such algorithms in a computer. We use graph grammars, a formal specification language, to model the DNA sequences and operations. The work presents a study of the DNA molecule structure, describing its features and the main operations performed for manipulation in laboratory. A description of the theory of Graph Grammars and its application are presented too. To validate the proposed model, the resulting DNA-graph grammar specifications are then translated into the L-systems format, another formal specification language, allowing for the simulation of the specifications using the L-Studio environment.

A computação com DNA é um campo da Bioinformática que, através da manipulação de seqüências de DNA, busca a solução de problemas. Em 1994, o matemático Leonard Adleman, utilizando operações biológicas e manipulação de seqüências de DNA, solucionou uma instância de um problema intratável pela computação convencional, estabelecendo assim, o início da computação com DNA. Desde então, uma série de problemas combinatoriais vem sendo solucionada através deste modelo de programação. Este trabalho analisa a computação com DNA, com o objetivo de traçar algumas linhas básicas para quem deseja programar nesse ambiente. Para isso, são apresentadas algumas vantagens e desvantagens da computação com DNA e, também, alguns de seus métodos de programação encontrados na literatura. Dentre os métodos estudados, o método de filtragem parece ser o mais promissor e, por isso, uma metodologia de programação, através deste método, é estabelecida. Para ilustrar o método de Filtragem Seqüencial, são mostrados alguns exemplos de problemas solucionados a partir deste método. / DNA computing is a field of Bioinformatics that, through the manipulation of DNA sequences, looks for the solution of problems. In 1994 the mathematician Leonard Adleman, using biological operations and DNA sequences manipulation, solved an instance of a problem considered as intractable by the conventional computation, thus establishing the beginning of the DNA computing. Since then, a series of combinatorial problems were solved through this model of programming. This work studies the DNA computing, aiming to present some basic guide lines for those people interested in this field. Advantages and disadvantages of the DNA computing are contrasted and some methods of programming found in literature are presented. Amongst the studied methods, the filtering method appears to be the most promising and for this reason it was chosen to establish a programming methodology. To illustrate the sequential filtering method, some examples of problems solved by this method are shown.

This dissertation focuses on rationalised DNA design as a tool for the discovery and development of new therapeutic entities, as well as understanding the biological function of DNA beyond the storage of genetic information. The study is comprised of two main areas of study: (i) the use of DNA as a coding unit to illustrate the relationship between code-diversity and dynamics of self-assembly; and (ii) the use of DNA as an active unit that interacts and regulates a target protein. In the study of DNA as a coding unit in code-diversity and dynamics of self-assembly, we developed the DNA-Based Diversity Modelling and Analysis (DDMA) method. Using Polymerase Chain Reaction (PCR) and Real Time Polymerase Chain Reaction (RT-PCR), we studied the diversity and evolution of synthetic oligonucleotide populations. The manipulation of critical conditions, with monitoring and interpretation of their effects, lead to understanding how PCR amplification unfolding could reshape a population. This new take on an old technology has great value for the study of: (a) code-diversity, convenient in a DNA-based selection method, so semi-quantitation can evaluate a selection development and the population\'s behaviour can indicate the quality; (b) self-assembly dynamics, for the simulation of a real evolution, emulating a society where selective pressures direct the population's adaptation; and (c) development of high-entropy DNA structures, in order to understand how similar unspecific DNA structures are formed in certain pathologies, such as in auto-immune diseases. To explore DNA as an active unit in Tumour Necrosis Factor α (TNF-α) interaction and activity modulation, we investigate DNA's influence on its spatial conformation by physical environment regulation. Active TNF-α is a trimer and the protein-protein interactions between its monomers are a promising target for drug development. It has been hypothesised that TNF-α forms a very intricate network after its activation between its subunits and receptors, but the mechanism is still not completely clear. During our research, we estimate the non-specific DNA binding to TNF-α in the low micro-molar range. Cell toxicity assays confirm this interaction, where DNA consistently enhances TNF-α's cytotoxic effect. Further binding and structural studies lead to the same conclusion that DNA binds and interferes with TNF-α structure. From this protein-DNA interaction study, a new set of tools to regulate TNF-α's biological activity can be developed and its own biology can be unveiled.

In dieser Arbeit wird ein Modell zum Aufzählen von DNA-Codes entwickelt. Indem eine Ordnung auf der Menge aller DNA-Codewörter eingeführt und auf die Menge aller Codes erweitert wird, erlaubt das Modell das Auffinden von DNA-Codes mit bestimmten Eigenschaften, wie Überlappungsfreiheit, Konformität, Kommafreiheit, Stickyfreiheit, Überhangfreiheit, Teilwortkonformität und anderer bezüglich einer gegebenen Involution auf der Menge der Codewörter. Ein auf Grundlage des geschaffenen Modells entstandenes Werkzeug erlaubt das Suchen von Codes mit beliebigen Kombinationen von Codeeigenschaften. Ein weiterer wesentlicher Bestandteil dieser Arbeit ist die Untersuchung der Optimalität von DNA-Codes bezüglich ihrer Informationsrate sowie das Finden solider DNA-Codes. / In this work a model for enumerating DNA codes is developed. By applying an order on the set of DNA codewords and extending this order on the set of codes, this model assists in the discovery of DNA codes with properties like non-overlappingness, compliance, comma-freeness, sticky-freeness, overhang-freeness, subword-compliance, solidness and others with respect to a given involution on the set of codewords. This tool can be used to find codes with arbitrary combinations of code properties with respect to the standard Watson-Crick-DNA involution. The work also investigates DNA codes with respect to the optimizing of the information rate, as well as finding solid DNA codes.

Glioblastoma multiforme (GBM) is a debilitating malignant brain tumor with expected patient survival of less than a year and limited responsiveness to most treatments, often requiring biopsy for diagnosis and invasive surgery for treatment. We propose a DNA computer system, consisting of input, computation, and output components, for diagnosis and treatment. The input component will detect the presence of three GBM biomarkers: vascular endothelial growth factor (VEGF), caveolin-1α (CAV), and B2 receptors. The computation component will include indicator segments for each of these genes, and ensure that output is only released if all the biomarkers are present. The output component will consist of the therapeutic agent interleukin-12 (IL-12). This study will designate four groups of animals: untreated tumor-free (control), tumor-inoculated (RG2), treated and tumor-free (DNA), and treated and tumor-inoculated (RG2/DNA). In the RG2 and RG2/DNA groups, we will inoculate adult male Fischer rats with RG2 cells into the striatum to induce tumor growth. Rats in the DNA and RG2/DNA groups will be implanted with the DNA system at the same location via recombinant adeno- associated viral vectors. The effectiveness of the DNA system will be evaluated through tumor size measurements, collected from brain slices stained with hematoxylin and eosin, and survival curve. Additionally, IL-12 localization will confirm the release of the output component. We anticipate that the DNA treatment will result in a decrease in tumor size, leading to smaller tumor size in the RG2/DNA group versus the RG2 group. The control group is expected to survive the longest, followed by the DNA group, then the RG2/DNA group, and finally the RG2 group. In the DNA group, IL-12 is expected to stay localized to the implantation site, remaining in its unreleased stem-loop form. On the other hand, it is expected to be released and active in the RG2/DNA group. This study provides a proof of concept to demonstrate the viability and effectiveness of a DNA system using VEGF, CAV, and B2 receptors as biomarkers and IL-12 as a therapeutic output component in the RG2 model. Further research may include varying several of the parameters used in this study, including amount of RG2 administered, choice of biomarkers, quantity and choice of output component, and choice of animal model. This system provides a promising and innovative new approach that is less invasive than surgery yet is still effective in diagnosing, targeting, and treating GBM.

The rapid developments in the field of DNA computing reflects two substantial questions: 1. Which models for DNA based computation are really universal? 2. Which model fulfills the requirements to a universal lab-practicable programmable DNA computer that is based on one of these models? This paper introduces the functional model DNA-HASKELL focussing its lab-practicability. This aim could be reached by specifying the DNA based operations in accordiance to an analysis of molecular biological processes. The specification is determined by an abstraction level that includes nucleotides and strand end labels like 5'-phosphate. Our model is able to describe DNA algorithms for any NP-complete problem - here exemplified by the knapsacik problem - as well as it is able to simulate some established mathematical models for computation. We point out the splicing operation as an example. The computational completeness of DNA-HASKELL can be supposed. This paper is based on discussions about the potenzial and limits of DNA computing, in particular the practicability of a universal DNA computer.

Experiments have demonstrated that DNA molecules can compute like a machine to solve mathematical problems, which is significant because of their parallel computation ability. However, due to the nature of biochemical reactions, DNA computation suffers from errors, which are its main limitation. The abstract and kinetic Tile Assembly Models are now commonly used to simulate real DNA computing experiments, and to look for new methods to advance the accuracy of DNA-based computation. One means of controlling errors is through proofreading tile sets. Several such tile sets have been proposed in the literature, such as Chen and Goel’s snaked proofreading tile sets, the 2-way and 3-way overlay tile sets of Reif et al., and Rothemund and Cook’s n-way overlay tile sets. In the first part of this thesis, we analyze the performance of the Rothemund-Cook n-way overlay tile sets. We prove that the n-way overlay tile set contains n^2+3n+4 rule tiles. Simulation results show that these tile sets clearly perform better than tile sets without any error-control mechanism, and the performance improves as n increases. It is also proved that the error rates in assemblies formed by the 1-way and 2-way tile sets are O(epsilon^2), where epsilon is the error rate in assemblies without any error correction. In the second part of this thesis, we focus on a different error mechanism, namely,errors caused by imperfect or malformed tiles. We propose a model of malformed tiles, and consider the performance of various proofreading tile sets in the presence of malformed tiles. Our simulation results show that the Reif et al. 3-way overlay tile sets are able to best deal with malformed tiles. During the simulations, we observed that snaked proofreading tile sets always have trouble completing whole patterns when malformed tiles are present. We instead propose two modified snaked proofreading constructions, and verify through both simulations and analysis that the two modified constructions have much better performances. / Thesis (Master, Mathematics & Statistics) -- Queen's University, 2009-08-25 11:10:39.142

This thesis focuses on the design and implementation of an application involving the principles of DNA computing simulation for solving some selected problems. DNA computing represents an unconventional computing paradigm that is totally different from the concept of electronic computers. The main idea of DNA computing is to interpret the DNA as a medium for performing computation. Despite the fact, that DNA reactions are slower than operations performed on computers, they may provide some promising features in the future. The DNA operations are based on two important aspects: massive parallelism and principle of complementarity. There are many important problems for which there is no algorithm that would be able to solve the problem in a polynomial time using conventional computers. Therefore, the solutions of such problems are searched by exploring the entire state space. In this case the massive parallelism of the DNA operations becomes very important in order to reduce the complexity of finding a solution.