DNA implementation of k-shortest paths computation

Author

Ibrahim, Zuwairie ; Tsuboi, Yusei ; Muhammad, Mohd Saufee ; Ono, Osamu ; Khalid, Marzuki

Author_Institution

Inst. of Appl. DNA Comput., Meiji Univ., Kawasaki

Volume

1

fYear

2005

fDate

5-5 Sept. 2005

Firstpage

707

Abstract

In this paper, a demonstration of DNA computing for k-shortest paths of a weighted graph is realized by biochemical experiments in such a way that every path is encoded by oligonucleotides and the length of the path is directly proportional to the length of oligonucleotides. For initial pool generation, parallel overlap assembly is employed for efficient generation of all candidate answers. During the computation, after the initial pool of solution is subjected to amplification, which is polymerase chain reaction, k-shortest paths could be separated by gel electrophoresis and the selection can be made at last

Keywords

biocomputing; electrophoresis; graph theory; DNA computing; biochemical experiment; gel electrophoresis; k-shortest path computation; oligonucleotides; parallel overlap assembly; polymerase chain reaction; weighted graph; Assembly; Business; Cities and towns; DNA computing; Electrokinetics; In vitro; Molecular computing; Polymer gels; Sequences; Temperature;

fLanguage

English

Publisher

ieee

Conference_Titel

Evolutionary Computation, 2005. The 2005 IEEE Congress on

Conference_Location

Edinburgh, Scotland

Print_ISBN

0-7803-9363-5

Type

conf

DOI

10.1109/CEC.2005.1554752

Filename

1554752