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.     

An improved surface-based method for DNA computation

DNA computing is a novel method for solving a class of intractable computational problems, in which the computing time can grow exponentially with problem size. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability, among which a surface-based method is an efficient candidate. In this paper, the surface-based approach proposed by Liu, Q., Wang, L., Frutos, A.G., Condon, A.E., Corn, R.M., and Smith, L.M., 2000, DNA computing on surfaces. Nature 403, 175-179 is analyzed and an improved surface-based method for DNA computation (i.e. the hybrid DNA/optical computing method) is proposed. Compared with Liu et al.'s approach, our method has some significant advantages such as low cost, short operating time, reusable surface and simple experimental steps. Moreover, the concept of combining easily patterned DNA computing steps with equally parallel, but generally uniform and not easily patterned optical computing steps is an important new direction.     

A DNA computing readout operation based on structure-specific cleavage.

We describe a structure-specific cleavage-based READOUT strategy for surface-based DNA computing. The strategy was demonstrated in the solution of a 4-variable/3-satisfiability (SAT) problem. The READOUT step identifies the DNA molecules present at the end of the computational process. The specificity of the sequence detection used here derives from the sequence specificity of DNA hybridization coupled with the structure specificity of the enzymatic cleavage. The process is linear, yielding a higher uniformity of detection of the DNA computing products compared to that obtained with PCR amplification. The structure-specific cleavage-based readout is simple, accurate, and compatible with multiple-word DNA computing.     

Solving the SAT problem using a DNA computing algorithm based on ligase chain reaction

A new DNA computing algorithm based on a ligase chain reaction is demonstrated to solve an SAT problem. The proposed DNA algorithm can solve an n-variable m-clause SAT problem in m steps and the computation time required is O (3m+n). Instead of generating the full-solution DNA library, we start with an empty test tube and then generate solutions that partially satisfy the SAT formula. These partial solutions are then extended step by step by the ligation of new variables using Taq DNA ligase. Correct strands are amplified and false strands are pruned by a ligase chain reaction (LCR) as soon as they fail to satisfy the conditions. If we score and sort the clauses, we can use this algorithm to markedly reduce the number of DNA strands required throughout the computing process. In a computer simulation, the maximum number of DNA strands required was 2(0.48n) when n=50, and the exponent ratio varied inversely with the number of variables n and the clause/variable ratio m/n. This algorithm is highly space-efficient and error-tolerant compared to conventional brute-force searching, and thus can be scaled-up to solve large and hard SAT problems.     

Length bounded molecular computing

The length of DNA strands is an important resource in DNA computing. We show how to decrease strand lengths in known molecular algorithms for some NP-complete problems, such as like 3-SAT and Independent Set, without substantially increasing their running time or volume.     

Solving traveling salesman problems with DNA molecules encoding numerical values

We introduce a DNA encoding method to represent numerical values and a biased molecular algorithm based on the thermodynamic properties of DNA. DNA strands are designed to encode real values by variation of their melting temperatures. The thermodynamic properties of DNA are used for effective local search of optimal solutions using biochemical techniques, such as denaturation temperature gradient polymerase chain reaction and temperature gradient gel electrophoresis. The proposed method was successfully applied to the traveling salesman problem, an instance of optimization problems on weighted graphs. This work extends the capability of DNA computing to solving numerical optimization problems, which is contrasted with other DNA computing methods focusing on logical problem solving.     

DNA computing using single-molecule hybridization detection

DNA computing aims at using nucleic acids for computing. Since micromolar DNA solutions can act as billions of parallel nanoprocessors, DNA computers can in theory solve optimization problems that require vast search spaces. However, the actual parallelism currently being achieved is at least a hundred million-fold lower than the number of DNA molecules used. This is due to the quantity of DNA molecules of one species that is required to produce a detectable output to the computations. In order to miniaturize the computation and considerably reduce the amount of DNA needed, we have combined DNA computing with single-molecule detection. Reliable hybridization detection was achieved at the level of single DNA molecules with fluorescence cross-correlation spectroscopy. To illustrate the use of this approach, we implemented a DNA-based computation and solved a 4-variable 4-clause instance of the computationally hard Satisfiability (SAT) problem.     

Solving satisfiability problems using a novel microarray-based DNA computer

An algorithm based on a modified sticker model accompanied with an advanced MEMS-based microarray technology is demonstrated to solve SAT problem, which has long served as a benchmark in DNA computing. Unlike conventional DNA computing algorithms needing an initial data pool to cover correct and incorrect answers and further executing a series of separation procedures to destroy the unwanted ones, we built solutions in parts to satisfy one clause in one step, and eventually solve the entire Boolean formula through steps. No time-consuming sample preparation procedures and delicate sample applying equipment were required for the computing process. Moreover, experimental results show the bound DNA sequences can sustain the chemical solutions during computing processes such that the proposed method shall be useful in dealing with large-scale problems.     

Chess games: a model for RNA based computation

