作者机构:
[Pan, LQ] Huazhong Univ Sci & Technol, Dept Control Sci & Engn, Wuhan 430074, Peoples R China.;Nanhua Univ, Inst Engn & Technol, Dept Math & Phys, Hengyang 421001, Peoples R China.
通讯机构:
[Pan, LQ] H;Huazhong Univ Sci & Technol, Dept Control Sci & Engn, Wuhan 430074, Peoples R China.
关键词:
DNA computing;NP-complete problem;minimal vertex cover problem
摘要:
DNA computing was proposed for solving a class of intractable computational problems, of which the computing time will grow exponentially with the problem size. Up to now, many achievements have been made to improve its performance and increase its reliability. It has been shown many times that the surface-based DNA computing technique has very low error rate, but the technique has not been widely used in the DNA computing algorithms design. In this paper, a surface-based DNA computing algorithm for minimal vertex cover problem, a problem well-known for its exponential difficulty, is introduced. This work provides further evidence for the ability of surface-based DNA computing in solving NP-complete problems.
作者机构:
[Zhu D.-M.] Department of Mathematics, East China Normal University, Shanghai 200062, China;Department of Mathematics and Physics, Nanhua University, Hengyang 421001, China;[Li X.-Y.] Department of Mathematics, East China Normal University, Shanghai 200062, China, Department of Mathematics and Physics, Nanhua University, Hengyang 421001, China
通讯机构:
[De-ming Zhu] D;Department of Mathematics, East China Normal University, Shanghai, China
关键词:
global existence;positive periodic solution;coincidence degree;distributed delay model
摘要:
By using the continuation theorem of Mawhin's coincidence degree theory, a sufficient condition is derived for the existence of positive periodic solutions for a distributed delay competition model {u'(t) = u(t)[r_1(t)-a_1(t)u(t)-b_1(t) ∫from x = -T to x = 0 of L_1(s)u(t+s)ds-c_1(t)∫from x = -T to x = 0 of K_1(s)v(t+s)ds], v'(t) = u(t)[r_2(t)-a_2(t)v(t)-b_2(t) ∫from x = -T to x = 0 of L_2(s)v(t+s)ds-c_2(t)∫from x = -T to x = 0 of K_2(s)u(t+s)ds], where r_1 and r_2 are continuous ω-periodic functions in R_+ = [0,∞), b_i (i = 1,2) is nonnegative continuous ω-periodic function in R_+ = [0,∞), b_i (i = 1,2) is nonnegative continuous ω-periodic function in R_+ = [0,∞), ω and T are positive constants, K_i, L_i ∈ C([-T,0], (0,∞)) and ∫from x = -T to x = 0 of K_i(s)ds = 1, ∫from x = -T to x = 0 of L_i(s)ds = 1, i = 1,2. Some known results are improved and extended.
作者机构:
[Pan, LQ] Huazhong Univ Sci & Technol, Dept Control Sci & Engn, Wuhan 430074, Peoples R China.;Nahua Univ, Inst Engn & Technol, Dept Math & Phys, Hengyang 421001, Peoples R China.
通讯机构:
[Pan, LQ] H;Huazhong Univ Sci & Technol, Dept Control Sci & Engn, Wuhan 430074, Peoples R China.
关键词:
DNA computing;Maximal clique problem;NP-complete problem
摘要:
The maximal clique problem is an NP (nondeterministic polynomial time)-complete problem. We present an algorithm that solves maximal clique problem within the framework of a surface-based model of computation. The time complexity of our algorithm is O(n2), and the number of kinds of short oligonucleotides needed to encode maximal clique problem is n + 3, where n is the size of the graph. In our algorithm, immobilizing DNA (deoxyribonucleic acid) strands to a solid surface reduces the possibility of error resulting from the loss of DNA strands in solution. A solution-based algorithm solving maximal clique problem has previously been proposed by Qi Ouyang et al.. In their algorithm, the number of enzyme is equal to the number of vertices of the graph, which causes the difficulty of encoding and scaling up, because the DNA sequences of restriction enzyme sites should not be present in otherwhere. Using surface-based model, we designed an algorithm for maximal clique problem, which needs only one enzyme.
期刊:
Journal of Chemical Information and Modeling,2002年42(3):524-528 ISSN:1549-9596
通讯作者:
Liu, YC
作者机构:
[Liu, YC] Nanhua Univ Hengyang, Dept Math & Phys Sci, Hunan 421001, Peoples R China.;Huazhong Univ Sci & Technol, Dept Control Sci & Engn, Wuhan 430074, Peoples R China.
通讯机构:
[Liu, YC] N;Nanhua Univ Hengyang, Dept Math & Phys Sci, Hunan 421001, Peoples R China.
摘要:
The graph-theoretic parameter that bas probably received the most attention over the years is the chromatic number. As is well-Known, the coloring problem is an NP-Complete problem. In this paper, it has been solved by means of molecular biology techniques. The algorithm is highly parallel and has satisfactory fidelity. This work shows further evidence for the ability of DNA computing to solve NP-Complete problems.
摘要:
In this paper we consider a kind of nonlinear neutral difference equations with continuous arguments. First, we obtain some sufficient conditions for the oscillation. When the coefficients in the equations are constants, these conditions are also necessary. Secondly, we derive a necessary and sufficient condition for the nonoscillation. Finally, we give a sufficient condition for the asymptotic behavior of the nonoscillatory solutions.
作者机构:
[李先义; 王礼广] Department of Mathematics, College of Mathematics/Physics, Nanhua University, Hengyang 421001, China;[田泽荣] Department of Computer, Mathematics/Computer Science College, Hunan Normal University, Changsha 410081, China
期刊:
Journal of Chemical Information and Modeling,2002年42(3):529-533 ISSN:1549-9596
通讯作者:
Liu, YC
作者机构:
[Liu, YC] Nanhua Univ, Inst Engn & Technol, Dept Math & Phys Sci, Hengyang 421001, Hunan, Peoples R China.;Xinjiang Univ, Inst Math & Phys, Urumqi 830046, Xinjiang, Peoples R China.;Huazhong Univ Sci & Technol, Dept Control Sci & Engn, Wuhan 430074, Hubei, Peoples R China.
通讯机构:
[Liu, YC] N;Nanhua Univ, Inst Engn & Technol, Dept Math & Phys Sci, Hengyang 421001, Hunan, Peoples R China.
摘要:
Some 2-D and 3-D graphical representations of DNA sequences have been given by Nandy, Leong and Mogenthaler, and Randic et al., which give visual characterizations of DNA sequences. In this paper, we presented a novel graphical representation of DNA sequences by taking four special vectors in 2-D Cartesian coordinate system to represent the four nucleic acid bases in DNA sequences, so that a DNA sequence is denoted on a plane by a directed walk. It is shown that the new graphical representation of DNA sequences has lower or nondegeneracy.
摘要:
The oscillation and nonoscillation of the advanced differential equations x′(t)−p(t)x(t+τ)=0, t⩾t0(∗) and x′(t)−∑i=1npi(t)x(t+τi)=0, t⩾t0(∗∗) are investigated, where p(t),pi(t)∈C([t0,∞),[0,∞)), τ and τi are positive constants. At first, a sharp sufficient condition for the oscillation of Eq. (∗) is obtained, then the result is generalized to Eq. (∗∗). These results improve the corresponding conclusions derived by Ladas and Stavroulakis (J. Differential Equations 44 (1982) 134–152). Next, two examples are given to illustrate the advantages of our results. Finally, the sufficient conditions for these two equations to be nonoscillatory are also obtained.