Molecular computation by DNA hairpin formation

被引:301
作者
Sakamoto, K
Gouzu, H
Komiya, K
Kiga, D
Yokoyama, S
Yokomori, T
Hagiya, M
机构
[1] Univ Tokyo, Grad Sch Sci, Dept Biochem & Biophys, Bunkyo Ku, Tokyo 1130033, Japan
[2] Univ Tokyo, Grad Sch Sci, Dept Informat Sci, Bunkyo Ku, Tokyo 1130033, Japan
[3] Waseda Univ, Sch Educ, Dept Math, Shinjuku Ku, Tokyo 1698050, Japan
关键词
D O I
10.1126/science.288.5469.1223
中图分类号
O [数理科学和化学]; P [天文学、地球科学]; Q [生物科学]; N [自然科学总论];
学科分类号
07 ; 0710 ; 09 ;
摘要
Hairpin formation by single-stranded DNA molecules was exploited in a DNA-based computation in order to explore the feasibility of autonomous molecular computing. An instance of the satisfiability problem, a famous hard combinatorial problem, was solved by using molecular biology techniques. The satisfiability of a given Boolean formula was examined autonomously, on the basis of hairpin formation by the molecules that represent the formula. This computation algorithm can test several clauses in the given formula simultaneously, which could reduce the number of Laboratory steps required for computation.
引用
收藏
页码:1223 / 1226
页数:4
相关论文
共 26 条
[11]  
LABEAN TH, 1999, P 5 INT M DNA BAS CO, P121
[12]   DNA SOLUTION OF HARD COMPUTATIONAL PROBLEMS [J].
LIPTON, RJ .
SCIENCE, 1995, 268 (5210) :542-545
[13]   DNA computing on surfaces [J].
Liu, QH ;
Wang, LM ;
Frutos, AG ;
Condon, AE ;
Corn, RM ;
Smith, LM .
NATURE, 2000, 403 (6766) :175-179
[14]  
MITCHELL D, 1992, AAAI-92 PROCEEDINGS : TENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, P459
[15]  
MORIMOTO N, 1999, DIMACS SERIES DISCRE, V48, P193
[16]  
OGIHARA M, 1999, DIMACS SERIES DISCRE, V48, P255
[17]   DNA solution of the maximal clique problem [J].
Ouyang, Q ;
Kaplan, PD ;
Liu, SM ;
Libchaber, A .
SCIENCE, 1997, 278 (5337) :446-449
[18]  
Paun G., 1998, DNA COMPUTING NEW CO
[19]  
REIF JH, 1999, DIMACS, V48, P217
[20]   State transitions by molecules [J].
Sakamoto, K ;
Kiga, D ;
Komiya, K ;
Gouzu, H ;
Yokoyama, S ;
Ikeda, S ;
Sugiyama, H ;
Hagiya, M .
BIOSYSTEMS, 1999, 52 (1-3) :81-91