Here we develop the theory of RNA computing and a method for solving the 'knight problem' as an instance of a satisfiability (SAT) problem. Using only biological molecules and enzymes as tools, we developed an algorithm for solving the knight problem (3 x 3 chess board) using a 10-bit combinatorial pool and sequential RNase H digestions. The results of preliminary experiments presented here reveal that the protocol recovers far more correct solutions than expected at random, but the persistence of errors still presents the greatest challenge.     

Computing with DNA by operating on plasmids

A new method of computing using DNA plasmids is introduced and the potential advantages are listed. The new method is illustrated by reporting a laboratory computation of an instance of the NP-complete algorithmic problem of computing the cardinal number of a maximal independent subset of the vertex set of a graph. A circular DNA plasmid, specifically designed for this method of molecular computing, was constructed. This computational plasmid contains a specially inserted series of DNA sequence segments, each of which is bordered by a characteristic pair of restriction enzyme sites. For the computation reported here, the DNA sequence segments of this series were used to represent the vertices of the graph being investigated. By applying a scheme of enzymatic treatments to the computational plasmids, modified plasmids were generated from which the solution of the computational problem was selected. This new method of computing is applicable to a wide variety of algorithmic problems. Further computations in this style are in progress.     

DNA computation model to solve 0-1 programming problem

0-1 programming problem is an important problem in opsearch with very widespread applications. In this paper, a new DNA computation model utilizing solution-based and surface-based methods is presented to solve the 0-1 programming problem. This model contains the major benefits of both solution-based and surface-based methods; including vast parallelism, extraordinary information density and ease of operation. The result, verified by biological experimentation, revealed the potential of DNA computation in solving complex programming problem.     

基于分子信标的DNA计算

DNA计算是解决一类难以计算问题的一种新方法,这种计算随着问题的增大可以呈指数增长．迄今为止,许多研究成果已经成功地提高了它的性能和增加了它的可行性,本文在基于表面的DNA计算中采用了分子信标编码策略,并对分子信标在与对应的补链杂交形成双链时的受力进行分析,给出3-SAT问题的另一种解法．这种方法比现有的方法更有效,更具发展前景．因为它具有编码简单;耗材底;操作时间短;技术先进等优点．本文尝试了分子生物学,光学和力学的结合．这一工作为DNA计算能解决NP一完全问题提供了更有力的依据．     

The Shortlist Method for Fast Computation of the Earth Mover's Distance and Finding Optimal Solutions to Transportation Problems

Finding solutions to the classical transportation problem is of great importance, since this optimization problem arises in many engineering and computer science applications. Especially the Earth Mover''s Distance is used in a plethora of applications ranging from content-based image retrieval, shape matching, fingerprint recognition, object tracking and phishing web page detection to computing color differences in linguistics and biology. Our starting point is the well-known revised simplex algorithm, which iteratively improves a feasible solution to optimality. The Shortlist Method that we propose substantially reduces the number of candidates inspected for improving the solution, while at the same time balancing the number of pivots required. Tests on simulated benchmarks demonstrate a considerable reduction in computation time for the new method as compared to the usual revised simplex algorithm implemented with state-of-the-art initialization and pivot strategies. As a consequence, the Shortlist Method facilitates the computation of large scale transportation problems in viable time. In addition we describe a novel method for finding an initial feasible solution which we coin Modified Russell''s Method.     

Phylo: a citizen science approach for improving multiple sequence alignment

Background

Comparative genomics, or the study of the relationships of genome structure and function across different species, offers a powerful tool for studying evolution, annotating genomes, and understanding the causes of various genetic disorders. However, aligning multiple sequences of DNA, an essential intermediate step for most types of analyses, is a difficult computational task. In parallel, citizen science, an approach that takes advantage of the fact that the human brain is exquisitely tuned to solving specific types of problems, is becoming increasingly popular. There, instances of hard computational problems are dispatched to a crowd of non-expert human game players and solutions are sent back to a central server.

Methodology/Principal Findings

We introduce Phylo, a human-based computing framework applying “crowd sourcing” techniques to solve the Multiple Sequence Alignment (MSA) problem. The key idea of Phylo is to convert the MSA problem into a casual game that can be played by ordinary web users with a minimal prior knowledge of the biological context. We applied this strategy to improve the alignment of the promoters of disease-related genes from up to 44 vertebrate species. Since the launch in November 2010, we received more than 350,000 solutions submitted from more than 12,000 registered users. Our results show that solutions submitted contributed to improving the accuracy of up to 70% of the alignment blocks considered.

Conclusions/Significance

We demonstrate that, combined with classical algorithms, crowd computing techniques can be successfully used to help improving the accuracy of MSA. More importantly, we show that an NP-hard computational problem can be embedded in casual game that can be easily played by people without significant scientific training. This suggests that citizen science approaches can be used to exploit the billions of “human-brain peta-flops” of computation that are spent every day playing games. Phylo is available at: http://phylo.cs.mcgill.ca.     

Strategies for optimizing DNA hybridization on surfaces

