DNA computing is a novel method for solving a class of intractable computational problem, in which the computing can grow exponentially with problem size. Up to now, many accomplishments have been achieved to improve ...DNA computing is a novel method for solving a class of intractable computational problem, in which the computing can grow exponentially with problem size. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability. Hamilton Graph Problem has been solved by means of molecular biology techniques. A small graph was encoded in molecules of DNA, and the 'operations' of the computation were performed with standard protocols and enzymes. This work represents further evidence for the ability of DNA computing to solve NP-complete search problems.展开更多
The surface-based DNA computing is one of the methods of DNA computing which uses DNA strands immobilized on a solid surface. In this paper, we applied surface-based DNA computing for solving the dominating set proble...The surface-based DNA computing is one of the methods of DNA computing which uses DNA strands immobilized on a solid surface. In this paper, we applied surface-based DNA computing for solving the dominating set problem. At first step, surface-based DNA solution space was constructed by using appropriate DNA strands. Then, by application of a DNA parallel algorithm, dominating set problem was resolved in polynomial time.展开更多
Chain length of closed circle DNA is equal. The same closed circle DNA＇s position corresponds to different recognition sequence, and the same recognition sequence corresponds to different foreign DNA segment, so clos...Chain length of closed circle DNA is equal. The same closed circle DNA＇s position corresponds to different recognition sequence, and the same recognition sequence corresponds to different foreign DNA segment, so closed circle DNA computing model is generalized. For change positive-weighted Hamilton circuit problem, closed circle DNA algorithm is put forward. First, three groups of DNA encoding are encoded for all arcs, and deck groups are designed for all vertices. All possible solutions are composed. Then, the feasible solutions are filtered out by using group detect experiment, and the optimization solutions are obtained by using group insert experiment and electrophoresis experiment. Finally, all optimization solutions are found by using detect experiment. Complexity of algorithm is concluded and validity of DNA algorithm is explained by an example. Three dominances of the closed circle DNA algorithm are analyzed, and characteristics and dominances of group delete experiment are discussed.展开更多
In this paper, the sticker based DNA computing was used for solving the independent set problem. At first, solution space was constructed by using appropriate DNA memory complexes. We defined a new operation called “...In this paper, the sticker based DNA computing was used for solving the independent set problem. At first, solution space was constructed by using appropriate DNA memory complexes. We defined a new operation called “divide” and applied it in construction of solution space. Then, by application of a sticker based parallel algorithm using biological operations, independent set problem was resolved in polynomial time.展开更多
基金Supported by the CNSF(60274026 60174047+1 种基金 30370356) Supported by the Anhui Provinc'e Educational Committee Foundation(2003Kj098)
文摘DNA computing is a novel method for solving a class of intractable computational problem, in which the computing can grow exponentially with problem size. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability. Hamilton Graph Problem has been solved by means of molecular biology techniques. A small graph was encoded in molecules of DNA, and the 'operations' of the computation were performed with standard protocols and enzymes. This work represents further evidence for the ability of DNA computing to solve NP-complete search problems.
文摘The surface-based DNA computing is one of the methods of DNA computing which uses DNA strands immobilized on a solid surface. In this paper, we applied surface-based DNA computing for solving the dominating set problem. At first step, surface-based DNA solution space was constructed by using appropriate DNA strands. Then, by application of a DNA parallel algorithm, dominating set problem was resolved in polynomial time.
基金supported by the National Natural Science Foundation of China(60574041)the Natural ScienceFoundation of Hubei Province(2007ABA407).
文摘Chain length of closed circle DNA is equal. The same closed circle DNA＇s position corresponds to different recognition sequence, and the same recognition sequence corresponds to different foreign DNA segment, so closed circle DNA computing model is generalized. For change positive-weighted Hamilton circuit problem, closed circle DNA algorithm is put forward. First, three groups of DNA encoding are encoded for all arcs, and deck groups are designed for all vertices. All possible solutions are composed. Then, the feasible solutions are filtered out by using group detect experiment, and the optimization solutions are obtained by using group insert experiment and electrophoresis experiment. Finally, all optimization solutions are found by using detect experiment. Complexity of algorithm is concluded and validity of DNA algorithm is explained by an example. Three dominances of the closed circle DNA algorithm are analyzed, and characteristics and dominances of group delete experiment are discussed.
文摘In this paper, the sticker based DNA computing was used for solving the independent set problem. At first, solution space was constructed by using appropriate DNA memory complexes. We defined a new operation called “divide” and applied it in construction of solution space. Then, by application of a sticker based parallel algorithm using biological operations, independent set problem was resolved in polynomial time.
