Molecular Beacon-based DNA Computing Model for Maximum Independent Set Problem
Maximum independent set problem is the core issue in NP-complete problems, many problems can be transformed into the maximum independent set problems to solve, so design a good algorithm for solving the problem is very necessary. Molecular beacon is a hairpin-shaped fluorescent probe, which can hybridize with target sequence that is complement to its loop sequence. The specificity of molecular beacon is as high as single base mismatch detection. In this paper, molecular beacon is as for probe, to separation and detection all of the independent sets, fmally by observing the fluorescence to determine whether or not the solution is existence. At the same time, in the establishment of the initial data pool, only one type of DNA molecules was synthesized. In the calculation process, the model does not require the restriction enzyme digestion, gel electrophoresis etc. These steps may avoid possible computational errors and data loss; at the same time, the algorithm also has easy code and reading solution.
DNA computing independent set molecular beacon peptide nucleic acid
Yin Zhixiang Song Bosheng Zhen Cheng Hua Cheng
Department of Mathematics and Physics, Anhui University of Science & Technology, Huainan, Anhui, 232001, China
国际会议
长沙
英文
1902-1905
2010-05-11（万方平台首次上网日期，不代表论文的发表时间）