DNA computing the Hamiltonian path problem

The directed Hamiltonian path (DHP) problem is one of the hard computational problems for which there is no practical algorithm on a conventional computer available. Many problems, including the traveling sales person problem and the longest path problem, can be translated into the DHP problem, which implies that an algorithm for DHP can also solve all the translated problems. To study the robustness of the laboratory protocol of the pioneering DNA computing for the DHP problem performed by Leonard Adleman (1994), we investigated how the graph size, multiplicity of the Hamiltonian paths, and the size of oligonucleotides that encode the vertices would affect the laboratory procedures. We applied Adleman's protocol with 18-mer oligonucleotide per node to a graph with 8 vertices and 14 edges containing two Hamiltonian paths (Adleman used 20-mer oligonucleotides for a graph with 7 nodes, 14 edges and one Hamiltonian path). We found that depending on the graph characteristics such as the number of short cycles, the oligonucleotide size, and the hybridization conditions that used to encode the graph, the protocol should be executed with different parameters from Adleman's.     

基于质粒DNA匹配问题的分子算法

给定无向图,图的最小极大匹配问题是寻找每条边都不相邻的最大集中的最小者,这个问题是著名的NP-完全问题.1994年Adleman博士首次提出用DNA计算解决NP-完全问题,以编码的DNA序列为运算对象,通过分子生物学的运算操作解决复杂的数学难题,使得NP-完全问题的求解可能得到解决.提出了基于质粒DNA的无向图的最大匹配问题的DNA分子生物算法,通过限制性内切酶的酶切和凝胶电泳完成解的产生和最终接的分离,依据分子生物学的实验手段,算法是有效并且可行的.     

Is optimal solution of every NP-complete or NP-hard problem determined from its characteristic for DNA-based computing

Cook's Theorem [Cormen, T.H., Leiserson, C.E., Rivest, R.L., 2001. Introduction to Algorithms, second ed., The MIT Press; Garey, M.R., Johnson, D.S., 1979. Computer and Intractability, Freeman, San Fransico, CA] is that if one algorithm for an NP-complete or an NP-hard problem will be developed, then other problems will be solved by means of reduction to that problem. Cook's Theorem has been demonstrated to be correct in a general digital electronic computer. In this paper, we first propose a DNA algorithm for solving the vertex-cover problem. Then, we demonstrate that if the size of a reduced NP-complete or NP-hard problem is equal to or less than that of the vertex-cover problem, then the proposed algorithm can be directly used for solving the reduced NP-complete or NP-hard problem and Cook's Theorem is correct on DNA-based computing. Otherwise, a new DNA algorithm for optimal solution of a reduced NP-complete problem or a reduced NP-hard problem should be developed from the characteristic of NP-complete problems or NP-hard problems.     

Hairpin formation in DNA computation presents limits for large NP-complete problems

Recently, several DNA computing paradigms for NP-complete problems were presented, especially for the 3-SAT problem. Can the present paradigms solve more than just trivial instances of NP-complete problems? In this paper we show that with high probability potentially deleterious features such as severe hairpin loops would be likely to arise. If DNA strand x of length n and the 'complement' of the reverse of x have l match bases, then x forms a hairpin loop and is called a (n,l)-hairpin format. Let gamma=2l/n. Then gamma can be considered as a measurement of the stability of hairpin loops. Let p(n,l) be the probability that a n-mer DNA strand is a (n,l)-hairpin format, and q(n,l)((m)) be the probability that m ones are chosen at random from 4(n) n-mer oligonucleotides such that at least one of the m ones is a (n,l)-hairpin format. Then, q(n,l)((m))=1-(1-p(n,l))(m)=mp(n,l). If we require q(n,l)((m))相似文献   

Molecular solutions to the binary integer programming problem based on DNA computation

Binary optimization is a widely investigated topic in integer linear programming. This study proposes a DNA-based computing algorithm for solving the significantly large binary integer programming (BIP) problem. The proposed approach is based upon Adleman and Lipton's DNA operations to solve the BIP problem. The potential of DNA computation for the BIP problem is promising given the operational time complexity of O(nxk).     

A new solution for maximal clique problem based sticker model

In this paper, we use stickers to construct a solution space of DNA for the maximal clique problem (MCP). Simultaneously, we also apply the DNA operation in the sticker-based model to develop a DNA algorithm. The results of the proposed algorithm show that the MCP is resolved with biological operations in the sticker-based model for the solution space of the sticker. Moreover, this work presents clear evidence of the ability of DNA computing to solve the NP-complete problem. The potential of DNA computing for the MCP is promising given the operational time complexity of O(nxk).     

A new fast algorithm for solving the minimum spanning tree problem based on DNA molecules computation

The minimum spanning tree (MST) problem is to find minimum edge connected subsets containing all the vertex of a given undirected graph. It is a vitally important NP-complete problem in graph theory and applied mathematics, having numerous real life applications. Moreover in previous studies, DNA molecular operations usually were used to solve NP-complete head-to-tail path search problems, rarely for NP-hard problems with multi-lateral path solutions result, such as the minimum spanning tree problem. In this paper, we present a new fast DNA algorithm for solving the MST problem using DNA molecular operations. For an undirected graph with n vertex and m edges, we reasonably design flexible length DNA strands representing the vertex and edges, take appropriate steps and get the solutions of the MST problem in proper length range and O(3m + n) time complexity. We extend the application of DNA molecular operations and simultaneity simplify the complexity of the computation. Results of computer simulative experiments show that the proposed method updates some of the best known values with very short time and that the proposed method provides a better performance with solution accuracy over existing algorithms.     

The k partition-distance problem

