[논문]DNA 컴퓨팅과 진화 모델을 이용하여 Traveling Salesman Problem를 해결하기 위한 DNA 서열 생성 알고리즘

김은경; 이상용

doi:10.5391/jkiis.2006.16.2.222

문제 정의

알고리즘을 제안하였다. DNA 서열 생성 알고리즘은 생물학적으로 더욱 가깝게 모델링 할 수 있는 진화 모델의 하나인 DNA 코딩 방법을 도입한 것으로, 생물학적 실험 오류의 발생 가능성이 낮은 DNA 서열을 생성하고자 하였다. 실험에서는 제안한 DNA 서열 생성 알고리즘과 단순 유전자 알고리즘을 TSP에 적용하여 유사성, H-측정, 이차 구조, 연속성, Tm의 적합도 평가하였다.
본 논문에서는 DNA 컴퓨팅과 진화 모델 중 DNA 코딩 방법을 적용한 DNA 서열 생성 알고리즘을 제안한다. 제안한 알고리즘은 TSP에 적용하여 기존에 단순 유전자 알고리즘과 비교하였다.
본 연구에서는 DNA 컴퓨팅으로 TSP를 해결할 때 발생되는 문제점들을 분석하고, 이를 해결하기 위해 DNA 서열생성 알고리즘을 제안하였다. DNA 서열 생성 알고리즘은 생물학적으로 더욱 가깝게 모델링 할 수 있는 진화 모델의 하나인 DNA 코딩 방법을 도입한 것으로, 생물학적 실험 오류의 발생 가능성이 낮은 DNA 서열을 생성하고자 하였다.

가설 설정

(2) H-측정 : 유사성과 같은 역할을 하지만 방향성에서 서로 상보적이다. 그러므로<식3>은<식2>로부터 상보적 특징을 고려한 표현이다.

제안 방법

