DNAComputer

DNA 컴퓨터는 기존 컴퓨터의 이진법을 DNA를 구성하는 아데닌(A), 사이토신(C), 구아닌(G), 타이민(T) 등 네 가지 요소로 바꾼 뒤 문제를 지닌 길다란 DNA 가닥 하나와 해답을 지닌 짧은 DNA 가닥들을 만들어 나가는 방식으로 만들어진다.

2001년 11월자 네이쳐에는 와이즈만 연구소 에서 연구한 DNAComputer에 관한 연구가 실렸다. Programmable and autonomous computing machine made of biomolecules

논문원문은 김우재에게 있습니다. 관심있으신분은 메일주시면 보내드리겠습니다.

DNA Based Computers
IT와 바이오의 만남.. DNA컴퓨터와 생체인증

김우재의 부족한 컴퓨터지식으로는 정확한 원리가 이해가 안됩니다. 논문 보내드릴테니 간단하게 소개 해주실 수 있는 유능한 프로그래머 계십니까?

오류의 위험이 있기는 하지만 이번 달 과학동아에 아주 쉽게 설명되어 있더군요. TSP를 DNAComputer로 푸는 예를 서울, 대구, 대전, 부산(기억이 맞다면) 네 도시와 그 사이를 다니는 버스로 간략화 해서 DNAComputer가 해를 어떻게 구하는지 설명합니다.

논문 좀 보내주세요. 근데 사실 DNAComputer는 공학자가 이해하기가 쉽지 않을 걸요. 오히려 생물학자들이 이해하기가 더 나을 거 같아요. 기본적인 아이디어는 time complexity 를 space complexity 로 바꾸었다는 것이고, 그 방법은 바로 DNA 를 사용하였다는 것입니다. 1994년 science 지였나? 처음에는 TSP로 소개되었고, 후에 Maximal clique, 체스... 뭐 몇몇 논문이 나왔지만, 시험관에서의 DNA 반응의 한계가 역시 존재한다는 점에서 조금 시들해졌다고 할까? 시험관 크기가 e-tube 크기가 아니라 비이커만하면 균일한 반응이 일어날 수가 없잖아요. 네이쳐에 실렸으면 뭔가 획기적인 전기가 있었던 것일지 궁금하군요. 가능하면 읽어보고 제가 설명할 수 있는 부분이 있음 올릴께요. 부탁. --지상은

이 논문의 특징은 DNAComputer를 프로그래밍 할 수 있도록 했다는 점에 있는 것 같습니다. DNAComputer 가 이제까지는 초기 컴퓨터들처럼 프로그래밍이 가능하지 않은 구조였던데 비해서, 이것은 범용으로 쓸 수 있다는 얘기가 되지 않을까 싶습니다.

이 논문의 아이디어는 software 와 input을 double strand DNA 로 하면서, software molecule들, 즉 finite state automata에서 각각 transition을 선택할 수 있도록 하였습니다. 그것이 프로그램을 바꿔주는 효과를 내게 하죠.

하지만 이 논문에서도 역시 극복 못한 근본적인 한계가 있습니다. DNAcomputer 는 time complexity를 space complexity 로 바꾸는 것에 불과하기 때문에, 계산해야 하는 복잡성이 작을 때는 돌아가지만, 복잡성이 증가하면, 역시 한계를 드러낼 수 밖에 없습니다. DNA 같은 biomolecule 들이 균일한 반응을 일으키기 위해서는 충분히 섞일 수 있을 정도의 작은 space에서 반응이 이루어져야 하는데, space 역시 exponential 하게, 즉, 10^2, 10^3, 10^4... 10^100... 이런 식으로 증가할 수는 없기 때문에, 역시 complexity 가 exponential 하게 증가하는 NP problem을 해결할 수 있는 방법이 되지는 못한다는 것이 현재까지의 견해입니다.

이 논문에서는 예를 들어 "abaaba" 라는 어떤 sequence를 어떤 소프트웨어(프로그램), 다시 말해서 어떤 finite state automata 에서 만들 수 있는지 없는지와, 만들 수 있다면 최종 state 가 S0 인지, S1인지를 알려 줍니다.

