산자부 과제 (지능형 생물정보 처리 시스템) 2001.4

DNA Computing 011001101010001 ATGCTCGAAGCT

Why DNA Computing? 6.022  1023 molecules / mole Immense, Brute Force Search of All Possibilities Desktop : 106 operations / second Supercomputer : 1012 operations / second 1 mol of DNA : 1026 Favorable Energetic: Gibb’s Free Energy 1 J for 2  1019 operations Storage Capacity: 1 bit per cubic nanometer

Applications Associative Memory Satisfiability and Boolean Operations DNA Adder Finite State Machines Road Coloring DNA Chip Solving NP-hard problems Turing Machine Boolean Circuits

The Problems of DNA Computing It takes TOO long times hybridization/ligation operation over 4 hours In Adleman’s experiments : 7 days! Not Perfect Operation Hybridization Mismatches Mismatched Hybridization Hairpin Hybridization Shifted Hybridization Extraction Errors Volume and Mass to solve a problem False Negatives & False Positives

The Problems of DNA Computing (2) Encoding Problems encoding problem is mapping the problem instance onto a set of DNA molecules and molecular biology protocols so that the resulting products contain an answer to instance of the problem prevent errors enable extraction

국외 연구 동향 미국의 MIT, Caltech, Princeton 대학과 Bell Labs 등에서 기초 연구 활발  구현 사례 없음 유럽에서는 EMCC (European Molecular Computing Consortium)을 구성  EU 차원의 지원 독일의 국립연구소 GMD BioMIP, Dortmund 대학, 영국의 Liverpool 대학에서 분자 컴퓨팅 기반 기술 개발. 일본의 동경대, ETL 국립연구소, ATR 등에서 DNA 컴퓨팅 연구 활발 기존의 연구는 대부분 용액상의 연산 모델임 최근 DNA칩상에서의 분자컴퓨팅 방식이 제안 Intelligent DNA Chip 제시

국내 연구 동향 서울대 ERC 등에서 DNA칩, 단백질칩 등에 관한 연구가 수행중이나 이것은 컴퓨팅의 개념이 아님 본 연구는 일회성의 진단용 칩이 아닌 반복적인 분자수준의 병렬추론을 하는 지능 컴퓨터 개념의 바이오칩 개발을 최종 목적으로 함 서울대 컴퓨터공학부에서(본 연구과제 팀) DNA 컴퓨팅 시뮬레이터 NACST를 개발(1998)하였으나 웻웨어에 의한 구현은 되지 않았음

제1단계 개발 목표 (2000.12 ~ 2003.8) 모델 개발 및 시뮬레이션 실험 검증 2001 10-TSP 해결 제1단계 개발 목표 (2000.12 ~ 2003.8) 모델 개발 및 시뮬레이션 실험 검증 2001 10-TSP 해결 10-HPP 해결 10-SAT 해결 2002 100-TSP 해결 10-TSP 해결 2003 1000-TSP 해결 10-TSP 이상 해결

Solution-based DNA Computing

Adleman’s experiment In 1994 Leonard Adleman demonstrated the potential of using interactions between DNA molecules to carry out “massive parallelism” in a test tube to solve hard combinatorial problems (Hamiltonian Path Problem) 1 3 2 5 6 4

Step 4 : Gel Electrophoresis AGCTTAGG ATGGCATG ATCC TACC Vertex 1 Vertex 2 AGCTTAGG ATGGCATG ATCCTACC 32 bp 16 bp Edge 12 Step 4 : Gel Electrophoresis AGCTTAGG ATGGCATG ATCC TACC Step 1 : Hybridization AGCTTAGGATGGCATGGAATCCGA… TCGAATCC AGCTTAGG ATGGCATG ATCCTACC Bead for vertex 1 Step 2 : Ligation Step 5 : Magnetic Bead Affinity Separation Vertex 1 Vertex 4 AGCTTAGGATGGCATGGAATCCGATGCATGGC TCGAATCC ACGTACCG Step 3 : PCR

Traveling salesman problem Hamiltonian cycle with minimum edge weights 1 3 2 5 6 4 White edges : cost 10 Red edges : cost 1

Gel-based DNA computing for TSP: Encoding (기본 개념) ATAGT GCACG PA1 PA2 A CGTGC AT CGATG CGTGC GCGCGC ATCGA PA2 WAC PC1 PA2 WAB PB1 10 1 B C GCTAC AGCTA TACGG ATCGA PC1 PC2 PB1 PB2

Gel-based DNA computing for TSP: Solution ACGTCTGCCA GCGCGC ACGTCTGCCA GCGCGC GCTACAGCTA GCGCGC P0 W01 P1 W12 P2 W23 ATAGTGCACG P3 W34 GCGCGC AGCTAGGCAT P4 ACCGTCTGCA GCGCGC GCATGCGAAT GCGCGC AGCTACGTAC GCGCGC P0 W60 P6 W56 P5 W45

Gel-based DNA computing for TSP: Encoding (구현 방법) 유전자 알고리즘 (Genetic Algorithm)을 이용해서 sequence 디자인 Mismatch 최소화 Hairpin 생성 억제 AGCGTTTGGC GCGCAAACCG AGCGTAC GCATGCG Mismatched hybridization Shifted hybridization AGCGTTAC GCGA GACG GCTTA GACTT CAATG

Gel-based DNA computing for TSP: Encoding (구현 방법) PCR primer 고려 Weight 표현 정확도

Surface-based DNA Computing

SAT problem Satisfiability Problem 3-SAT Problem Find Boolean values for variables that make the given formula true 3-SAT Problem Every NP problems can be seen as the search for a solution that simultaneously satisfies a number of logical clauses, each composed of three variables.

DNA Chips for DNA Computing I. Make: oligomer synthesis II. Attach (Immobilized): 5’HS-C6-T15-CCTTvvvvvvvvTTCG-3’ III. Mark: hybridization IV. Destroy: Enzyme rxn (ex.EcoRI) V. Unmark * 문제를 만족시키지 않는 모든 strand 제거 VI. Readout: N cycle의 마지막 단계에 해가 남게 되면, PCR로 증폭하여 확인!

Implementing GA

GA는 population을 이용해서 병렬적으로 문제를 해결 Motivation GA는 population을 이용해서 병렬적으로 문제를 해결 + Bio-molecule의 막대한 병렬성 Bio-molecule을 이용하여 GA를 구현

대상문제 우선은 SAT문제를 대상으로 함. Fitness function의 문제만 해결되면 확장 가능.