Một mô hình máy tính DNA để giải quyết vấn đề tô màu đỉnh

Science China Press., Co. Ltd. - Tập 51 - Trang 2541-2549 - 2006
Jin Xu1,2, Xiaoli Qiang1, Fang Gang1, Kang Zhou1
1Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan, China
2Department of Biotechnology, Dalian University, Dalian, China

Tóm tắt

Một máy tính DNA đặc biệt đã được thiết kế để giải quyết vấn đề tô màu đỉnh. Thân chính của loại máy tính DNA này là điện di gel polyacrylamide, có thể được phân loại thành ba phần: vùng melting, vùng dung dịch không thỏa mãn và vùng dung dịch. Gel polyacrylamide này được kết nối với thiết bị điều chỉnh nhiệt độ, và nhiệt độ liên quan lần lượt là T_m1, T_m2 và T_m3. Hơn nữa, với trọng tâm vào phương pháp mã hóa, chúng tôi đã thành công trong việc thực hiện thí nghiệm trên một đồ thị với 5 đỉnh. Trong bài viết này, chúng tôi giới thiệu cấu trúc cơ bản, nguyên lý và phương pháp hình thành các chuỗi DNA thư viện.

Từ khóa

#máy tính DNA #tô màu đỉnh #điện di gel polyacrylamide #chuỗi DNA thư viện

Tài liệu tham khảo

Adleman L. Molecular computation of solution to combinatorial problems. Science, 1994, 66(11): 1021–1024

Lipton R J. DNA solution of hard computational problems. Science, 1995, 268(28): 542–545

Roweis S, Winfree E, Burgoyne R, et al. A sticker based architecture for DNA computation. In: Baum E B, et al., eds. DNA Based Computers, Proc. 2nd Annual Meeting. Princeton, 1999, 1–27

Braich R S, Chelyapov N, Johnson C, et al. Solution of a 20-variable 3-SAT problem on a DNA computer. Science, 2002, 296(19): 499–502

Sakamoto K, Gouzu H, Komiya K, et al. Molecular computation by DNA hairpin formation. Science, 2000, 288: 1223–1226

Ouyang Q, Kaplan P D, Liu S M, et al. DNA solution of the maximal clique problem. Science, 1997, 278(17): 446–449

Liu Q H, Wang L M, Frutos A G, et al. DNA computing on surfaces. Nature, 2000, 403(13): 175–178

Benenson Y, Gil B, Ben-Dor U, et al. An autonomous molecular computer for logical control of gene expression. Nature, 2004, 429(27): 1–6

Benenson Y, Paz-Elizur T, Adar R, et al. Programmable and autonomous computingmachine made of biomolecules. Nature, 2001, 414(22): 430–434

Bondy J A, Murty U S R. Graph Theory with Applications. London, Basingtoke and New York: The Macmillan Press Ltd., 1976

Gibbons A. Algorithmic Graph Theory. Cambridge, London, New York: Cambridge University Press, 1985

Jensen T R, Toft B. Graph Coloring Problems. New York/Singapore: A Wiley-Interscience Publication, John Wiley & Sons, 1995

Wood D C. A technique for coloring a graph applicable to large-scale optimization problems. Comput J, 1969, 12: 317

Karger D, Motwani R, Sudan M. Approximate graph coloring by semidefinite programming. Journal of ACM, 1998, 45(2): 246–265

Halldorsson M M. A still better performance guarantee for approximate graph coloring. Inf Proc Lett, 1994, 45: 19–23

Xu Jin, Bao Zheng. Neural network and graph theory. Sci China Ser F-Inf Sci, 2002, 45(1): 1–24

Blas A D, Jagota A, Hughey R. Energy function-based approaches to graph coloring. IEEE Transactions on Neural Networks, 2002, 13(1): 81–90

Goldberg D. Genetic Algorithm in Search, Optimization and Machine Learning. Boston: Addison-Wesley Publishing, 1989

Xu Jie, Du Wen, Li Zongping, et al. Study on the plan of using shunting locomotives based on Simulated Annealing Algorithm and Graph Coloring. Journal of The China Railway Society, 2003, 25(3): 24–30

Liu Yachun, Xu Jin, Pan Linqiang, et al. DNA solution of a graph coloring problem. J Chem Inf Comput Sc, 2002, 42(3): 524–528

Liu Wenbin, Xu Jin. A DNA algorithm for the graph coloring problem. J Chem Inf Comput, 2002, 42: 1176–1178

Gao Lin, Xu Jin. A DNA algorithm for graph vertex coloring problem. Acta Electronic Sinica, 2003, 31(4): 494–496

Dorit S. Hochbaum. Approximation Algorithms for NP-hard Problems. Boston: PWS Publishing Company, 1997

Zhang Fengyue. The DNA computing model of 0-1programming problem and timetable problem. The Degree of Doctor of Philosophy, Huazhong University of Science and Technology, June, 2004

Xu Jin, Huang Buyi. DNA Computer Principle, Advances and Difficulties (II): Formation of Data Base—DNA Synthesis. Chin J Comput, 2005, 28(10): 1–9

Lu Shengdong. Current Protocols in Molecular Biology. Beijing: Chinese Academy of Medical Science & Peking Union Medical College Press, 1999. 9

Fumiaki Tanaka, Atsushi Kameda, Masahito Yamamoto. Design of nucleic acid sequences for DNA computing based on a themodynamic approach. Nucleic Acids Res, 2005, 33(3): 903–911

Garzon M, Deaton R J. Codeword design and information encoding in DNA ensemble. Nat Comput, 2004, 3: 253–292

Thông tin
Thông tin xuất bản

Science China Press., Co. Ltd.

Tập 51

2541-2549

Thông tin tác giả