DNA Encoding for Solving the NP problems

被引：1
作者：
Liu Xikui [1 ]
Li Yan [1 ]
机构：
[1] Shandong Univ Sci & Technol, Coll Informat & Engn, Qingdao 266510, Peoples R China
来源：
PROCEEDINGS OF THE 27TH CHINESE CONTROL CONFERENCE, VOL 3 | 2008年
关键词：
DNA encoding; Helix twist angle distance; Immune GA;
D O I：
10.1109/CHICC.2008.4605491
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Most existing DNA computing methods follow the Adleman's coding scheme to solve NP-complete problems. Effective encoding can reduce the false hybridization. Helix twist angle distances describe quantitatively difference of helix twist angles. In this paper, by translating helix twist angle distance function into proper constraint term, the new evaluation formula of every DNA individual corresponding to the selected constraint term is proposed. Immune genetic algorithm is presented to solve the problem, and the better DNA sequences arc found. By comparing experimental data with the previous data, we find that the sequences generated by helix twist angle distance function satisfy simultaneously the constraint terms of Hamming distance, reverse Hamming distance and reverse-complement Hamming distance. Accordingly, the complexity of encoding problem is reduced.
引用
收藏
页码：336 / 340
页数：5
相关论文
共 13 条
  • [1] MOLECULAR COMPUTATION OF SOLUTIONS TO COMBINATORIAL PROBLEMS
    ADLEMAN, LM
    [J]. SCIENCE, 1994, 266 (5187) : 1021 - 1024
  • [2] Deaton R., 1998, COMPUTING BIOMOLECUL, P138
  • [3] DEATON R, 1997, P 2 ANN C CAL, P463
  • [4] Deaton R., 1996, P 2 ANN M DNA BAS CO, P159
  • [5] BASE SEQUENCE AND HELIX STRUCTURE VARIATION IN B-DNA AND A-DNA
    DICKERSON, RE
    [J]. JOURNAL OF MOLECULAR BIOLOGY, 1983, 166 (03) : 419 - 441
  • [6] Demonstration of a word design strategy for DNA computing on surfaces
    Frutos, AG
    Liu, QH
    Thiel, AJ
    Sanner, AMW
    Condon, AE
    Smith, LM
    Corn, RM
    [J]. NUCLEIC ACIDS RESEARCH, 1997, 25 (23) : 4748 - 4757
  • [7] FUMIAKI T, 2003, NEAREST NEIGHBOR THE, P170
  • [8] GARZON M, 1997, P 2 ANN GEN PROGR C, P472
  • [9] Hartemink A. J., 1998, P 4 DIMACS WORKSH DN, P227
  • [10] Marathe A., 1999, P 5 DIMACS WORKSH DN, P75
12