Simulating Boolean Circuits on a DNA Computer 2002-21610 장정우
About paper Simulating Boolean Circuits on a DNA Computer Mitsunori Ogihara, Animesh Ray 1997 Proceedings of the first annual international conference on computational moleculer biology
Introduction Boolean circuit은 잘 알려진 계산모델 중 하나이다. DNA를 이용해서 대규모의 병렬로 작동하는 Boolean circuit을 simulation 할 수 있다. 이 논문에서는 semi-unbounded fan-in circuit ( AND gate의 fan-in은 2개이고 OR gate의 fan-in은 unlimited) 을 DNA를 이용해서 simulation하는 방법을 다루고 있다.
DNA Operation Gel electrophoresis – 길이 순으로 ordering Appending Cleavage Amplification
Simluation 각각의 gate 에 대해서 대응하는 서로 다른 DNA strand 를 만들어 준다. 전체 population중에서 가 등장한다는 것은 해당 gate의 값이 1이라는 것을 뜻한다. 각각의 는 길이가 L이며 각각 A로 시작해서 B로 끝나고 중간에는 A나 B가 등장하지 않는다. 전체 Population은 P로 최대 fan-out의 크기는 F로 나타낸다. 시작단계에서는 각각 입력에 해당하는 를 pouring한다.
Simulation-OR Gate 존재하는 각각의 개수가 최소 FP개가 되도록 Amplify한다. Simulation 하려고 하는 단계에 해당하는 를 pouring 한다. 각각의 OR gate에 대해 linker를 pouring한후 ligation연산을 이용해서 appending한다. 길이가 2L이 되는 strand들을 뽑아오고 1L짜리 strand들은 버린다. Cleavage를 이용해서 해당 단계의 들만 남긴다.
Simulating-AND Gate OR의 경우와 같다. 단 AND의 경우 두 개의 입력이 모두 1이 되어야 하므로 linker를 만들 때 order를 설정하고 길이가 3L인 strand들만을 남기는 점이 다르다.
Example Input이 1011인 경우 F,P는 각 1이다. x1 x2 x3 x4 OR g5 OR g6 AND g7
Example OR x1 x3 x4 g5 g6 x1g5 x2g5 x3g6 x4g6
Example AND g5 g6 x1 x3 g7 g5g7 g7g6
Analysis 각 단계의 비용 d (log(FP) + c) 크기가 FP보다 커질때 까지 Amplication 각각 2L,3L인 strand들 추출 다시 cleavage로 잘라냄 d (log(FP) + c)
Conclusion 이상에서 보인 바와 같이 Boolean Circuit을 DNA를 이용해서 시뮬레이션 할 수 있으며 비용은 circuit의 depth와 최대 fan-out에 의해서 정의되며 fan-in과는 무관하다. 길이가 40정도인 DNA strand로 1trillion개의 gate로 이루어진 Boolean Circuit을 simulation할 수 있다.