Solving Vertex Cover Problem Using DNA Tile Assembly Model
DNA tile assembly models are a class of mathematically distributed and parallel biocomputing models in DNA tiles. In previous works, tile assembly models have been proved be Turing-universal; that is, the system can do what Turing machine can do. In this paper, we use tile systems to solve computati...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2013-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2013/407816 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832568352686473216 |
|---|---|
| author | Zhihua Chen Tao Song Yufang Huang Xiaolong Shi |
| author_facet | Zhihua Chen Tao Song Yufang Huang Xiaolong Shi |
| author_sort | Zhihua Chen |
| collection | DOAJ |
| description | DNA tile assembly models are a class of mathematically distributed and parallel biocomputing models in DNA tiles. In previous works, tile assembly models have been proved be Turing-universal; that is, the system can do what Turing machine can do. In this paper, we use tile systems to solve computational hard problem. Mathematically, we construct three tile subsystems, which can be combined together to solve vertex cover problem. As a result, each of the proposed tile subsystems consists of Θ(1) types of tiles, and the assembly process is executed in a parallel way (like DNA’s biological function in cells); thus the systems can generate the solution of the problem in linear time with respect to the size of the graph. |
| format | Article |
| id | doaj-art-4816d506da8a4eefb4514b1f9bf1e949 |
| institution | Kabale University |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2013-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-4816d506da8a4eefb4514b1f9bf1e9492025-02-03T00:59:17ZengWileyJournal of Applied Mathematics1110-757X1687-00422013-01-01201310.1155/2013/407816407816Solving Vertex Cover Problem Using DNA Tile Assembly ModelZhihua Chen0Tao Song1Yufang Huang2Xiaolong Shi3Key Laboratory of Image Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan, Hubei 430074, ChinaKey Laboratory of Image Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan, Hubei 430074, ChinaKey Laboratory of Image Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan, Hubei 430074, ChinaKey Laboratory of Image Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan, Hubei 430074, ChinaDNA tile assembly models are a class of mathematically distributed and parallel biocomputing models in DNA tiles. In previous works, tile assembly models have been proved be Turing-universal; that is, the system can do what Turing machine can do. In this paper, we use tile systems to solve computational hard problem. Mathematically, we construct three tile subsystems, which can be combined together to solve vertex cover problem. As a result, each of the proposed tile subsystems consists of Θ(1) types of tiles, and the assembly process is executed in a parallel way (like DNA’s biological function in cells); thus the systems can generate the solution of the problem in linear time with respect to the size of the graph.http://dx.doi.org/10.1155/2013/407816 |
| spellingShingle | Zhihua Chen Tao Song Yufang Huang Xiaolong Shi Solving Vertex Cover Problem Using DNA Tile Assembly Model Journal of Applied Mathematics |
| title | Solving Vertex Cover Problem Using DNA Tile Assembly Model |
| title_full | Solving Vertex Cover Problem Using DNA Tile Assembly Model |
| title_fullStr | Solving Vertex Cover Problem Using DNA Tile Assembly Model |
| title_full_unstemmed | Solving Vertex Cover Problem Using DNA Tile Assembly Model |
| title_short | Solving Vertex Cover Problem Using DNA Tile Assembly Model |
| title_sort | solving vertex cover problem using dna tile assembly model |
| url | http://dx.doi.org/10.1155/2013/407816 |
| work_keys_str_mv | AT zhihuachen solvingvertexcoverproblemusingdnatileassemblymodel AT taosong solvingvertexcoverproblemusingdnatileassemblymodel AT yufanghuang solvingvertexcoverproblemusingdnatileassemblymodel AT xiaolongshi solvingvertexcoverproblemusingdnatileassemblymodel |