본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

해밀톤 경로 문제를 위한 DNA 컴퓨팅에서 코드 최적화
Code Optimization in DNA Computing for the Hamiltonian Path Problem

김은경   (공주대학교 컴퓨터공학과UU0000178  ); 이상용   (공주대학교 정보통신공학부UU0000178  );
  • 초록

    DNA 컴퓨팅은 생체 분자들의 막대한 병렬성을 정보 처리 기술에 적용한 기술로, Np-complete문제를 해결하기 위하여 사용되고 있다. 하지만 DNA 컴퓨팅 기술만으로 NP-complete 문제를 해결할 경우에는 해를 찾지 못하거나 많은 시간이 걸리는 문제점이 있다. 본 논문에서는 DNA 코딩 방법을 적용하여 DNA 서열을 효율적으로 표현하고, 반응횟수 만큼 합성과 분리 과정을 거쳐 코드를 생성하는 ACO(Algorithm for Code Optimization)를 제안했다. 그리고 ACO를 NP-complete 문제 중의 하나인 Hamiltonian Path Problem에 적용하였다. 그 결과 ACO는 Adleman의 DNA 컴퓨팅 알고리즘 보다 가변길이의 DNA 코드를 효율적으로 표현할 수 있다는 것을 확인하였다. 또 한 ACO는 Adleman의 DNA 컴퓨팅 알고리즘 보다 탐색 시간과 생물학적 오류율을 50%정도 줄일 수 있었으며, 빠른 시간 내에 정확한 경로를 탐색할 수 있었다.


    DNA computing is technology that applies immense parallel castle of living body molecules into information processing technology, and has used to solve NP-complete problems. However, there are problems which do not look for solutions and take much time when only DNA computing technology solves NP-complete problems. In this paper we proposed an algorithm called ACO(Algorithm for Code Optimization) that can efficiently express DNA sequence and create good codes through composition and separation processes as many as the numbers of reaction by DNA coding method. Also, we applied ACO to Hamiltonian path problem of NP-complete problems. As a result, ACO could express DNA codes of variable lengths more efficiently than Adleman's DNA computing algorithm could. In addition, compared to Adleman's DNA computing algorithm, ACO could reduce search time and biological error rate by 50% and could search for accurate paths in a short time.


  • 주제어

    해밀톤 경로 문제 .   DNA 컴퓨팅 .   DNA 코딩 방법 .   NP-complete 문제.  

  • 참고문헌 (12)

    1. A. Brenneman and A. E. Condon, 'Strand Design for Bio-Molecular Computation,' Dept. of Computer Science, University of British Columbia, March 22, 2001 
    2. R. Deaton, R. C. Murphy, M. Garzon, D. R. Franceschetti, S. E. Jr. Stevens, 'Reliability and efficiency of a DNA-based computation,' Physical Review Letters, 82(2) : 417-420, 1998 
    3. M. Yamamoto, J. Yamashita, T. Shiba, T. Hirayama, S. Takya, K. Suzuki, M. Munekata, A. Ohuchi, 'A Study on the Hybridiztation Process In DNA Computing,' In [DNA-V], pp. 99-108, 1999 
    4. T. Yoshikawa, T. Furuhashi, Y. Uchidawa, 'Acquisition of Fuzzy Rules of Constructing Intelligent Systems using Genetic Algorithm based on DNA Coding Method,' Proceedings of International Joint Conference of CFSA/IFIS/SOFT'95 on Fuzzy Theory and Applications, 1995 
    5. T. Yoshikawa, T. Furuhashi, Y. Uchidawa. 'The Effect of Combination of DNA Coding Method with Pseudo-Bacterial GA,' Proceeding of the 1997 IEEE International Intermag. 97 Magnetics Conference 1997 
    6. A. Salomaa, DNA complementarity and paradigms of computing, Turku Centre for Computer Science TUCS Technical Reports, No.457, 2002 
    7. N. Jonoska, N. C. Seedman (Eds.), 'Preliminary Proceedings of 7th International Meeting on DNA Based Computers,' University of South Florida, Tampa, FL, June, 10-13, 2001 
    8. J. A. Rose, R. J. Deaton, D. R. Franceschetti, M. Garzon, and S. E. Jr. Stevens, 'A Statistical Mechanical Treatment of Error in the Annealing Biostep of DNA Computation,' In [GECC099], pp. 1829-1834 
    9. R. Deaton, R. C. Murphy, M. Garzon, D. R. Franceschetti, S. E. Jr. Stevens, 'A DNA based implementation of an evolutionary search for good encodings for DNA computation,' Proceedings of IEEE Conference on Evolutionary Computation, IEEE Press, pp. 267-271, 1997 
    10. J. D. Watson, M. Gliman, J. Wikowski, M. Zoller, Recombinant DNA, 2nd Ed., Scientific American Books, New York, 1992 
    11. L. M. Adleman, 'Molecular computation of solutions to combinatorial problems,' Science, 266: 1021-1024, 1994 
    12. M. Ogihara, A. Ray, Executing Parallel Logical Operations with DNA, In Proceedings of the IEEE Congress on Evolutionary Computation, pp. 972-979, 1999 
  • 이 논문을 인용한 문헌 (1)

    1. Lim, Hee-Woong ; Yoo, Suk-I. ; Zhang, Byoung-Tak 2007. "Thermodynamics-Based Weight Encoding Methods for Improving Reliability of Biomolecular Perceptrons" 정보과학회논문지. Journal of KIISE. 소프트웨어 및 응용, 34(12): 1056~1064     

 저자의 다른 논문

  • 김은경 (4)

    1. 2003 "Maximal Clique Problem을 해결하기 위한 DNA 코딩 방법을 적용한 DNA 컴퓨팅" 정보처리학회논문지. The KIPS transactions. Part B. Part B b10 (7): 769~776    
    2. 2004 "Traveling Salesman Problem을 해결하기 위한 DNA 코딩 방법을 적용한 DNA 컴퓨팅" 퍼지 및 지능시스템학회 논문지 = Journal of fuzzy logic and intelligent systems 14 (1): 105~111    
    3. 2005 "효과적인 배낭 문제 해결을 위해 DNA 코딩 방법을 적용한 DNA 컴퓨팅" 퍼지 및 지능시스템학회 논문지 = Journal of fuzzy logic and intelligent systems 15 (6): 730~735    
    4. 2006 "DNA 컴퓨팅과 진화 모델을 이용하여 Traveling Salesman Problem를 해결하기 위한 DNA 서열 생성 알고리즘" 퍼지 및 지능시스템학회 논문지 = Journal of fuzzy logic and intelligent systems 16 (2): 222~227    
  • 이상용 (50)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기