TAK Tiles

TAK Tiles are a Hamming code based error detection system for DNA computing that work in Order(1) with exactly 32 Wang tiles based on the Wang Tile Model for DNA Self Assembly. They take as input a Hamming coded string representing an output from any other DNA Nanotechnology system, and output the parity bits to demonstrate the validity of the Hamming coded input string. The system works at temperature 2 by assembling into a log(L − D) × L rectangular module, similar to a binary counter, where L is the length of the Hamming code, and D is the number of data bits.

Background

In the emerging field of DNA computing, there has been a necessity for mechanisms that correct or detect the errors that occur in the combining of the DNA. Such errors can occur due to unintended and incomplete attachments of a strand with another strand. When using the DNA strands to do some type of a numerical computation it is therefore important to identify if the computation occured correctly. A well known mechanism for error detection in electrical engineering has been the use of Hamming codes. TAK Tiles extend the use of Hamming codes to detect errors that occur in the computation performed with DNA as well.

Temperature

Temperature plays an important role in any chemical reaction in determining whether or not there is enough energy to activate the reaction. In developing a Wang Tile Model for DNA computing in order to maintain clarity the temperature of the system is designated by numbers like 1, 2, or 3 instead of in absolute temperatures. The tile glues in the model are then developed such that they will hold up to a certain temperature, and will break down at higher temperatures.

Previous Systems

Tile Proofreading

Snake Tiles Error Free Self-Assembly using Error Prone Tiles

Advantages of TAK Tiles

This Order(1) algorithm is a notable improvement over the previous error detection/correction systems which generally work in Order(n^2) in the context of DNA or Molecular self-assembly, or at least require an increasing amount of tile types as the size of the system grows.

This system is modular so that it can work in conjunction with other systems.

Purpose

In order to eventually establish a DNA computer we would like to build up the various pieces of the computer from full adders and multipliers to multiplexers and so forth. We can expect many components that we make to require the use of TAK Tiles in order to eventually establish the robustness of the DNA computer.

History

This particular system was devised by ICME, Stanford University students Aditya Mittal, Tiyu Wang, and Kathryn Hymes under the guidance of Professor Ashish Goel for a Molecular Algorithms class. The original ideas used to solve this problem were based on Aditya's undergraduate computer engineering classes by Professor Ehat Ercanli at Syracuse University. Particular details of the problem were resolved by Tiyu Wang. Kathryn Hymes presented the work on behalf of the team at 14th International Meeting on DNA Computing in Prague, Czech Republic.

See Also

DNA Nanotechnology

DNA Computing

Error Detection

Main Menu