Fast Parallel Molecular Algorithms for DNA-Based Computation: Graph Isomorphism Problem
- Resource Type
- Conference
- Authors
- Li, Guo; Rong, Guan; Kenli, Li; Renfa, Li
- Source
- 2009 2nd International Conference on Biomedical Engineering and Informatics Biomedical Engineering and Informatics, 2009. BMEI '09. 2nd International Conference on. :1-5 Oct, 2009
- Subject
- Bioengineering
Computing and Processing
Communication, Networking and Broadcast Technologies
Concurrent computing
DNA computing
Biology computing
Biological system modeling
Sequences
Power system modeling
Biological information theory
Annealing
Splicing
Hydrogen
- Language
- ISSN
- 1948-2914
1948-2922
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(2 n ) DNA strands is required in the worst case, where n is the vertex number of a graph.