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.

DNA graph structures can self-assemble from branched junction molecules to yield solutions to computational problems. Self-assembly of graphs have previously been shown to give polynomial time solutions to hard computational problems such as 3-SAT and k-colorability problems. Jonoska et al. have proposed studying self-assembly of graphs topologically, considering the boundary components of their thickened graphs, which allows for reading the solutions to computational problems through reporter strands. We discuss weighting algorithms and consider applications of self-assembly of graphs and the boundary components of their thickened graphs to problems involving minimal weight Eulerian walks such as the Chinese Postman Problem and the Windy Postman Problem.

The behavior of the Deoxyribonucleic Acid (DNA) molecule can be exploited to perform useful computation. It can also be ”programmed” using the language of Chemical Reaction Networks (CRNs). One specialized CRN construct is the Surface Chemical Reaction Network (SCRN). The SCRN construct can implement asynchronous cellular automata, which can in turn be used to implement digital logic circuits. SCRN based digital logic circuits are thought to have several advantages over regular CRN circuits. One of these proposed advantages is their scalability. This thesis investigates the scalability of SCRN based adder circuits, how does an increase in the number of bits affect the time required for the circuit to produce a correct result? Additionally, how is the throughput of the circuit affected when multiple additions are performed in a pipelined fashion? These questions are studied through experiments where the execution of optimized SCRN adder circuits is simulated. Due to the stochastic nature of SCRNs each such execution is all but guaranteed to be unique, requiring the simulation of the circuits to be repeated until a sufficiently large statistical sample has been collected. The results show these samples to follow a Gaussian distribution, regardless of the number of bits or the number of pipelined operations. The experiments show the simulated latency of the studied SCRN adder circuits to scale linearly with the number of input bits. The results also show that the throughput can be greatly improved through the pipelining of multiple operations. However, the results are inconclusive as to the maximum possible throughput of SCRN adder circuits. A conclusion of the project is that SCRN digital logic circuit design could conceivably benefit from the implementation of specialized components beyond the standard logic gates. / DNA-molekylen kan utnyttjas för att genomföra användbara beräkningar. Den kan också ”programmeras” via abstraktionen kemiska reaktionsnätverk. Ytbundna Kemiska Reaktionsnätverk (YKR) är i sin tur en vidare specialisering av sådana reaktionsnätverk. Ett YKR kan implementera en asynkrona cellulära automat, som i sin tur kan implementera kretsar för digital logik. Kretsar för digital logik byggda med YKR anses ha flera fördelar gentemot motsvarande kretsar byggda från vanliga kemiska reaktionsnätverk. En av dessa tilltänkta fördelar ligger i deras skalbarhet. Detta examensarbete undersöker skalbarheten hos YKR-baserade additions-kretsar, hur påverkar ett ökat antal bitar tiden som krävs för att kretsen ska producera ett korrekt resultat? Vidare, hur påverkas genomströmningen när flera operationer matas in direkt och genomför efter varandra i en pipeline? Dessa frågor studeras genom experiment där körningar av optimerande YKR-baserade additionskretsar simuleras. På grund av de stokastiska egenskaperna hos YKR är varje sådan körning i princip garanterad att vara unik, vilket kräver upprepade simuleringar av varje krets tills ett tillräckligt stort statistiskt urval har insamlats. Dessa resultat visar sig följa en normalfördelningskurva, oavsett antalet bitar eller antalet operationer som matats in i en pipeline. Experimenten visar att den simulerade latensen skalar linjärt med antalet indata-bitar för de studerade additionskretsarna. Resultaten visar även att genomströmningen förbättras avsevärt när flera operationer körs direkt efter varandra i en pipeline. Resultaten är dock ofullständiga när det gäller uppmätandet av additionskretsarna högsta möjliga genomströmning. En slutsats av projektet är att YKR-baserade kretsar för digital logik möjligen skulle kunna gagnas av implementerandet av specialiserade komponenter utöver de vanliga logikgrindarna.