(1) 선택 연산 : 선택은 적응도가 가장 높은 개체에서 도태될 가능성이 있는 확률적 선택 방법의 단점을 보완한 엘리트 보존 전략 (elitist preserving strategy) 을 사용하여, 생물학 실험에 효율적으로 반응할 수 있도록로 수정하였다.
(1) 유사성 : 생성된 DNA 서열의 유사성을 평가하여 각 서열 간의 고유성만을 측정하도록를 사용하였다.
(3) 돌연변이 연산 : 교차로 생성된 정점 서열에 대하여 개체의 다양성을 높이기 위해 독립적으로 랜덤하게 발생하도록 하였다. 돌연변이가 일어날 확률은 0에서 1사이의 값으로 <식12>와 같은 확률적 돌연변이가 일어나도록 하였다.
(3) 이차 구조 : 한 서열이 자체적으로 휘어져서 상보 결합하는 것을 막기 위해, 발생 가능한 모든 경우를 수치화하여로 계산하였다.
(7) 적합도 평가 함수의 가중합 : 여섯 가지의 적합도 평가 기준을으로 평가 하였다.
(8) 적합도 스케일링: 적합도 평가 함수의 가중합은 0~1 사이의 값을 가지므로, 실험 조건의 만족도를 높이기 위해서개선된의 스케일링 윈도우를 이용하여 실험 조건의 만족도를 조정하였다.
컴퓨팅 알고리즘을 나타낸 것이다. Adlemane HPP를 해결하기 위해 시작 정점에서 도착 정점의 모든 정점을 정확히 한번만 포함하는 경로를 찾기 위해 모든 가능한 해답을 DNA 코드로 표현하고, 단 한번의 합성과 분리 과정을 통해 후보 해를 생성한 다음, 찾는 해가 있는지 검사하여 답을 제시하였다[6丄
거쳐 생성된 [표 1]을 사용하였다. 가중치는 편의상 5가지의 costl ~cost5 (10, 20, 30, 40, 50)로 나누었다.
그러므로 설계된 [표 1]의 서열이 예기치 않은 결합이 일어나는지 확인하기 위해, 정점의 서열을 랜덤하게 결합하여 그 결과를 10% 폴리아크릴아미드 겔 전기 영동으로 확인하였다. 그 결과 [그림 기을 얻을 수 있었다.
그리고 대략 300~ 350bp 정도에서 elution하여 PCR 하였다. 그리고 T-easy vector에 클로닝하여 시퀀싱으로 결과를 확인하였다. [그림 8]은 TSP의 전체 경로 중 일부분의 정점과 간선의 서열을 확인한 결과물이다.
그리고 가중 합을 적합도 스케일링하여로 평가 하였다.
그리고 대략 300~ 350bp 정도에서 elution하여 PCR 하였다. 그리고 T-easy vector에 클로닝하여 시퀀싱으로 결과를 확인하였다.
그리고 정점을 긴 DNA 서열로부터 분리하는데 사용하기 위한 시작 코돈과 정지 코돈의 개수와 동일한 염기의 발생을 막기 위한 염기의 연속성 조건을 함께 설정하도록 하였다. 이렇게 설정된 조건들이 DNA 염기인 A, T, G, C의 고른 분포와 DNA의 다양한 특징을 고려한<식1>을 사용하였다.
또한 여러가지 적합도 평가 기준은 단일한 형태가 아닌 여러가지 적합도를 포함한 적합도 함수의가중합 형태이므로, 을 사용하였다.
본 논문에서는 DNA 서열 생성 알고리즘을 7개의 정점 (city)과 5개의 가중치(cost), 25개의 간선(road)으로 설계된 [그림 4]의 TSP 그래프를 이용하였다.
본 실험에서는 [그림 4]의 TSP 그래프를 사용하여, 제안한 알고리즘과 단순 유전자 알고리즘을 사용한 DNA 컴퓨팅을 비교 평가 하였다. 실험에 사용된 파라미터는 [표 2]와 같이 설정하였다.
DNA 서열 생성 알고리즘은 생물학적으로 더욱 가깝게 모델링 할 수 있는 진화 모델의 하나인 DNA 코딩 방법을 도입한 것으로, 생물학적 실험 오류의 발생 가능성이 낮은 DNA 서열을 생성하고자 하였다. 실험에서는 제안한 DNA 서열 생성 알고리즘과 단순 유전자 알고리즘을 TSP에 적용하여 유사성, H-측정, 이차 구조, 연속성, Tm의 적합도 평가하였다. 그 결과, 단순 유전자 알고리즘으로 생성된 서열보다 적은 변위차로 생물학적 실험오류가 줄어들었으며, 세대수에 따른 평균 적합도 평가를 통해 생성된 서열은 우수하다는 것을 확인하였다.
오류가 없는 정점과 가중치 서열은 긴 경로를 생성하기 위해 반응시간과 시약을 제안하여, 결합과 결찰 과정을 수행하였다. 그리고 대략 300~ 350bp 정도에서 elution하여 PCR 하였다.
증폭된 서열을 분자량에 따라 이동 거리가 다르다는 성질을 이용한 겔 전기 영동으로 특정 길이의 DNA 서열을 확인하고 추출한다. 추출된 결과를 좋은 해인지 판단하기 위해 클로닝을 거쳐 시퀀싱으로 판독한다.
초기 DNA 서열의 생성은 문제에 사용할 긴 서열을 Randomized Block Design (RBD)을 적용하여 질량이 서로 다른 염기를 적합하게 배열할 수 있도록 하는 DNA 염기 결정 상수와 최대 발생 빈도와 최소 발생 빈도로 나타낸 전체 서열에 필요한 GC 비율을 설정하였다. 그리고 정점을 긴 DNA 서열로부터 분리하는데 사용하기 위한 시작 코돈과 정지 코돈의 개수와 동일한 염기의 발생을 막기 위한 염기의 연속성 조건을 함께 설정하도록 하였다.
추출한다. 추출된 결과를 좋은 해인지 판단하기 위해 클로닝을 거쳐 시퀀싱으로 판독한다.

데이터처리

제안한 알고리즘은 TSP에 적용하여 기존에 단순 유전자 알고리즘과 비교하였다. 그 결과 DNA 서열 생성 알고리즘은 그래프 문제의 표현에서 DNA의 특성을 잘 표현하고, 서열의 길이를 조절할 수 있었다.

이론/모형

(5) 용융 온도 (Tm): Tm을 계산하기 위해 [10]에서 사용된 Nearest Neighbor (NN 모델)로 설정하였다.

성능/효과

[그림 8]은 TSP의 전체 경로 중 일부분의 정점과 간선의 서열을 확인한 결과물이다. 그 결과 319bp의 최소의 길이를 갖는 정점 1—가중치 1—정점2—가중치 1—»정점 가중치 It■정점 4—* 가중치 정점 5—>가중치 It■정점 6—> 가중치2—정점가중치4—정점1 (총 가중치 : 130)의 경로를 확인할 수 있었다.
제안한 알고리즘은 TSP에 적용하여 기존에 단순 유전자 알고리즘과 비교하였다. 그 결과 DNA 서열 생성 알고리즘은 그래프 문제의 표현에서 DNA의 특성을 잘 표현하고, 서열의 길이를 조절할 수 있었다. 또한 생물학적 실험 오류율을 줄임으로써 빠른 시간 내에 최적의 서열을 생성할 수 있다.
실험에서는 제안한 DNA 서열 생성 알고리즘과 단순 유전자 알고리즘을 TSP에 적용하여 유사성, H-측정, 이차 구조, 연속성, Tm의 적합도 평가하였다. 그 결과, 단순 유전자 알고리즘으로 생성된 서열보다 적은 변위차로 생물학적 실험오류가 줄어들었으며, 세대수에 따른 평균 적합도 평가를 통해 생성된 서열은 우수하다는 것을 확인하였다. 또한 추가적으로 생물학적 실험으로 확인한 결과 최적의 경로를 찾을 수 있었다.
따라 평균 적합도 결과를 나타낸 그래프이다. 그 결과, 단순 유전자 알고리즘으로 생성된 서열은 모든 세대에서 불규칙한 평균 적합도를 생성하였으며, DNA 서열 생성 알고리즘으로 생성된 서열은 50세대 이후에 평균 적합도의 변위가 9wf(x)<14로, 우수한 자식 개체를 지속적으로 유지하고 있음을 확인할 수 있다. 따라서 제안한 알고리즘은 50세대 이후에 생성된 자식 개체 중에서 우수한 해를 찾을 수 있다.
생성된 정점 서열의 적합도 평가를 비교하였다. 그 결과, 연속성은 서로 비슷한 결과 값을 보이지만 유사성, H-측정, 이차 구조, Tme 제안한 알고리즘으로부터 생성된 정점서열이 전반적으로 좋은 결과를 보인다. 특히 서열의 안정성을 나타내는 Tm 값은 49~52℃로 변위가 작은 반면 단순유전자 알고리즘의 Tm 값은 24~47℃로 변위가 매우 큰 것을 확인할 수 있다.
그 결과, 단순 유전자 알고리즘으로 생성된 서열은 모든 세대에서 불규칙한 평균 적합도를 생성하였으며, DNA 서열 생성 알고리즘으로 생성된 서열은 50세대 이후에 평균 적합도의 변위가 9wf(x)<14로, 우수한 자식 개체를 지속적으로 유지하고 있음을 확인할 수 있다. 따라서 제안한 알고리즘은 50세대 이후에 생성된 자식 개체 중에서 우수한 해를 찾을 수 있다.
그 결과, 단순 유전자 알고리즘으로 생성된 서열보다 적은 변위차로 생물학적 실험오류가 줄어들었으며, 세대수에 따른 평균 적합도 평가를 통해 생성된 서열은 우수하다는 것을 확인하였다. 또한 추가적으로 생물학적 실험으로 확인한 결과 최적의 경로를 찾을 수 있었다.
위와 같이 본 논문에서 제안한 DNA 서열 생성 알고리즘은 TSP를 위해 생성한 서열이 모든 적합도 평가에서 우수한 결과를 나타냈으며, 적은 오류율을 가진 많은 서열들을 이용하여 빠른 결과를 얻을 수 있었다
그 결과, 연속성은 서로 비슷한 결과 값을 보이지만 유사성, H-측정, 이차 구조, Tme 제안한 알고리즘으로부터 생성된 정점서열이 전반적으로 좋은 결과를 보인다. 특히 서열의 안정성을 나타내는 Tm 값은 49~52℃로 변위가 작은 반면 단순유전자 알고리즘의 Tm 값은 24~47℃로 변위가 매우 큰 것을 확인할 수 있다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

DNA 컴퓨팅과 진화 모델을 이용하여 Traveling Salesman Problem를 해결하기 위한 DNA 서열 생성 알고리즘
A DNA Sequence Generation Algorithm for Traveling Salesman Problem using DNA Computing with Evolution Model 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

데이터처리

이론/모형

성능/효과

참고문헌 (10)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

DNA 컴퓨팅과 진화 모델을 이용하여 Traveling Salesman Problem를 해결하기 위한 DNA 서열 생성 알고리즘 A DNA Sequence Generation Algorithm for Traveling Salesman Problem using DNA Computing with Evolution Model 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

데이터처리

이론/모형

성능/효과

참고문헌 (10)

이 논문을 인용한 문헌

저자의 다른 논문 :

김은경 (4) 이상용 (63)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

DNA 컴퓨팅과 진화 모델을 이용하여 Traveling Salesman Problem를 해결하기 위한 DNA 서열 생성 알고리즘
A DNA Sequence Generation Algorithm for Traveling Salesman Problem using DNA Computing with Evolution Model 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper