作者机构:
[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.
期刊:
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.
作者机构:
[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.
摘要:
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.
期刊:
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.
摘要:
By means of one photon absorption laser-induced resonance fluorescence at 599.5 nm the relative concentrations of the amidogen (NH2) radical in the ammonia (NH3) radio-frequency (rf) plasma source were measured under different discharge pressures and rf powers. The time dependence of the fluorescence which comes from the radiation 101-211 of the P-branches of the Σ vibronic sub-bands can be described by a single-exponential decay. The decay time of NH2(A2A1) Σ (0, 9, 0) rovibronic state was determined. The spatial dependence of the NH2 density in the discharge tube was measured.