(51) Int. Cl. 7 C12Q 1/68 (19) 대한민국특허청 (KR) (12) 등록특허공보 (B1) (45) 공고일자 (11) 등록번호 (24) 등록일자 2005 년 08 월 03 일 10-0504628 2005 년 07 월 21 일 (21) 출원번호 10-2002-0028187 (65) 공개번호 10-2003-0090182 (22) 출원일자 2002년05월21일 (43) 공개일자 2003년11월28일 (73) 특허권자재단법인서울대학교산학협력재단서울특별시관악구봉천동산 4-2 (72) 발명자장병탁서울서초구방배 3 동방배아트힐 101-1801 박태현서울시서초구서초동 1334 번지신동아아파트 5-1102 신수용서울관악구봉천 2 동동아아파트 104-1402 이지연경기안양시만안구석수동석수대아아이투빌 104-503 (74) 대리인임재룡 심사관 : 김희수 (54) DNA 컴퓨팅을위한 DNA 가닥의녹는점차이를이용한실수정보부여방법및이를이용하여가중치그래프문제를해결하는방법 요약 본발명은 DNA 가닥의녹는점을이용하여 DNA 컴퓨팅에서필요한실수정보를 DNA 가닥에인코딩하는방법과, 이를이용하여그래프문제를해결하는방법에관한것으로, 더욱상세하게는, PCR 수행시낮은변성온도에서는녹는점이낮은 DNA 가닥이상대적으로더많이증폭된다는사실에기초하여, 녹는점의차이를이용해서실수를표현한후해당녹는점을가지는 DNA 를제작하고, PCR 의변성온도를높은것에서부터시작하여각주기마다서서히낮추면서 PCR 을수행함으로써, 또는그반대로낮은변성온도로부터시작하여각주기마다서서히올려주면서 PCR 을수행함으로써, 필요한 DNA, 즉큰실수나작은실수를표현하는 DNA 를상대적으로더많이증폭시켜, 가중치가있는그래프문제를해결할수있는 DNA 컴퓨팅방법에관한것인데, 이는녹는점이관련된대부분의구현단계에활용될수있고해를효율적으로찾을수있다는특징을가진다. 대표도 도 4-1 -
색인어 DNA 컴퓨팅, 실수정보인코딩, 가중치, 그래프문제, DNA 가닥, 녹는점 명세서 도면의간단한설명 도 1 은녹는점차이를이용하여고안한 20 mer 짜리도시시퀀스와가중치시퀀스의예이고, 도 2 는여행하는순환외판원문제의한예와그문제를녹는점차이를이용하여생화학적인실험들로구현하기위한전체적인흐름도이고, 도 3a 및 3b 는그구현부분에서각단계의결과로서, 레인 M 은 50 bp 마커 (marker) 로서, 도 3a 의 (A) 에서레인 1, 2 는단계 1 의라이게이션 (ligation) 결과를, 레인 3 은올리고머혼합물을나타내고, 도 3a 의 (B) 에서레인 1 은반복적인라이게이션결과를나타내며, 도 3b 의 (A) 에서레인 1,2 는도 2b 의과정 2 의 PCR 결과이고, 도 3b 의 (B) 에서레인 1 은도 2b 의과정 4 의 PCR 결과이며, 도 3b 의 (C) 는레인 1 은도 2b 의과정 7 의 DTG-PCR 결과이다. 도 4 는변성온도구배 PCR(denaturation temperature gradient PCR) 의효과를보여주는결과로서, 레인 M 은 50 bp 마커를나타내는바, 레인 1 은일반적인 PCR 결과를, 레인 2 는 DTG-PCR 결과를나타낸다. 발명의상세한설명 발명의목적 발명이속하는기술및그분야의종래기술 본발명은최근에대두되고있는새로운컴퓨팅분야인 DNA 컴퓨팅에관련된것으로, 더욱상세하게는 DNA 가닥의녹는점이 GC 함량과열역학적요소들에의해서결정되는특성을이용하여, 상이한녹는점을갖도록제작된 DNA 염기서열들간의녹는점차이를실수정보와결부시킴으로써, DNA 가닥에실수정보를표현하는방법및이런녹는점차이를이용하여실수정보가부여된 DNA 염기서열을사용하여, 가중치가있는그래프문제를해결하는방법에관한것이다. DNA 컴퓨팅은 1994 년 Adleman 에의해서도입된컴퓨팅분야로 (L. M. Adleman, Molecular computation of solutions to combinatorial problems, Science, 266:1021-1024, 1994), 기존의순차적이고비가역적인실리콘기반의컴퓨팅으로부터벗어나생체분자들과생화학적실험들의거대한병렬성을이용하여기존의컴퓨터로연산이어려운문제들을해결하고자고안된새로운컴퓨팅모델중하나이다. 종래의실리콘컴퓨팅은, ON" 과 0FF" 의전기신호를각각 1 과 0 으로대응시키는 2 진수의기계언어로정보를인코딩하여처리하며, 정보처리의기본연산은논리합 (AND 연산 : 예를들어, 1 and 1 = 1; 1 and 0 = 0; 0 and 0 = 0) 과논리곱 (OR 연산 : 예를들어, 1 or 1 = 1; 1 or 0 = 1; 0 or 0 = 0) 으로이루어져있다. 반면, DNA 컴퓨팅은 DNA 의기본단위인 A, G, T, C 의 4 개의염기로이루어지는합성 DNA 분자에정보를인코딩시키며, 이들정보는 DNA 분자사이의분자적특성에의한상호작용및생화학적인실험등에의해서처리된다. 예를들어, 2 라는실수를표현할때, 기존의실리콘컴퓨팅은전기신호의 ON 및 OFF 를이용하여 0000 0010 의 8 비트단위의전기신호에대응시켜나타낼수있으며, DNA 컴퓨팅에서는예를들어 AAAA CCTG' 라는 8 개의 DNA, 즉올리고뉴클레오타이드 DNA 에대응시켜 2 라는실수를표현할수있다. - 2 -
다시설명하자면, DNA 컴퓨팅은, 일정한정보를 A, G, T, C 의 4 개의염기로이루어지는 DNA 분자에저장하고, 이를생화학적인방법에의하여정보를처리함으로써, 목적하는정보처리결과를얻어낸다. 이러한 DNA 컴퓨팅방법은, DNA 분자의특성으로인하여, 기존의순차적이고비가역적인실리콘기반의컴퓨팅으로부터벗어나거대한병렬성, 매우빠른처리능력및좁은공간에서의정보저장능력을나타낼수있다. DNA 컴퓨팅의창시자인 Adleman 에따르면, 정보를 DNA 의염기서열로표시하여컴퓨팅하는것은다음과같은장점을갖는다. - DNA 컴퓨팅은생화학적반응을이용하여연산을수행하는것이고, 그의처리속도는초당 1014 정도의처리를수행할수있어, 현재가장빠른슈퍼컴퓨터보다약 100 배빠른속력을갖는다. - DNA 컴퓨팅은 1 줄당 2x1019 처리를수행할수있어, 인간이만든컴퓨터보다약 10 억배정도의에너지가절약된다. - DNA 컴퓨팅은 1 입방나노미터당약 1 비트를저장할수있어, 비디오테입보다약 10 조배이상의저장능력을갖는다. 이러한장점을활용하기위해서많은연구들이진행되고있으나아직까지개발된것이많지않다. 또한기존의연구들은대부분대부분의연구들이조합최적화 (Q. Ouyang, P. D. Kaplan, S. Liu, and A. Libchaber, DNA solution of the maximal clique problem, Science, 278:446-449, 1997), 불리안회로작성 (G. C. Owenson, M. Amos, D. A. Hodgson, and A. Gibbsons, DNA-based logic, Soft Computing, 5(2):102-105, 2001) 등에대한연구에집중하고있다. 그러나실생활에서발생되는대다수의문제들은실수로나타내어지는가중치정보를가지고있고 ( 예를들어, 교통비, 처리시간등 ), 내재된실수로나타내어지는가중치정보를이용해서해답을구하게되어있다. 즉, DNA 컴퓨팅의응용분야를확장시키기고, 실생활문제에적용하기위해서는, 가중치를나타내는실수를 DNA 염기서열상에효율적으로표현하는방법이필요하다. DNA 가닥안에실수정보를표현하는방법으로는, DNA 의길이, DNA 의농도, 이중가닥 DNA 에서의수소결합의개수등을이용한것이제안되어져왔으며, 이외에도특정염기서열로서이진수를표현하는방법이사용되어졌다. 하지만, 이러한표현방법은표현범위나확장성에있어서많은문제점들을가지고있다. 길이차이를통해실수정보를표현하면 (A. Narayanan and S. Zorbalas, DNA algorithms for computing shortest paths, In Proceedings of Genetic Programming 1998, pp. 718-723, Morgan Kaufmann, 1998), 길이를구별함으로써원하는 DNA 가닥을쉽게찾아낼수있다는장점을가지지만, 표현할수있는실수의범위가작게제한될수밖에없고, 이로인해확장성에한계를갖게된다. 또한, DNA 가닥의농도차이를통해실수를표현하는방법 (M. Yamamura, Y. Hiroto, and T. Matoba, Solutions of shortest path problems by concentration control, In Preliminary Proceedings of 7th International Workshop on DNA-based Computers, pp.231-240, 2001) 도고안되었다. 이방법은해답을찾아가는과정을효율적으로진행할수있다는장점이있으나, 최종해답을확인하는것이쉽지않다는문제점을가진다. 전기영동결과의밴드는한개가아닌여러종류의 DNA 가닥으로구성되어있는데, 그중에서한종류의가닥만을추출할수있는방법이없고, 또한어떤밴드에최종해답이포함되어있는지알수없다. 이밖에수소결합의개수를이용하고자하는노력 (S.-Y. Shin, B.-T. Zhang, and S.-S. Jun, Solving traveling salesman problems using molecular programming, In Proceedings of Congress on Evolutionary Computation 1999, pp.994-1000, IEEE Press, 1999) 도행해졌다. 그러나이방법은 DNA 의녹는점이단순히 GC 의함량만으로결정된다는가정하에제안된방법으로, 본발명에서제안하는열역학적요소들을고려한녹는점차이를이용한실수로나타내어지는가중치정보의표현방법보다정보를표현하는것이비효율적이다. 실수가아닌이진수를 DNA 가닥에표현하는방법 (Q. Ouyang, P. D. Kaplan, S. Liu, and A. Libchaber, DNA solution of the maximal clique problem, Science, 278:226-229, 1997) 도제안되었으나, 이는특정염기서열을사용해서 0, 1 을구분하는단순한방법이었다. 따라서실제적용할수있는경우가많지않다는한계가있다. 이상에서살펴본바와같이, DNA 컴퓨팅분야에서는, 실수정보를 DNA 에나타내는방법에관한개발이요구되고있고, 이에대해많은시도들이있으나, 상기한문제점으로인하여, 실제로적용하기에는문제점을갖는다. - 3 -
발명이이루고자하는기술적과제 이에, 본발명자들또한실수정보를 DNA 가닥에인코딩하기위한방법을찾기위해많은연구를수행한결과, DNA 가닥의녹는점이 GC 함량과열역학적요소들에의해서결정되고, PCR 수행시낮은변성온도에서는녹는점이낮은 DNA 가닥이상대적으로더많이증폭된다는사실에기초하여, 작은실수를인코딩하기위해서는녹는점을낮게하여 DNA 를제작하고, 반대로큰실수의경우에는녹는점을높게하여 DNA 를제작한후, PCR 의변성온도를낮은것에서부터시작하여각주기마다서서히높이면서 PCR 을수행함으로써, 또는그반대로높은변성온도로부터시작하여각주기마다서서히내려주면서 PCR 을수행함으로써, 상대적으로녹는점이차이가나는 DNA, 즉작은실수 ( 각주기마다온도를높이는경우 ) 또는큰실수 ( 각주기마다온도를낮추는경우 ) 를나타내는 DNA 가더많이증폭되도록하고, 이를이용하여 DNA 컴퓨팅이가중치가있는그래프문제를해결할수있음을발견하고, 본발명을완성하기에이르렀다. 따라서본발명의목적은 DNA 컴퓨팅에서사용되는 DNA 염기서열상에, 실수정보를표현하는방법과이를이용하여실수로표현되는가중치가있는그래프문제를해결하기위한방법을제공하는것이다. 발명의구성및작용 상기한목적을달성하기위해서, 본발명은실수정보를 DNA 염기서열상에표현하는데에있어서, 녹는점을다르게하여제작한 DNA 가닥으로표현함을특징으로한다. 또한, 가중치가있는그래프문제를 DNA 컴퓨팅에의해해결하는데있어서, 본발명에따른 DNA 컴퓨팅방법은, 가중치마다녹는점을다르게대응시킨 DNA 들을이용함을특징으로한다. 이하, 본원발명을더욱구체적으로설명한다. 본원명세서에서 그래프 라는용어는, 특정문제의해가되는정점 (vertex) 과간선 (edge) 의집합을의미하며, 간선에는일정한가중치가주어질수있다. 예를들어 가중치 는순환외판원문제 (traveling salesman problem) 의경우 여행비용 을의미한다. 본발명을상세히설명하기에앞서, 순환외판원문제 (traveling salesman problem) 의예를통해서, 그래프및가중치의용어에대한예를들고, DNA 컴퓨팅에의한그래프문제의처리에대해설명한다. 순환외판원문제란, 예를들어외판원이 A, B, C 및 D 의 4 개의도시를각각한번씩만방문하고, 최종적으로원래의도시 A 로돌아올때, 가장최소한비용으로방문을마치는방법을구하는것이다. 이때, 각도시간에는길이하나만있을수도있고, 여러개있을수도있으며없을수도있다. 또한, 각각의길을통과하는비용이매우다양하다. 이때, A 도시를출발하여 B, C 및 D 를모두한번씩만거쳐 D 로돌아올수있는방법의집합, 즉해의집합을그래프라고정의하며, 각도시를정점이라하고, 각각의길에대해서는간선이라한다. 또한, 각길을통과하는데소요되는비용이가중치가된다. 외판원의방문경로문제의정답, 즉해는최소한의비용으로방문을마칠수있는방법이된다. DNA 컴퓨팅으로상기순환외판원의방문경로문제를해결하는것은다음의방법에의해서이루어진다. 우선, 정점에해당하는각각의도시를나타내는 DNA 염기서열을합성한다. 예를들어, A 도시 : AAAAaaaa, B 도시 GGGGgggg, C 도시 TTTTtttt, D 도시 CCCCcccc 로대응시킨다. 그런다음, 각도시의염기서열을이용하여간선 (edge) 에해당하는각도시간의이동을표현한다. 예를들어 A 에서 B 로가는길을표시하는염기서열은 ttttcccc 로나타내고, B 에서 C 로가는길은 ccccaaaa 로, C 에서 D 로가는길은 aaaagggg, D 에서 A 로가는길은 ggggtttt 로표현한다. 이와같은문제에서, (A, B, C, D, A) 의순으로각도시를방문하는 DNA 염기서열은, AAAAaaaaGGGGggggTTTTttttCCCCccccAAAAaaaa 의 DNA 로나타낼수있다. 그다음, 같은방식으로, 도시들을방문하는다른가능한경로에대한염기서열들을모두합성하여해의집단인그래프를작성한다. 그래프의작성은라이게이즈 (ligase) 를이용하여 8 base 길이의 DNA 들을연결시키는것에의해이루어진다. 라이게이즈효소에의한 DNA 연결은 DNA 가닥의 5 - 말단과 3 - 말단사이에무작위로이루어지므로, (A, A, B, B, C) 등의두개이상의도시를거친외판원의이동경로에해당하는 DNA 도얻어질수있고, (A, B, C, A) 또는 (A, B, C, D, A, B) 등과같이한도시를두번또는한번도방문하지않는외판원의이동경로에해당하는 DNA 들도얻어질수있다. 그러나이러한것들은해가될수없으므로, 제거되어야만한다. 이러한 DNA 들은다음의방법에의해서제거된다. - 4 -
예를들어, 모든도시를한번씩만방문한 DNA 염기서열의길이와한도시를두번이상또는한번도방문하지않은것에대응하는염기서열은서열길이가달라질것이다. 이때전기영동을실시하여길이가다른 DNA 를걸러낼수있다. 또한, A 도시를출발하여 A 도시에서끝나야하므로, 해가될수있는 DNA 가닥의 5 - 말단의 8 개의염기서열및 3 - 말단의 8 개의염기서열은항상동일해야한다. 따라서그말단의염기서열로이루어진프라이머를사용해서 PCR 함으로써다른염기서열을갖는 DNA 는걸러질수있다. 그리고친화성분리법 (affinity separation) 을사용하여모든도시를방문한 DNA 가닥만을걸러낼수있다. 상기와같이걸러진 DNA 들은서열분석을하거나프라이머쌍을달리하여 PCR 한생성물을전기영동하여크기를확인함으로써, 외판원의이동경로를역해석할수있다. 상기에서언급한문제는가중치가일정하거나가중치를포함하지않는순환외판원문제의경우이고, 가중치까지고려하여상기한문제를해결하기위해서는, 가중치를나타내는 DNA 서열을포함해야만한다. 한편, 본발명은상기한가중치를나타내는 DNA 의생성방법에관한것이며, 특히실수로나타내어지는가중치를 DNA 상에표현하기위해서, 본원발명은가중치의실수정보를 DNA 의녹는점과연관시킴을특징으로한다. 본원명세서에서 DNA 의녹는점 은, 이중가닥 DNA 의절반이단일가닥 DNA 로해리되는온도로정의되는데, GC 의함량과열역학적요소들, 염의농도, 그리고 DNA 의농도에의해서결정된다. DNA 의녹는점을계산하는방법은여러가지가제안되어왔다. 그중의하나는 GC 의함량, DNA 의길이, DNA 의농도, 염의농도를변수로사용한것이고, 다른하나는열역학적요소들인엔탈피와엔트로피의변화와 DNA 의길이, DNA 의농도, 염의농도를변수로고려한것으로서 nearestneighbor 모델 (J. SantaLucia Jr., A unified view of polymer, dumbbell, and oligonucleotide DNA nearest-neighbor thermodynamics, Proc. Natl. Acad. Sci. USA, 95:1460-1465, 1998) 이라고도알려져있다. 만약 DNA 의길이와농도, 그리고염의농도가일정하다면, DNA 의녹는점은 GC 의함량과열역학적요소들에의해서만결정된다. 본발명은, GC 의함량과열역학적요소들을고려하여, DNA 의녹는점을다양하게생성하고, 실수의차이를 DNA 의녹는점의차이와대응시킴으로써, 가중치의실수정보를 DNA 상에표현한다. DNA 의녹는점을이용하여실수정보를부여하는데에는두가지방법이있을수가있다. 예를들어, 숫자가작을수록 DNA 가닥의녹는점을높게하거나, 반대로숫자가클수록 DNA 가닥의녹는점을높게하는것이다. 이는 DNA 컴퓨팅의목적에따라서달리할수있다. 녹는점이높은 DNA 가닥의서열혹은녹는점이낮은 DNA 가닥의서열은, 당업계의통상적인방법에의해서서열을생성한후, 당업계의통상적인방법에의해서 DNA 가닥의녹는점을측정하고, DNA 들마다의상대적인녹는점차이를확인함으로써, 생성될수있다. 한편, 본발명은또한이러한가중치를나타내는 DNA 의서열을이용함으로써, 가중치가있는그래프문제를해결할수있다. 따라서본발명은 DNA 컴퓨팅에의해가중치가있는그래프문제를해결하기위한방법을제공한다. 상기가중치에따라녹는점을다르게부여한 DNA 를이용하여가중치가있는그래프문제의해결을위한본발명에따른 DNA 컴퓨팅방법은, 변성온도구배 (denaturation temperature gradient) PCR 을이용함을특징으로한다. DNA 의증폭에많이사용되는생화학적실험방법의하나가 PCR (Polymerase Chain Reaction) 이다. PCR 은변성 (denaturation) 단계, 어닐링 (annealing) 단계, 중합 (polymerization) 단계의사이클을반복수행하는것으로, 각각의단계에해당하는온도로반복적으로바꾸어주는것에의해서상기사이클이반복수행된다. DNA 의녹는점은변성단계와관련이있다. 변성은이중가닥의 DNA 가단일가닥으로해리되는것을의미하며, DNA 의변성이이루어지지않을경우, PCR 에의한 DNA 의증폭은수행될수없다. 따라서 DNA 의녹는점이높다면, 높은온도에서만 DNA 가변성될수있다는것을의미하며, DNA 의녹는점이낮다면, 낮은온도에서도 DNA 가변성될수있다는것을의미한다. 만약작은실수를갖는 DNA 가닥을녹는점이낮게하여제작된다면, 낮은변성온도에서 PCR 을수행함으로써, 큰실수를나타내는 DNA 들에비해상대적으로많은양이증폭될수있으며, 이를통해작은숫자를나타내는것들을분리해낼수있다. 변성온도구배 PCR 이란, 기존의일반 PCR 과마찬가지로변성, 어닐링, 중합의단계로수행되지만, 그와는달리각주기마다변성온도를일정하게올려주거나내려주면서수행되는 PCR 을의미한다. DNA 컴퓨팅을이용하여, 특히변성온도구배 PCR 을이용하여, 가중치가있는그래프문제, 예를들어순환외판원문제를해결하는방법은, 도 2b 의흐름도에서보는바와같다. - 5 -
순환외판원문제에서는, 원하는경로가가중치의합이가장작은것이, 소요비용이가장작은길이되기때문에, 작은가중치를인코딩하는 DNA 가닥의녹는점을낮게하였다. 따라서일정조건을만족한 DNA 가닥들중에서가중치의합이가장작은 DNA 가닥 ( 원하는가닥 ) 을많이증폭시켜야하기때문에, 변성온도를점차적으로올리는방법을사용하였다. 변성온도가낮은상태에서는녹는점이낮은 ( 즉, 가중치의합이작은 ) DNA 만이증폭되다가, 변성온도가점차높아지면서, 가중치의차이에상관없이, 모든 DNA 들이증폭되게된다. 따라서가중치의합의차이에따라증폭량이달라지므로, 가장증폭이많이수행된 DNA 를선택하여, 염기서열을확인한후, 서열분석을통해결과를확인함으로써, 가중치가있는그래프문제가해결된다. 반대로, 작은가중치를인코딩하는 DNA 가닥의녹는점을높게하고, 일정조건을만족한 DNA 가닥들중에서가중치의합이가장작은 DNA 가닥 ( 원하는가닥 ) 을많이증폭시기위해서, 변성온도를높게시작하여점차적으로낮추는방법도사용될수있다. 본발명에따른 DNA 컴퓨팅방법은시작단계에서가능한모든답들을균일하게생성해낸뒤에, 정답의조건을가지는것을찾아나가기만하는기존의방법과는달리, 답공간에정답을상대적으로많은수포함하게한다는데에장점을가진다. 한편, DNA 컴퓨팅에서실수로나타내어지는가중치를포함하는그래프문제들은순환외판원문제, 스타이너트리문제 (steiner tree problem), 최소간격트리문제 (minimum spanning tree problem) 등이있으며, 본발명의 DNA 컴퓨팅방법, 즉가중치의차이를녹는점의차이로표현하고, 변성온도구배 PCR 을수행하는방법에의해서상기한문제들은해결될수있다. 이러한 DNA 컴퓨팅방법은, 기존의 DNA 컴퓨팅을이용한문제풀이의방식이가능한모든답을생성해낸후에정답을찾아가는소모적조사알고리즘 (exhaustive search algorithm) 을사용하지만, 본 DNA 컴퓨팅방법은생체분자들과생화학적실험방법들을사용하는장점을충분히활용하므로, 정답을많이남게혹은정답을많이생성하게하여, 보다합리적으로문제를해결할수있다. 이하의실시예에서는, 녹는점차이를이용하여가중치의실수표현과, 이렇게가중치가부여된 DNA 를이용하여, 순환외판원문제의해결을구현하고자하였다. 하기실시예에기재된 DNA 의염기서열들은, 단지예시를목적으로한것일뿐, 본발명을특정화시키는것은아니며, 상기에서설명한바와같이, 가중치의차이를표현하기위해서, 녹는점의차이를나타낼수있는서열이라면, 본발명에사용될수있다. 그외에, 하기의실시예는본발명을예시하기위해기재된것일뿐, 이에의해서본발명이한정되는것은아니다. 실시예 1: 순환외판원문제의해결을위한올리고뉴클레오타이드 DNA 의제작 본실시예에서는도 2a 에기재된순환외판원문제를 DNA 컴퓨팅으로해결하고자한것이다. DNA 컴퓨팅에의해순환외판원문제를구현하기위해서는도시와가중치 ( 소요비용 ), 그리고길에해당하는올리고머를각각고안해야한다. 도시는 20 개의뉴클레오타이드로이루어진단일가닥 DNA 로, 균일한녹는점을갖도록고안하였다. 즉, nearestneighbor 모델로는 5 이내의차이를가지고, GC 함량은모두 50% 로동일하도록하였다. 이는표 1 에기재되어있다. 또한, 가중치도 20 개의뉴클레오타이드로이루어진단일가닥 DNA 로고안하였는데, 가중치가낮은것의녹는점을낮게, 가중치가높은것의녹는점을높게하였다. 가중치에대한올리고뉴클레오타이드 DNA 의서열들및각각의녹는점은하기표 2 에기재된바와같다. 한편, 길에해당하는염기서열은도시와가중치가결합된염기서열의상보적인염기서열로서, 자세히는앞쪽도시의후반부 10 개와가중치 20 개, 그리고연결되는뒤쪽도시의전반부 10 개의올리고뉴클레오타이드로이루어지 40mer 의 DNA 가닥에상보적인 40 개의올리고뉴클레오타이드의단일가닥 DNA 로고안되었다. 예를들면, 도시 0 은 5 - AGGCGAGTATGGGGTATATC - 3 이고, 도시 1 은 5 - CCTGTCAACATTGACGCTCA - 3 이라면, 도시 0 과 1 을연결하고가중치가 3 인 (3 - ATGATAGATATGTAGATTCC - 5 ) 간선염기서열은 3 - CCCCATATAGATGATAGATATGTAGATTCCTACTATCTAT - 5 가된다. - 6 -
올리고머의염기서열은염기서열생성기인 NACST/Seq (Shin, S.-Y., Kim, D.-M., Lee, I.-H., and Zhang, B.-T., Evolutionary Sequence Generation for Reliable DNA Computing, Proceedings of 2002 Congress on Evolutionary Computation, IEEE Press, 2002) 를이용하여생성하였다. 도시번호 염기서열 ( 5-3 ) 녹는점 GC함량 0 AGGCGAGTATGGGGTATATC 60.73 50 1 CCTGTCAACATTGACGCTCA 59.24 50 2 TTATGATTCCACTGGCGCTC 59.00 50 3 ATCGTACTCATGGTCCCTAC 56.81 50 4 CGCTCCATCCTTGATCGTTT 58.13 50 5 CTTCGCTGCTGATAACCTCA 59.44 50 6 GAGTTAGATGTCACGTCACG 56.97 50 표 1. 표 2. 가중치 염기서열 ( 3-5 ) 녹는점 GC 함량 3 ATGATAGATATGTAGATTCC 47.89 30 5 GGATGTGATATCGTTCTTGT 54.62 40 7 GGATTAGCAGTGCCTCAGTT 58.37 50 9 TGGCCACGAAGCCTTCCGTT 64.51 60 11 GAGCTGGCTCCTCATCGCGC 68.88 70 실시예 2: DNA 컴퓨팅에의한순환외판원문제의해결 도 2b 는도 2a 에나타내어지는 5 가지종류의가중치를포함하는순환외판원문제를 DNA 컴퓨팅을이용하여해결하기위한전체적인흐름도이다. 단계 1: 하이브리드형성에의한길생성 7 개의도시, 가중치및길에해당하는올리고뉴클레오타이드를모두넣어준뒤에, 온도를 95 로올렸다가상온까지점차식히는방법으로도시와도시가길로연결된가능한모든길을생성 (hybridization) 하였다. 즉, 온도를높여준후, 상온까지온도를서서히낮추어주면, 길에해당하는 40 개의뉴클레오타이드로이루어진단일가닥 DNA( 길 ) 와, 각각 20 개의뉴클레오타이드로이루어진도시에해당하는단일가닥 DNA 및가중치에해당하는단일가닥 DNA 가어닐링 (annealing) 되어, 즉하이브리드형성되어이중가닥 DNA 들이형성된다. 단계 2: 순환외판원문제의해의집합을구성하는 DNA 의작성 상기단계 1) 에서하이브리드형성시킨 40bp 길이의이중가닥 DNA 들은, T4 DNA 라이게이즈 (ligase; 절단되어있는 DNA 를연결시켜주는효소 ) 를사용하여각닉 (nick; DNA 의절단되어있는부위를말함 ) 을연결하였다 ( 이하, 라이게이션 ligation ). 상기단계 1) 에서의하이브리드형성및단계 2) 의라이게이션의수행결과는도 3a 의 (A) 에나타내었다. 또한, 반복적라이게이션 (repetitive ligation) 결과는도 3a 의 (B) 에나타내었다. 상기도 3a 에서보는바와같이, 라이게이션에의해서, 상기단계 1) 에서얻어지는올리고뉴클레오타이드에비하여, 길어진 DNA 가닥이생성됨을확인할수있었다. 이러한길어진 DNA 는, 외판원이방문한도시의순서와가중치 ( 예를들어, 도시간의이동에소요되는상대적인비용 ) 가연결된정보를포함한다. 그러나이들 DNA 에는, 한도시를방문하지않거나, 두번이상방문한경우의수도포함하고있으며, 이는하기의단계들에의해서, 순환외판원문제의해에해당하지않은경우에해당하는 DNA 들은제거될수있다. 단계 3: 해집단에해당하는 DNA 들의여과 (filtering) - 7 -
순환외판원문제에서해의대상에해당되는것들은, ⅰ) 0 번도시로끝날것 ; ⅱ) 0 번도시로시작할것 ; ⅲ) 각도시를한번씩만방문할것의 3 가지조건을충족해야된다. 본발명의 DNA 컴퓨팅방법에서, 상기한조건을모두만족하는 DNA 들은다음과같이분리해낼수있다. ⅰ) 0 번도시로끝날것 : 끝나는도시에해당하는염기서열에상보적인프라이머를사용하여, 연쇄중합반응 (PCR) 을수행하였다. 이를통해 0 번도시로끝나는길에해당하는 DNA 가닥을증폭시킬수있다. PCR 은당업계에통상적으로알려진조건또는당업계의통상적인방법에의해서찾아지는조건하에서수행하였다. PCR 수행후, 얻어지는결과물들은전기영동을수행하여분석하였다. 한편, 외판원이 7 개도시를방문했다면, 그외판원이지나간모든길에해당하는 DNA 는, 0 번도시를두번 ( 시작과끝 ), 다른도시들을한번씩거치기때문에 20bp 길이의도시 8 개와, 각도시의중간에역시 20bp 의가중치를표시하는 7 개시퀀스로이루어진 300bp 의길이를갖게된다. 따라서전기영동수행결과중, 약 300bp 정도의길이에해당하는 DNA 들은, 아가로스젤을오려내어분리한후, 통상의방법으로용출 (elution) 하여얻어진다. 이렇게얻어진 DNA 들은하기 ⅱ) 에서의이차 PCR 을위한주형 (template) DNA 로사용한다. ⅱ) 0 번도시에서시작할것 : 시작하는도시에해당하는염기서열을프라이머로사용하고, 상기 ⅰ) 에서얻어진약 300bp 길이의 DNA 들을주형 DNA 로하여 PCR 을수행하였다. 그런다음, 이를아가로스젤전기영동을수행하고, 약 300bp 부근의밴드에서 DNA 를용출하여분리하였다. 그결과는도 3b 에나타내었다. 도 3b 에서, (A) 는 0 번도시에서끝나는외판원의도시방문경로들에대한 DNA 의증폭결과이며, (B) 는 0 번도시에서시작하는외판원의도시방문경로들에대한 DNA 의증폭결과를나타낸다. 본단계에서분리된 DNA 들은, 동일한도시수를가지면서 ( 그러나, 각도시를한번씩만방문하였는지는확인할수없음.), 0 번도시로끝나고, 동시에 0 번도시로시작하는외판원이움직인길에해당하는 DNA 가닥들을얻을수있다. 단계 4: 각도시를한번씩만방문한외판원의길에해당하는 DNA 의분리 본단계는, 순환외판원문제의상기조건 ⅲ) 을충족하는지를확인하는단계, 즉각도시를한번씩만방문했는지를확인하는단계로서, 이는바이오틴 - 스트렙타비딘 (biotin-streptavidin) 의친화성분리법 (affinity separation) 을이용하여수행하였다. 바이오틴은 244Da 의분자량을가지는비타민의하나이이고아비딘은약 68 kda 의분자량을가지는단백질인데바이오틴은아비딘에아주강한힘으로바인딩하게된다. 이결합의결합상수 (association constant) 는 1015M-1 정도로자연상에존재하는가장강한비공유결합으로알려져있으며많은면역반응연구에사용되고있다. 스트렙타비딘은아비딘과매우유사한구조를가지고있으며역시바이오틴과매우단단히결합을하여아비딘대신에많이사용된다. 각도시에상보적인 DNA 가닥을바이오틴 (biotin) 으로표식한물질을프루브 (probe) 로사용하여, 이에하이브리드형성되는 DNA 가닥만을선택해내는방법으로, 스트렙타빈이붙어있는상자성비드 (paramagnetic beads) 를사용하여수행하였다. 예를들어 1 번도시에상보적인염기서열을가지는 20mer 의단가닥 DNA 의 5'- 말단부분에바이오틴을표식하여이를스트렙타비딘이붙어있는상자성비드와함께 incubation 하게되면바이오틴과스트렙타비딘의강한결합에의해상자성비드에프루브 DNA 가붙게된다. 이렇게결합이일어난비드와결합이일어나지않은단가닥 DNA 는자석으로분리가가능하다. 프루브 DNA 가결합되어있는상자성비드를자석으로분리한뒤에이에 ii) 에서분리한 DNA 가닥들을상온에서 incubation 시켜주면, 1 번도시를포함하는 DNA 가닥들만하이브리드형성을하여상자성비드에붙은채로남게된다. 역시이도자석으로분리가가능하다. 이후에하이브리드형성을하지않은단가닥 DNA 들은씻어서없앤후에, 물을첨가한뒤, 온도를높여해리시켜 DNA 가닥들을분리해낸다. 이러한과정을나머지도시들 (2~6) 에대해서반복한다. 본단계를거침으로써, 순환외판원문제의모든조건을충족시키는 DNA 들을얻어낼수있다. 단계 5: 가중치의합이가장높은 DNA 가닥의분리 - 8 -
상기단계 4 에서분리되는 DNA 가닥들에대하여, 변성온도구배 PCR 을수행하였다. 첫주기의변성온도를 70 로시작하고, 한주기당 1 씩높여주었으며, 마지막의 10 주기는 95 로수행하였다. 그결과를, 도 3b(C) 에나타내었다. 가중치가낮은길에해당하는 DNA 가닥의녹는점은낮고, 가중치가높은것의녹는점은높으므로, 변성온도를낮은온도에서부터시작하여점차높이면서 PCR 을수행하면, 초기의낮은변성온도에서는가중치가작은 DNA 만해리되어 PCR 증폭이수행되지만, 높아진변성온도에서는높은것이든또는낮은것이든 DNA 가모두해리되어 PCR 증폭이수행된다. 즉, DTG-PCR 수행후에가장많이증폭된 DNA 를분리함으로써, 가중치의합이가장작은 DNA 를얻을수있다. 그결과를도 3b 의 (C) 에나타내었다. 실시예 3: 가중치가있는문제의해결에대한 DTG-PCR 의유용성 도 4 는상기실시예 2 의변성온도구배 PCR 를수행한결과, 즉, 본발명의 DNA 컴퓨팅의일례를수행한결과를나타낸다. 본발명의 DNA 컴퓨팅에이용되는변성온도구배 PCR 의유용성을확인하기위하여, 길이가다른두주형 DNA ( 이주형은앞의단계에서 0 으로시작하는도시를걸러내기위해 PCR 을할때에일반 PCR 을한것과 DTG-PCR 을한것을비교한것이다. 즉, 실험도중에얻어진데이터이다. 따라서주형은단계 3 의 i) 에서용출하여얻어진것이고, 프라이머는단계 3 의 ii) 에서사용한것과같은시작하는도시, 즉 0 번도시를사용하였다 ) 가섞여있는것을, 일반적인 PCR 과변성온도구배 PCR 을각각수행한결과, 도 4 에서보는바와같이, 길이가짧은, 즉녹는점이낮은 DNA 가닥이상대적으로많이증폭되었음을확인할수있었다. 발명의효과 이상에서상세히설명한바와같이, 본발명은 DNA 염기서열상에녹는점차이를이용하여실수를구현하는방법으로서, 가중치를포함한그래프문제와기타실수정보부여가필요한 DNA 컴퓨팅응용분야의구현에유용하다. (57) 청구의범위 청구항 1. 가중치의실수정보를 DNA 상에표현하는데있어서, GC 함량과열역학적요소들을고려하여, DNA 가닥의녹는점을다양하게생성하고, 실수의차이를 DNA 의녹는점의차이와대응시켜가중치의실수정보를 DNA 상에표현하는것을특징으로하는가중치의실수정보를 DNA 상에표현하는방법. 청구항 2. 삭제 청구항 3. 제 1 항에있어서, 상기실수정보와대응시킨 DNA 를이용하는것을특징으로하는, 가중치가있는그래프문제를해결하는방법. 청구항 4. 제 3 항에있어서, 상기실수로나타내어지는가중치정보와대응시킨 DNA 를변성온도구배 PCR(denaturation temperature gradient PCR) 을이용함을특징으로하는가중치가있는그래프문제를해결하는방법. 도면 - 9 -
도면 1a 도면 1b 도면 2a - 10 -
도면 2b 도면 3a 도면 3b - 11 -
도면 4-12 -