Three Dimensional DNA Self-Assembly Model for the Minimum Vertex Cover Problem

Author

Zhang, Xuncai ; Song, Wenjun ; Fan, Ruili ; Cui, Guangzhao

Author_Institution

Coll. of Electr. & Electron. Eng., Zhengzhou Univ. of Light Ind., Zhengzhou, China

Volume

1

fYear

2011

fDate

28-30 Oct. 2011

Firstpage

348

Lastpage

351

Abstract

DNA self-assembly technology has brought novel inspiration to the development of DNA computing. Diversified computational models based on DNA self-assembly have been used to solve various NP problems. In this paper, a three-dimensional (3D) DNA self-assembly model is presented to solve the minimum vertex cover problem. With the capacity of DNA molecules in massive parallel computation, the model can simulate a non-deterministic algorithm and solve the problem in polynomial time. Meanwhile, the computation space of the model is O(n3) and the number of distinct tiles is O(1).

Keywords

biocomputing; computational complexity; DNA computing; NP problems; diversified computational models; minimum vertex cover problem; three dimensional DNA self-assembly model; Assembly; Computational modeling; DNA; Self-assembly; Solid modeling; Three dimensional displays; Tiles; DNA Computing; DNA Self-Assembly; Minimum Vertex Cover; Non-Deterministic Algorithm;

fLanguage

English

Publisher

ieee

Conference_Titel

Computational Intelligence and Design (ISCID), 2011 Fourth International Symposium on

Conference_Location

Hangzhou

Print_ISBN

978-1-4577-1085-8

Type

conf

DOI

10.1109/ISCID.2011.94

Filename

6079703