일단 Figure 1에서 보는바와 같이 소프트웨어(finite state automata)가 A1-A7 까지 7가지가 있습니다. 그리고 그 각각의 finite state automata에서 transition 은 8개가 됩니다. S0에서 S1 으로 가는 것과, S1에서 S0으로 가는 것 합하면 2개, S0, S1 이 스스로 도는 것 2개, 거기다가 a, b를 만드는 것 2개 해서 2*2*2 모두 곱하면 8가지의 transition 이 나오죠.

Transition molecule 은 Figure 2-a 에서 보는 것처럼 만듭니다. 공통적으로 FokI 이라는 제한효소로 인지되는 부분이 있고, sticky end 는 어떤 state 에서 어떤 state에서 가는지와 a를 만드느냐 b를 만드느냐에 따라 약간씩 다르게 만듭니다. 중요한 것은 FokI 이 인지하는 부분과 자르는 부분에 차이가 있다는 것입니다. 옆으로 한참 가서 자르는 특성을 사용하는 것입니다.

Input molecule 은 우리가 생성하고자 하는 "abaaba" 같은 sequence입니다. Figure 2-b 에서는 앞부분이 "ab" 로 시작하는 sequence 이죠. "ab" 의 앞부분은 어차피 떨어져 나갈 부분으로 일종의 Begin state 에 해당한다고 보시면 됩니다. 디자인을 그렇게 한 거죠.

Symbol 과 state 는 Figure 2-c에서 보는 것과 같이 만듭니다.

이제 Figure 2-d의 mechanism을 보시죠. 맨 처음에 input molecule을 FokI 으로 짤라 버립니다. Begin state 떨어져 나가고, 그 다음에 input molecule 의 "a" 부분이 노출되게 됩니다. 그 다음에는 ligation을 시키는 거죠. A1 - A7에 해당하는 프로그램 종류에 따라서 transition molecule 들을 넣는 조합이 다르겠지만, 일단 transition T1이 있으면 당연히 T1이 달라붙습니다. 다른 건 상보적이지 않아서 붙지를 않습니다.

그 다음에 또 자릅니다. 이번에는 새로 붙은 T1 의 FokI 부위가 인지되어서, 한참 오른쪽의 부분이 짤리니까, input molecule 의 "b" 부분이 노출되게 됩니다. 이런 식으로 계속 반복하다 보면... 결국은 최종적으로 a 나 b 같은 sequence 들은 아무것도 안 남게 됩니다. 그리고 맨 마지막 그림에서 볼 수 있듯이, output reporter를 보면 맨 마지막에 끝나는 state 가 S0 인지 S1인지 알 수 있습니다. 이것이 프로그램이 끝까지 수행될 때 나오는 결과물이고, 만약 S1 이건 S0이건 이것이 나오지 않는다면, 그건 그 프로그램으로는 input sequence를 만들 수 없다는 얘기가 됩니다.

실제 실험 결과가 Figure 3 의 전기영동 결과로 display 됩니다. Figure 3-a 에 보면 sequence "aa" "aba" "aabb" 는 프로그램 A1 이 generation 할 수 있다는 의미이고, 최종 종료되는 state 는 각각 S0, S1, S0 임을 알 수 있습니다. 조금 더 가면, 프로그램 A2에서 "aabb" 는 생성할 수 없음을 알 수 있습니다.

논문에는 parallel computation 과 non-deterministic computation 등 몇가지 더 있는데, 결국 위 개념의 확장판에 불과하다고 보여집니다.

컴파일러 공부하다가 생각이 든건데, 이게 지금 어떤 모델에서 어떤 sequence 가 생성(production) 되는지를 FiniteStateAutomata 로 본 거거든요. TransformationalGrammar 중에서 Regular Grammar 로 lexical analysis 한 거죠. 그럼 사람들이 다음 단계는 뭘 생각할까요? 당연히 Context Free Grammar 로 syntax analysis 하는게 되겠죠. 이건 순차적으로 반응이 일어나서는 안되고, 떨어진 곳끼리 상호작용을 해야하기 때문에 훨씬 복잡할 걸로 생각되지만, DNA 가 실제로 그렇게 작동을 하잖아요. 방법은 당연히 있을테지만, 시험관안에서 어떻게 만드느냐의 디자인 문제일 것 같군요. 관심 있으신 분은 생각해 보세요. 이거 처음으로 해낼수만 있다면, Science 나 Nature 에 논문 실을 수 있습니다.

디자인도 문제겠지만, '시험관안'이라는 공간의 문제도 상당히 크죠?

See also TuringMachine

생명과학분류 컴퓨터분류