[논문]DNA 컴퓨팅의 새로운 PCR 연산

김정숙

DNA 컴퓨팅의 새로운 PCR 연산
New PCR of DNA Computing 원문보기

컴퓨터산업학회논문지 = Journal of the Korea Computer Industry Society, v.2 no.10, 2001년, pp.1349 - 1354

초록
AI-Helper

외판원 문제(Traveling Salesman Problem)는 주어진 n개의 도시들과 그 도시들 간의 거리비용이 주어졌을 때, 모든 도시들을 정확히 한번씩만 방문하면서 걸린 비용이 최소가 드는 경로를 찾는 문제이다. 따라서 최적해(optimal)를 구하는 것은 전형적인 NP-완전 문제 중의 하나로, 외판원 문제를 해결하려는 다양한 알고리즘들이 개발되고 있다. 특히 실제 생체 분자(bio-molecule)를 계산의 도구로 사용하는 새로운 계산 방법인 DNA 컴퓨팅은 DNA 분자가 잠재적으로 가지고 있는 막대한 병렬성을 이용해서 NP-완전 문제들을 해결하고자 하는 연구들이 많이 진행되고 있다. 그러나 아직 실제 생체 분자의 특성을 잘 반영하는 계산 모델이나 분자 생물학에서 사용하는 연산들이 많이 개발되지 않아 계산 효율이 비교적 좋지 않다. 따라서 본 논문에서는 외판원 문제를 해결하기 위한 DAN컴퓨팅의 새로운 중합 효소 연쇄 반응(Polymerase Chain Reaction, PCR) 연산을 개발하였다.

Abstract ▼ AI-Helper

In the Traveling Salesman Problem(TSP), a set of N cities is given and the problem is to find the shortest route connecting them all, with no city visited twice and return to the city at which it started. Since TSP is a well-known combinatorial optimization problem and belongs to the class of NP-complete problems, various techniques are required for finding optimum or near optimum solution to the TSP. Especially DNA computing, which uses real bio-molecules to perform computations supported by molecular biology, has been studied by many researchers to solve NP-complete problem using massive parallelism of DNA computing. Though very promising, DNA computing technology of today is inefficiency because the effective computing models and operations reflected the characteristics of bio-molecules have not been developed yet. In this paper, I design new Polymerase Chain Reaction(PCR) operations of DNA computing to solve TSP.

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

그러나 지금은 개발되어 있는 연산이 많지 않다. 따라서 본 논문에서는 DNA 컴퓨팅의 연산 중 중합 효소 연쇄 반응 연산을 효율적으로 수행할 수 있도록 개발하였다.
그러나 DNA 컴퓨팅 알고리즘은 아직 연산 개발이나 코드 표현 방법들이 부족하다. 따라서 본 논문에서는 이런 문제점을 해결하고자 새로운 PCR 연산 기법을 3가지 설계하고 실험을 진행하고 있으며, 앞으로 연구과제는 문제의 크기가 아주 큰 문제를 해결할 수 있는 효율적인 방법들을 개발하는 일과 코드를 최적화하는 알고리즘을 추가하고 개발하는 일이다. 더불어 실험을 실제 실체처럼 수행할 수 있는 시뮬레이터를 확장하여 구현하는 일이다.

가설 설정

생각하였다. 또한 매번 반응이 있을 때마다 해를 생성한다고 가정하였다. 실험은 도시수가 많지 않은 단순한 그래프이고, 생물학 실험 방법들에서 전기 영동법은 미리 정해진 길이 이상의 염기배열을 삭제하는데 사용하였으며 항체 친화력 반응을 이용하여 각 정점 방문 여부를 검사하는 실험이 진행중이다.
반응 오류는 없다고 가정하므로 항상 정확하게 반응한다고 생각하였다. 또한 매번 반응이 있을 때마다 해를 생성한다고 가정하였다.

제안 방법

마지막으로 세 번째 방법은 중합효소 연쇄 반응 연산을 할 특정한 염기 배열을 선택하여, 그 염기배열내의 가중치를 검사한 후 가장 가중치가 많은 두 곳을 선택해서 서로 위치를 교환한 후 중합 효소연쇄 반응을 수행한다. 위에서 제안한 방법으로 연산을 수행하면서 현재 생성된 해보다 나쁜해를 가지는 경로를 생성하면 그 경로는 최종해가 될 가능성이 없으므로 해 집단에서 삭제하였다.
먼저 첫 번째 개발한 방법은 특정한 염기 배열 즉 시작 부분과 끝 부분이 특정 정점(시작 정점)인염기배열을 선택한 후 임의의 두 위치를 선택하여 그 두 위치를 서로 바꾼 후, 염기 배열을 증폭 시켜 상대적으로 다른 염기 배열들의 비율이 낮아지도록 하였다.
또한 매번 반응이 있을 때마다 해를 생성한다고 가정하였다. 실험은 도시수가 많지 않은 단순한 그래프이고, 생물학 실험 방법들에서 전기 영동법은 미리 정해진 길이 이상의 염기배열을 삭제하는데 사용하였으며 항체 친화력 반응을 이용하여 각 정점 방문 여부를 검사하는 실험이 진행중이다.
것이다. 여기서는 증폭시키고자 하는 염기 배열을 단순하게 상보 결합을 추가하여 이중가닥으로 만들지 않고 좀 더 새로운 염기 배열을 얻을 수 있도록 하는 중합효소 연쇄 반응을 제안한다.

