The surface-based approach for DNA computation is unreliable for SAT

Previous research presented DNA computing on surfaces, which applied to each clause three operations:"mark","destroy", and "unmark", and demonstrated how to solve a four-variable four-clause instance of the 3-SAT. It was claimed that only the strands satisfying the problem remained on the surface at the end of the computation and the surface-based approach was capable of scaling up to larger 3-SAT problems. Accordingly, the identities of the strands were only determined in the"readout" step for the correct solutions to the problem without checking if the strands really satisfied the problem. Thus, based on the claim above, the surface-based approach became a polynomial-time algorithm. In this paper, we show that for some instance of SAT, at the end of the computation all the remaining strands falsify the instance. However, by the previous claim all the strands falsifying the problems would be regarded as the correct solutions to the problems. Therefore, the DNA computing on surfaces is unreliable. For this reason, it is necessary to add a "verify" step after the "readout" step to check if the strands remaining on the surface at the end of the computation really satisfy the problem.     

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.     

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))相似文献   

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 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 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 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.     

基于分子信标的DNA计算

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

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 family of diverse Cul4-Ddb1-interacting proteins includes Cdt2, which is required for S phase destruction of the replication factor Cdt1

Cul4 E3 ubiquitin ligases contain the cullin 4 scaffold and the triple beta propeller Ddb1 adaptor protein, but few substrate receptors have been identified. Here, we identify 18 Ddb1- and Cul4-associated factors (DCAFs), including 14 containing WD40 repeats. DCAFs interact with multiple surfaces on Ddb1, and the interaction of WD40-containing DCAFs with Ddb1 requires a conserved "WDXR" motif. DCAF2/Cdt2, which is related to S. pombe Cdt2, functions in Xenopus egg extracts and human cells to destroy the replication licensing protein Cdt1 in S phase and after DNA damage. Depletion of human Cdt2 causes rereplication and checkpoint activation. In Xenopus, Cdt2 is recruited to replication forks via Cdt1 and PCNA, where Cdt1 ubiquitylation occurs. These studies uncover diverse substrate receptors for Cul4 and identify Cdt2 as a conserved component of the Cul4-Ddb1 E3 that is essential to destroy Cdt1 and ensure proper cell cycle regulation of DNA replication.     

Sub-Golgi distribution in rat liver of CMP-NeuAc GM3- and CMP-NeuAc:GT1b alpha 2----8sialyltransferases and comparison with the distribution of the other glycosyltransferase activities involved in ganglioside biosynthesis

Using a sucrose density gradient fractionation of a highly purified Golgi apparatus from rat liver, we determined the sub-Golgi distribution of CMP-NeuAc:GM3 ganglioside alpha 2----8sialyltransferase (GM3-SAT) and CMP-NeuAc:GT1b ganglioside alpha 2----8sialyltransferase (GT1b-SAT), in comparison with that of the other glycosyltransferase activities involved in ganglioside biosynthesis. While GM3-SAT was recovered in several density fractions, GT1b-SAT was mainly found on less dense sub-Golgi membranes; this indicates that these two activities are physically separate. Moreover, with regard to the monosialo pathway, CMP-NeuAc:lactosylceramide alpha 2----3sialyltransferase, UDP-GalNAc:GM3 ganglioside beta 1----4N-acetylgalactosaminyltransferase, UDP-Gal:GM2 ganglioside beta 1----3galactosyltransferase, and CMP-NeuAc:GM1 ganglioside alpha 2----3sialyltransferase were resolved from more dense to less dense fractions, respectively. In the disialo pathway, UDP-GalNAc:GD3 ganglioside beta 1----4N-acetylgalactosaminyltransferase, UDP-Gal:GD2 ganglioside beta 1----3galactosyltransferase and CMP-NeuAc:GD1b ganglioside alpha 2----3sialyltransferase co-distributed with the corresponding activities of the monosialo pathway. These last results indicate that many Golgi glycosyltransferases involved in ganglioside biosynthesis are localized in the order in which they act.     

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.     

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.     

全错位排列问题的一种改进的表面DNA计算模型

文章提出全错位排列问题的一种改进的表面计算模型,通过巧妙的编码,不但继承了表面计算的诸多优点,而且摆脱了以往模型难以推广的不足.同时,设计中采用了荧光淬灭的有关技术,利用观察荧光淬灭来确定问题的非解,这种读解方法简单有效,算法是有效可行的.     

ClusPro FMFT-SAXS: Ultra-fast Filtering Using Small-Angle X-ray Scattering Data in Protein Docking

We have recently demonstrated that incorporation of small-angle X-ray scattering (SAXS)-based filtering in our heavily used docking server ClusPro improves docking results. However, the filtering step is time consuming, since ≈ 10⁵ conformations have to be sequentially processed. At the same time, we have demonstrated the possibility of ultra-fast systematic energy evaluation for all rigid body orientations of two proteins, by sampling using Fast Manifold Fourier Transform (FMFT), if energies are represented as a combination of convolution-like expressions. Here we present a novel FMFT-based algorithm FMFT-SAXS for massive SAXS computation on multiple conformations of a protein complex. This algorithm exploits the convolutional form of SAXS calculation function. FMFT-SAXS allows computation of SAXS profiles for millions of conformations in a matter of minutes, providing an opportunity to explore the whole conformational space of two interacting proteins. We demonstrate the application of the new FMFT-SAXS approach to significantly speed up SAXS filtering step in our current docking protocol (1 to 2 orders of magnitude faster, running in several minutes on a modern 16-core CPU) without loss of accuracy. This is demonstrated on the benchmark set as well as on the experimental data. The new approach is available as a part of ClusPro server (https://beta.cluspro.org) and as an open source C library (https://bitbucket.org/abc-group/libfmftsaxs).     

Solving the three dimensional quadratic assignment problem on a computational grid

The exact resolution of large instances of combinatorial optimization problems, such as three dimensional quadratic assignment problem (Q3AP), is a real challenge for grid computing. Indeed, it is necessary to reconsider the resolution algorithms and take into account the characteristics of such environments, especially large scale and dynamic availability of resources, and their multi-domain administration. In this paper, we revisit the design and implementation of the branch and bound algorithm for solving large combinatorial optimization problems such as Q3AP on the computational grids. Such gridification is based on new ways to efficiently deal with some crucial issues, mainly dynamic adaptive load balancing and fault tolerance. Our new approach allowed the exact resolution on a nation-wide grid of a difficult Q3AP instance. To solve this instance, an average of 1,123 computing cores were used for less than 12 days with a peak of around 3,427 computing cores.     

Ligation errors in DNA computing

DNA computing is a novel method of computing proposed by Adleman (1994), in which the data is encoded in the sequences of oligonucleotides. Massively parallel reactions between oligonucleotides are expected to make it possible to solve huge problems. In this study, reliability of the ligation process employed in the DNA computing is tested by estimating the error rate at which wrong oligonucleotides are ligated. Ligation of wrong oligonucleotides would result in a wrong answer in the DNA computing. The dependence of the error rate on the number of mismatches between oligonucleotides and on the combination of bases is investigated.