Title :
Fast Parallel Molecular Algorithms for DNA-Based Computation: Graph Isomorphism Problem
Author :
Li, Guo ; Rong, Guan ; Kenli, Li ; Renfa, Li
Author_Institution :
Sch. of Comput. & Commun., Hunan Univ., Changsha, China
Abstract :
The existence DNA computing models can solve most hard NP problems in theory. The graph isomorphism problem is a classical NP-hard problem. In this paper we proposed a DNA-based sticker algorithm, which uses the concept of incidence degree sequence to solve the graph isomorphism problem. The proposed algorithm is simplicity of operation and only O(2n) DNA strands is required in the worst case, where n is the vertex number of a graph.
Keywords :
DNA; biocomputing; computational complexity; graph theory; molecular biophysics; optimisation; DNA based computation; DNA based sticker algorithm; DNA computing models; NP hard problem; graph isomorphism problem; incidence degree sequence; parallel molecular algorithms; Annealing; Biological information theory; Biological system modeling; Biology computing; Concurrent computing; DNA computing; Hydrogen; Power system modeling; Sequences; Splicing;
Conference_Titel :
Biomedical Engineering and Informatics, 2009. BMEI '09. 2nd International Conference on
Conference_Location :
Tianjin
Print_ISBN :
978-1-4244-4132-7
Electronic_ISBN :
978-1-4244-4134-1
DOI :
10.1109/BMEI.2009.5302914