Specific and predictable hybridization of the polynucleotide sequences to their complementary counterparts plays a fundamental role in the rational design of new nucleic acid nanodevices. Generally, nucleic acid hybridization can be performed using two major strategies, namely hybridization of DNA or RNA targets to surface-tethered oligonucleotide probes (solid-phase hybridization) and hybridization of the target nucleic acids to randomly distributed probes in solution (solution-phase hybridization). Investigations into thermodynamic and kinetic parameters of these two strategies showed that hybridization on surfaces is less favorable than that of the same sequence in solution. Indeed, the efficiency of DNA hybridization on surfaces suffers from three constraints: (1) electrostatic repulsion between DNA strands on the surface, (2) steric hindrance between tethered DNA probes, and (3) nonspecific adsorption of the attached oligonucleotides to the solid surface. During recent years, several strategies have been developed to overcome the problems associated with DNA hybridization on surfaces. Optimizing the probe surface density, application of a linker between the solid surface and the DNA-recognizing sequence, optimizing the pH of DNA hybridization solutions, application of thiol reagents, and incorporation of a polyadenine block into the terminal end of the recognizing sequence are among the most important strategies for enhancing DNA hybridization on surfaces.     

多维背包问题的DNA计算

提出了一种基于DNA计算的求解多维背包问题的算法,该算法分两个阶段执行,第一个阶段采用试管方法,分别求出满足各个约束方程的可行域;第二个阶段采用表面方法,对第一个阶段求出的多个可行域取交集,即得满足整个约束方程组的可行域,再比较该可行域中各可行解对应的目标函数值,进而得到最优解。并通过实例分析验证了该算法的有效性和正确性,该算法将试管方法和表面方法结合使用,充分利用了两种方法各自的优点。     

The study of tool use as the way for general estimation of cognitive abilities in animals

Investigation of tool use is an effective way to determine cognitive abilities of animals. This approach raises hypotheses, which delineate limits of animal's competence in understanding of objects properties and interrelations and the influence of individual and social experience on their behaviour. On the basis of brief review of different models of manipulation with objects and tools manufacturing (detaching, subtracting and reshaping) by various animals (from elephants to ants) in natural conditions the experimental data concerning tool usage was considered. Tool behaviour of anumals could be observed rarely and its distribution among different taxons is rather odd. Recent studies have revealed that some species (for instance, bonobos and tamarins) which didn't manipulate tools in wild life appears to be an advanced tool users and even manufacturers in laboratory. Experimental studies of animals tool use include investigation of their ability to use objects physical properties, to categorize objects involved in tool activity by its functional properties, to take forces affecting objects into account, as well as their capacity of planning their actions. The crucial question is whether animals can abstract general principles of relations between objects regardless of the exact circumstances, or they develop specific associations between concerete things and situations. Effectiveness of laboratory methods is estimated in the review basing on comparative studies of tool behaviour, such as "support problem", "stick problem", "tube- and tube-trap problem", and "reserve tube problem". Levels of social learning, the role of imprinting, and species-specific predisposition to formation of specific domains are discussed. Experimental investigation of tool use allows estimation of the individuals' intelligence in populations. A hypothesis suggesting that strong predisposition to formation of specific associations can serve as a driving force and at the same time as obstacle to animals' activity is discussed. In several "technically gifted" species (such as woodpecker finches, New Caledonian crows, and chimpanzees) tool use seems to be guided by a rapid process of trial and error learning. Individuals that are predisposed to learn specific connections do this too quickly and thus become enslaved by stereotypic solutions of raising problems.     

The simultaneous recurrent neural network for addressing the scaling problem in static optimization.

A trainable recurrent neural network, Simultaneous Recurrent Neural network, is proposed to address the scaling problem faced by neural network algorithms in static optimization. The proposed algorithm derives its computational power to address the scaling problem through its ability to "learn" compared to existing recurrent neural algorithms, which are not trainable. Recurrent backpropagation algorithm is employed to train the recurrent, relaxation-based neural network in order to associate fixed points of the network dynamics with locally optimal solutions of the static optimization problems. Performance of the algorithm is tested on the NP-hard Traveling Salesman Problem in the range of 100 to 600 cities. Simulation results indicate that the proposed algorithm is able to consistently locate high-quality solutions for all problem sizes tested. In other words, the proposed algorithm scales demonstrably well with the problem size with respect to quality of solutions and at the expense of increased computational cost for large problem sizes.     

Towards effective science cloud provisioning for a large-scale high-throughput computing

The science cloud paradigm has been actively developed and investigated, but still requires a suitable model for science cloud system in order to support increasing scientific computation needs with high performance. This paper presents an effective provisioning model of science cloud, particularly for large-scale high throughput computing applications. In this model, we utilize job traces where a statistical method is applied to pick the most influential features to improve application performance. With these features, a system determines where VM is deployed (allocation) and which instance type is proper (provisioning). An adaptive evaluation step which is subsequent to the job execution enables our model to adapt to dynamical computing environments. We show performance achievements by comparing the proposed model with other policies through experiments and expect noticeable improvements on performance as well as reduction of cost from resource consumption through our model.