대상 데이터

도구 및 저장 도구로 사용한다. 따라서 가상의 DNA 컴퓨터는 A(Adenine), C(Cytosme), G(Guanine), T(Thymine), 4가지 염기의 정보를 표현한다. A는 T와 2개의 수소 결합을 형성하면서 결합하고 C는 G와 3개의 수소 결합을 형성하면서 결합하는데, 이것을 Watson-Crick 상보 결합이라고 한다[1][5].
[9]는 VNA(Virtual Nucleic Acid) 라는 시뮬레이터를 개발하였고, [10]에서는 NACST(Nucleic Acid Computing Simulation Toolkit)이라는 시뮬레이터를 각각 개발하였다. 본 논문에서 실험은 진행중이며, 실험에서 사용한 파라미터는 [10]에 있는 파라미터를 동일하게 사용하였다. 다음 <표 2>는 외판원 문제를 해결하기 위해 사용한 파라미터들이다.

이론/모형

의미한다. 문제에 따라 다양한 표현 방법이 존재하지만, 여기서는 Adleman의 그래프 표현 방법을 사용한다. 외판원 문제는 간선 염기배열은 연결을 하는 역할뿐만 아니라 가중치를 표현하기 위한 역할도 해 주어야 한다.
본 논문에서는 [10]에서 제시한 코드 표현 방법을 사용한다. 정점 염기 배열은 위치 염기배열만을 포함하고, 간선 염기배열은 위치 염기배열과 가중치 염기배열을 모두 포함하도록 한다.
A는 T와 2개의 수소 결합을 형성하면서 결합하고 C는 G와 3개의 수소 결합을 형성하면서 결합하는데, 이것을 Watson-Crick 상보 결합이라고 한다[1][5]. 자료구조는 DNA 구조인 이중가닥(double strand)이나 단일가닥(single strand)을 사용하며, 정보를 저장하고 추출하는 기본 방법은 Watson-Crick 상보 결합이다. 일반적인 연산자로는 생물학 실험 방법들인 결찰법(ligation), 서냉복원법(annealing), 하이브리드형성(hybridization), 중합효소 연쇄반응, 겔 전기 영동법(gel electrophoresis), 항체 친화력 반응(antibody affinity) 등과 여러 가지 효소(enzyme) 들을 사용한다.

성능/효과

둘째로, DNA 컴퓨터는 계산 속도나 계산 효율에서도 우수하다. 계산 속도 측면에서 살펴보면 일반 PC는 초당 10⁶번의 계산을 할 수 있고 슈퍼컴퓨터라 할지라도 초당 10¹²번의 연산만이 가능하다.

후속연구

DNA 컴퓨팅 알고리즘이 가지고 있는 초 병렬성을 이용하여 NP-완전 문제들을 해결하는 새로운 방법들이 제안될 것으로 보이며, 또한 기존의 진화 연산 모델보다 생체 컴퓨터 (biocomputer)의 구현 가능성이 높고, 다른 기술 분야로의 파급 효과도 클 것으로 기대한다. 그러나 DNA 컴퓨팅 알고리즘은 아직 연산 개발이나 코드 표현 방법들이 부족하다.
DNA 컴퓨팅이 주목을 받고 있는 이유는 DNA 분자가 가지고 있는 막대한 병렬성으로 현재 사용되고 있는 병렬 컴퓨터로써는 상상도 할 수 없다. 이러한 병렬성을 이용하면 NP-완전 문제들과 같은 여러 가지 문제들을 효율적으로 해결할 수 있을 것으로 생각된다. 그런데, DNA 컴퓨팅은 생체 분자를 이용하기 때문에 일반 컴퓨터의 연산자를 사용할 수 없고, 분자 생물학에서 사용하는 여러 가지 실험 방법들을 연산의 도구로 사용하여야 한다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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 컴퓨팅의 새로운 PCR 연산
New PCR of DNA Computing 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

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

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

선택된 텍스트

연합인증

DNA 컴퓨팅의 새로운 PCR 연산 New PCR of DNA Computing 원문보기

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

Abstract ▼ AI-Helper

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

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

이 논문을 인용한 문헌

저자의 다른 논문 :

김정숙 (26)

관련 콘텐츠

원문 보기

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

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

선택된 텍스트

DNA 컴퓨팅의 새로운 PCR 연산
New PCR of DNA Computing 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper