• DocumentCode
    2123378
  • 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
  • fYear
    2009
  • fDate
    17-19 Oct. 2009
  • Firstpage
    1
  • Lastpage
    5
  • 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;
  • fLanguage
    English
  • Publisher
    ieee
  • 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
  • Type

    conf

  • DOI
    10.1109/BMEI.2009.5302914
  • Filename
    5302914
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2123378