Many applications of data partitioning (clustering) have been well studied in bioinformatics. Consider, for instance, a set N of organisms (elements) based on DNA marker data. A partition divides all elements in N into two or more disjoint clusters that cover all elements, where a cluster contains a non-empty subset of N. Different partitioning algorithms may produce different partitions. To compute the distance and find the consensus partition (also called consensus clustering) between two or more partitions are important and interesting problems that arise frequently in bioinformatics and data mining, in which different distance functions may be considered in different partition algorithms. In this article, we discuss the k partition-distance problem. Given a set of elements N with k partitions of N, the k partition-distance problem is to delete the minimum number of elements from each partition such that all remaining partitions become identical. This problem is NP-complete for general k?>?2 partitions, and no algorithms are known at present. We design the first known heuristic and approximation algorithms with performance ratios 2 to solve the k partition-distance problem in O(k?·?ρ?·?|N|) time, where ρ is the maximum number of clusters of these k partitions and |N| is the number of elements in N. We also present the first known exact algorithm in O(??·?2(?)·k(2)?·?|N|(2)) time, where ? is the partition-distance of the optimal solution for this problem. Performances of our exact and approximation algorithms in testing the random data with actual sets of organisms based on DNA markers are compared and discussed. Experimental results reveal that our algorithms can improve the computational speed of the exact algorithm for the two partition-distance problem in practice if the maximum number of elements per cluster is less than ρ. From both theoretical and computational points of view, our solutions are at most twice the partition-distance of the optimal solution. A website offering the interactive service of solving the k partition-distance problem using our and previous algorithms is available (see http://mail.tmue.edu.tw/~yhchen/KPDP.html).     

Progressive tree neighborhood applied to the maximum parsimony problem

The Maximum Parsimony (MP) problem aims at reconstructing a phylogenetic tree from DNA sequences while minimizing the number of genetic transformations. To solve this NP-complete problem, heuristic methods have been developed, often based on local search. In this article, we focus on the influence of the neighborhood relations. After analyzing the advantages and drawbacks of the well-known Nearest Neighbor Interchange (NNI), Subtree Pruning Regrafting (SPR) and Tree-Bisection-Reconnection (TBR) neighborhoods, we introduce the concept of Progressive Neighborhood (PN) which consists in constraining progressively the size of the neighborhood as the search advances. We empirically show that applied to the Maximum Parsimony problem, this progressive neighborhood turns out to be more efficient and robust than the classic neighborhoods using a descent algorithm. Indeed, it allows to find better solutions with a smaller number of iterations or trees evaluated.     

Combining land cover mapping of coastal dunes with vegetation analysis

Question: Coastal dune systems are characterized by a natural mosaic that promotes species diversity. This heterogeneity often represents a severe problem for traditional mapping or ground survey techniques. The work presented here proposes to apply a very detailed CORINE land cover map as baseline information for plant community sampling and analysis in a coastal dune landscape. Location: Molise coast, Central Italy. Method: We analysed through an error matrix the coherence between land cover classes and vegetation types identified through a field survey. The CORINE land cover map (scale 1: 5000) of the Molise coast was used with the CORINE legend expanded to a fourth level of detail for natural and semi‐natural areas. Vegetation data were collected following a random stratified sampling design using the CORINE land cover classes as strata. An error matrix was used to compare, on a category‐by‐category basis, the relationship between vegetation types (obtained by cluster analyses of sampling plots) and land cover classes of the same area. Results: The coincidence between both classification approaches is quite good. Only one land cover class shows a very weak agreement with its corresponding vegetation type; this result was interpreted as being related to human disturbance. Conclusions: Since it is based on a standard land cover classification, the proposal has a potential for application to most European coastal systems. This method could represent a first step in the environmental planning of coastal systems.     

A neural network for the Steiner minimal tree problem

The problem of finding the shortest tree connecting a set of points is called the Steiner minimal tree problem and is nearly three centuries old. It has applications in transportation, computer networks, agriculture, telephony, building layout and very large scale integrated circuit (VLSI) design, among others, and is known to be NP-complete. We propose a neural network which self-organizes to find a minimal tree. Solutions found by the network compare favourably with the best known or optimal results on test problems from the literature. To the best of our knowledge, the proposed network is the first neural-based solution to the problem. We show that the neural network has a built-in mechanism to escape local minima.     

Scalability of the surface-based DNA algorithm for 3-SAT

Since Adleman first proposed DNA computing for the Hamiltonian path problem, several authors have reported DNA computing for 3-SAT. Previous research presented DNA computing on surfaces and demonstrated how to solve a four-variable four-clause instance of 3-SAT, and claimed that the surface-based approach was designed to scale up to larger problems. In this paper we establish an error model for the incomplete "mark" and imperfect "destroy" operations. By using the error model we argue that no matter how large the "mark" and "destroy" rates are we can always give satisfiable instances of 3-SAT such that no DNA strands remain on the surface at the end of the computation. By the surface-based approach the satisfiable instances of 3-SAT would be misdetermined to be unsatisfiable. Thus, the error leads to an incorrect result of the SAT computation. Furthermore, given the "mark" rate p and the "not-destroy" rate rho, we find that the approach can only solve at most N-variable instances of 3-SAT problems, where N=[(2+beta(2)+2+2 square root beta (2))/beta(2)] in which beta=1-1/(p+rhoq) and q=1-p and [a] is the greatest integer less than a or equal to a.     

Complexity and approximability of double digest

We revisit the DOUBLE DIGEST problem, which occurs in sequencing of large DNA strings and consists of reconstructing the relative positions of cut sites from two different enzymes. We first show that DOUBLE DIGEST is strongly NP-complete, improving upon previous results that only showed weak NP-completeness. Even the (experimentally more meaningful) variation in which we disallow coincident cut sites turns out to be strongly NP-complete. In the second part, we model errors in data as they occur in real-life experiments: we propose several optimization variations of DOUBLE DIGEST that model partial cleavage errors. We then show that most of these variations are hard to approximate. In the third part, we investigate variations with the additional restriction that coincident cut sites are disallowed, and we show that it is NP-hard to even find feasible solutions in this case, thus making it impossible to guarantee any approximation ratio at all.     

Interpreting woody cover data in tropical and subtropical areas: Comparison between the equilibrium and the non-equilibrium assumption

We compared two basic assumptions about the woody cover distribution in tropical and subtropical areas: the equilibrium (woody cover always reaches a long-term steady state) vs the non-equilibrium assumption (woody cover fluctuates in response to fire disturbances). We considered two models each one representative of one of the two assumptions: an equilibrium and a non-equilibrium model. The equilibrium model considered fire as an a priori determined parameter, whereas the non-equilibrium model assumed fires as stochastic events whose probability increased with grass density. We compared the results of the models with large datasets containing woody cover values sampled at the continental and at the global scale. In particular, we focused on two evidences shown by data. The first evidence is that woody cover is limited by water scarcity for low rainfall values and by fire for high rainfall values (arid–moist savanna distinction). The second evidence is the bimodality of woody cover data observed for high rainfall values. The equilibrium model gave a static interpretation of the data. The non-equilibrium model, instead, gave a more general interpretation of the data. In particular, the non-equilibrium model detected the arid–moist savanna distinction as emergent along a rainfall gradient and demonstrated that the bimodality observed in the woody cover data could be obtained in the woody cover values exhibited by a vegetation system in different times. Thus, woody cover data do not necessarily represent steady states. Rather, they could represent snapshots of a vegetation system in certain time instants.     

The continuity and discontinuity of the living cover: problem of the scale

The reply to B.M. Mirkin's critical remarks (2005) concerning my paper "Continuity and discontinuity of the geomerida: the bionomic and biotic aspects" (Kafanov, 2005a) is given. The relationship between continuity and discontinuity of the living cover depends on the scale of study. The continuum mainly belongs to regularities of topological order. At regional, subglobal and global scale, the continuum of biochores is rather rare. The objective evidences of relative discontinuity of the living cover are determined by significant alterations of taxonomic richness at regional, subglobal and global scale.     

A large‐area,spatially continuous assessment of land cover map error and its impact on downstream analyses

Land cover maps increasingly underlie research into socioeconomic and environmental patterns and processes, including global change. It is known that map errors impact our understanding of these phenomena, but quantifying these impacts is difficult because many areas lack adequate reference data. We used a highly accurate, high‐resolution map of South African cropland to assess (1) the magnitude of error in several current generation land cover maps, and (2) how these errors propagate in downstream studies. We first quantified pixel‐wise errors in the cropland classes of four widely used land cover maps at resolutions ranging from 1 to 100 km, and then calculated errors in several representative “downstream” (map‐based) analyses, including assessments of vegetative carbon stocks, evapotranspiration, crop production, and household food security. We also evaluated maps’ spatial accuracy based on how precisely they could be used to locate specific landscape features. We found that cropland maps can have substantial biases and poor accuracy at all resolutions (e.g., at 1 km resolution, up to ～45% underestimates of cropland (bias) and nearly 50% mean absolute error (MAE, describing accuracy); at 100 km, up to 15% underestimates and nearly 20% MAE). National‐scale maps derived from higher‐resolution imagery were most accurate, followed by multi‐map fusion products. Constraining mapped values to match survey statistics may be effective at minimizing bias (provided the statistics are accurate). Errors in downstream analyses could be substantially amplified or muted, depending on the values ascribed to cropland‐adjacent covers (e.g., with forest as adjacent cover, carbon map error was 200%–500% greater than in input cropland maps, but ～40% less for sparse cover types). The average locational error was 6 km (600%). These findings provide deeper insight into the causes and potential consequences of land cover map error, and suggest several recommendations for land cover map users.     

Computational complexity of a problem in molecular structure prediction.

The computational task of protein structure prediction is believed to require exponential time, but previous arguments as to its intractability have taken into account only the size of a protein's conformational space. Such arguments do not rule out the possible existence of an algorithm, more selective than exhaustive search, that is efficient and exact. (An efficient algorithm is one that is guaranteed, for all possible inputs, to run in time bounded by a function polynomial in the problem size. An intractable problem is one for which no efficient algorithm exists.) Questions regarding the possible intractability of problems are often best answered using the theory of NP-completeness. In this treatment we show the NP-hardness of two typical mathematical statements of empirical potential energy function minimization of macromolecules. Unless all NP-complete problems can be solved efficiently, these results imply that a function minimization algorithm can be efficient for protein structure prediction only if it exploits protein-specific properties that prohibit the simple geometric constructions that we use in our proofs. Analysis of further mathematical statements of molecular structure prediction could constitute a systematic methodology for identifying sources of complexity in protein folding, and for guiding development of predictive algorithms.     

Analysis of leaf appearance,leaf death and phoma leaf spot,caused by Leptosphaeria maculans,on oilseed rape (Brassica napus) cultivars

Development of phoma leaf spot (caused by Leptosphaeria maculans) on winter oilseed rape (canola, Brassica napus) was assessed in two experiments at Rothamsted in successive years (2003–04 and 2004–05 growing seasons). Both experiments compared oilseed rape cultivars Eurol, Darmor, Canberra and Lipton, which differ in their resistance to L. maculans. Data were analysed to describe disease development in terms of increasing numbers of leaves affected over thermal time from sowing. The cultivars showed similar patterns of leaf spot development in the 2003–04 experiment when inoculum concentration was relatively low (up to 133 ascospores m⁻³ air), Darmor developing 5.3 diseased leaves per plant by 5 May 2004, Canberra 6.6, Eurol 6.8 and Lipton 7.5. Inoculum concentration was up to sevenfold greater in 2004–05, with Eurol and Darmor developing 2.4 diseased leaves per plant by 16 February 2005, whereas Lipton and Canberra developed 2.8 and 3.0 diseased leaves, respectively. Based on three defined periods of crop development, a piece-wise linear statistical model was applied to the progress of the leaf spot disease (cumulative diseased leaves) in relation to appearance (‘birth’) and death of leaves for individual plants of each cultivar. Estimates of the thermal time from sowing until appearance of the first leaf or death of the first leaf, the rate of increase in number of diseased leaves and the area under the disease progress line (AUDPL) for the first time period were made. In 2004–05, Canberra (1025 leaves ×°C days) and Lipton (879) had greater AUDPL values than Eurol (427) and Darmor (598). For Darmor and Lipton, the severity of leaf spotting could be related to the severity of stem canker at harvest. Eurol had less leaf spotting but severe stem canker, whereas Canberra had more leaf spotting but less severe canker.     

The complexity of the gapped consecutive-ones property problem for matrices of bounded maximum degree

The Gapped Consecutive-Ones Property (C1P) Problem, or the (k, δ)-C1P Problem is: given a binary matrix M and integers k and δ, decide if the columns of M can be ordered such that each row contains at most k blocks of 1's, and no two neighboring blocks of 1's are separated by a gap of more than δ 0's. This problem was introduced by Chauve et al. ( 2009b ). The classical polynomial-time solvable C1P Problem is equivalent to the (1, 0)-C1P problem. It has been shown that, for every unbounded or bounded k ≥ 2 and unbounded or bounded δ ≥ 1, except when (k, δ) = (2, 1), the (k, δ)-C1P Problem is NP-complete (Maňuch et al., 2011 ; Goldberg et al., 1995 ). In this article, we study the Gapped C1P Problem with a third parameter d, namely the bound on the maximum number of 1's in any row of M, or the bound on the maximum degree of M. This is motivated by the reconstruction of ancestral genomes (Ma et al., 2006 ; Chauve and Tannier, 2008 ), where, in binary matrices obtained from the experiments of Chauve and Tannier ( 2008 ), we have observed that the majority of the rows have low degree, while each high degree row contains many rows of low degree. The (d, k, δ)-C1P Problem has been shown to be polynomial-time solvable when all three parameters are fixed (Chauve et al., 2009b ). Since fixing d also fixes k (k ≤ d), the only case left to consider is the case when δ is unbounded, or the (d, k, ∞)-C1P Problem. Here we show that for every d > k ≥ 2, the (d, k, ∞)-C1P Problem is NP-complete.     

Vaccination and the prevention problem

This paper seeks to critically review a traditional objection to preventive medicine (which I call here the 'prevention problem'). The prevention problem is a concern about the supposedly inequitable distribution of benefits and risks of harm resulting from preventive medicine's focus on population-based interventions. This objection is potentially applicable to preventive vaccination programmes and could be used to argue that such programmes are unethical. I explore the structure of the prevention problem by focusing upon two different types of vaccination (therapeutic vaccination and preventive vaccination). I argue that the 'prevention problem' cannot be fairly applied to the case of preventive vaccination because such programmes do not just focus upon benefits at the level of populations (as is claimed by the prevention problem). Most such preventive vaccination programmes explicitly seek to create and maintain herd protection. I argue that herd protection is an important public good which is a benefit shared by all individuals in the relevant population. This fact can then be used to block the 'prevention problem' argument in relation to preventive vaccination programmes. I conclude by suggesting that whilst the future development and use of therapeutic vaccines does raise some interesting ethical issues, any ethical objections to prophylactic vaccination on the basis of the 'prevention problem' will not be overcome through the substitution of therapeutic vaccines for preventive vaccines; indeed, the 'prevention problem' fails on its own terms in relation to preventive vaccination programmes.