Fast parallel molecular solutions for DNA-based supercomputing: the subset-product problem

In this paper our main purpose is to give molecular solutions for the subset-product problem. In order to achieve this, we propose three DNA-based algorithms--parallel adder, parallel multiplier and parallel comparator--that formally verify our designed molecular solutions for the subset-product problem. We also show that Boolean circuits are not needed to perform mathematical operations on a molecular computer. Furthermore, this work indicates that the subset-product problem is solved and also presents clear evidence of the ability of molecular computing to perform complicated mathematical operations.     

A DNA-based in vitroGenetic Program

In PNA-mediated Whiplash PCR (PWPCR), autonomous molecular computation is implemented by the recursive polymerase extension of a mixture of DNA hairpins. Like other methods based on exhaustive search, however, application to problem instances of realistic size is prevented by the exponential scaling of thesolution space. The tendency of evolving populations to minimize the sampling of large, low fitness basins suggests that a DNA-based evolutionary approach might be an effective alternative to exhaustive search. In this work, PWPCR is modified to support the evolution of a population of finite state machines. A practical, in vitroalgorithm for applying this architecture to evolve approximate solutions to instances of the NP-complete problem, Hamiltonian Pathis described in detail.     

DNA algorithm for an unbounded fan-in Boolean circuit

In this paper, we present a new DNA-based evaluation algorithm for a Boolean circuit that employs standard bio-molecular techniques. The algorithm operates on an unbounded fan-in Boolean circuit consisting of AND and OR gates. The whole simulation of our algorithm is proposed in a single test tube in O(1) time complexity and is much easier to implement in the laboratory than previously described models. Furthermore, the algorithm allows for evaluating any number of Boolean circuits in parallel in a single test tube.     

A DNA-Based Semantic Fusion Model for Remote Sensing Data

Semantic technology plays a key role in various domains, from conversation understanding to algorithm analysis. As the most efficient semantic tool, ontology can represent, process and manage the widespread knowledge. Nowadays, many researchers use ontology to collect and organize data''s semantic information in order to maximize research productivity. In this paper, we firstly describe our work on the development of a remote sensing data ontology, with a primary focus on semantic fusion-driven research for big data. Our ontology is made up of 1,264 concepts and 2,030 semantic relationships. However, the growth of big data is straining the capacities of current semantic fusion and reasoning practices. Considering the massive parallelism of DNA strands, we propose a novel DNA-based semantic fusion model. In this model, a parallel strategy is developed to encode the semantic information in DNA for a large volume of remote sensing data. The semantic information is read in a parallel and bit-wise manner and an individual bit is converted to a base. By doing so, a considerable amount of conversion time can be saved, i.e., the cluster-based multi-processes program can reduce the conversion time from 81,536 seconds to 4,937 seconds for 4.34 GB source data files. Moreover, the size of result file recording DNA sequences is 54.51 GB for parallel C program compared with 57.89 GB for sequential Perl. This shows that our parallel method can also reduce the DNA synthesis cost. In addition, data types are encoded in our model, which is a basis for building type system in our future DNA computer. Finally, we describe theoretically an algorithm for DNA-based semantic fusion. This algorithm enables the process of integration of the knowledge from disparate remote sensing data sources into a consistent, accurate, and complete representation. This process depends solely on ligation reaction and screening operations instead of the ontology.     

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

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

Fish as predators and prey: DNA-based assessment of their role in food webs

Fish are both consumers and prey, and as such part of a dynamic trophic network. Measuring how they are trophically linked, both directly and indirectly, to other species is vital to comprehend the mechanisms driving alterations in fish communities in space and time. Moreover, this knowledge also helps to understand how fish communities respond to environmental change and delivers important information for implementing management of fish stocks. DNA-based methods have significantly widened our ability to assess trophic interactions in both marine and freshwater systems and they possess a range of advantages over other approaches in diet analysis. In this review we provide an overview of different DNA-based methods that have been used to assess trophic interactions of fish as consumers and prey. We consider the practicalities and limitations, and emphasize critical aspects when analysing molecular derived trophic data. We exemplify how molecular techniques have been employed to unravel food web interactions involving fish as consumers and prey. In addition to the exciting opportunities DNA-based approaches offer, we identify current challenges and future prospects for assessing fish food webs where DNA-based approaches will play an important role.     

Towards an efficient parallel raycasting of unstructured volumetric data on distributed environments

Direct volume rendering of large and unstructured datasets demands high computational power and memory bandwidth. Developing an efficient parallel algorithm requires a deep understanding of the bottlenecks involved in the solutions for this problem. In this work, we make a thorough analysis of the overhead components involved in parallel volume raycasting of unstructured grids for high-resolution images on distributed environments. This evaluation has revealed potential opportunities for performance improvements. The result is a novel approach to distributed memory raycasting that includes different acceleration techniques to enhance ray distribution, face projection, memory locality, and message exchanging, while maintaining load balance. We report the gains achieved in each phase and in the complete parallel algorithm when compared with a conventional approach.     

Coevolving solutions to the shortest common superstring problem

The shortest common superstring (SCS) problem, known to be NP-Complete, seeks the shortest string that contains all strings from a given set. In this paper we compare four approaches for finding solutions to the SCS problem: a standard genetic algorithm, a novel cooperative-coevolutionary algorithm, a benchmark greedy algorithm, and a parallel coevolutionary-greedy approach. We show the coevolutionary approach produces the best results, and discuss directions for future research.     

Optimising parallel R correlation matrix calculations on gene expression data using MapReduce

Background

High-throughput molecular profiling data has been used to improve clinical decision making by stratifying subjects based on their molecular profiles. Unsupervised clustering algorithms can be used for stratification purposes. However, the current speed of the clustering algorithms cannot meet the requirement of large-scale molecular data due to poor performance of the correlation matrix calculation. With high-throughput sequencing technologies promising to produce even larger datasets per subject, we expect the performance of the state-of-the-art statistical algorithms to be further impacted unless efforts towards optimisation are carried out. MapReduce is a widely used high performance parallel framework that can solve the problem.

Results

In this paper, we evaluate the current parallel modes for correlation calculation methods and introduce an efficient data distribution and parallel calculation algorithm based on MapReduce to optimise the correlation calculation. We studied the performance of our algorithm using two gene expression benchmarks. In the micro-benchmark, our implementation using MapReduce, based on the R package RHIPE, demonstrates a 3.26-5.83 fold increase compared to the default Snowfall and 1.56-1.64 fold increase compared to the basic RHIPE in the Euclidean, Pearson and Spearman correlations. Though vanilla R and the optimised Snowfall outperforms our optimised RHIPE in the micro-benchmark, they do not scale well with the macro-benchmark. In the macro-benchmark the optimised RHIPE performs 2.03-16.56 times faster than vanilla R. Benefiting from the 3.30-5.13 times faster data preparation, the optimised RHIPE performs 1.22-1.71 times faster than the optimised Snowfall. Both the optimised RHIPE and the optimised Snowfall successfully performs the Kendall correlation with TCGA dataset within 7 hours. Both of them conduct more than 30 times faster than the estimated vanilla R.

Conclusions

The performance evaluation found that the new MapReduce algorithm and its implementation in RHIPE outperforms vanilla R and the conventional parallel algorithms implemented in R Snowfall. We propose that MapReduce framework holds great promise for large molecular data analysis, in particular for high-dimensional genomic data such as that demonstrated in the performance evaluation described in this paper. We aim to use this new algorithm as a basis for optimising high-throughput molecular data correlation calculation for Big Data.     

State transitions by molecules

In our previous paper, we described a method by which a state machine is implemented by a single-stranded DNA molecule whose 3'-end sequence encodes the current state of the machine. Successive state transitions are performed in such a way that the current state is annealed onto an appropriate portion of DNA encoding the transition table of the state machine and the next state is copied to the 3'-end by extension with polymerase. In this paper, we first show that combined with parallel overlap assembly, a single series of successive transitions can solve NP-complete problems. This means that the number of necessary laboratory steps is independent from the problem size. We then report the results of two experiments concerning the implementation of our method. One is on isothermal reactions which greatly increase the efficiency of state transitions compared with reactions controlled by thermal cycles. The other is on the use of unnatural bases for avoiding out-of-frame annealing. The latter result can also be applied to many DNA-based computing paradigms.     

Multiplexed-Replica Exchange Molecular Dynamics Method for Protein Folding Simulation

Simulating protein folding thermodynamics starting purely from a protein sequence is a grand challenge of computational biology. Here, we present an algorithm to calculate a canonical distribution from molecular dynamics simulation of protein folding. This algorithm is based on the replica exchange method where the kinetic trapping problem is overcome by exchanging noninteracting replicas simulated at different temperatures. Our algorithm uses multiplexed-replicas with a number of independent molecular dynamics runs at each temperature. Exchanges of configurations between these multiplexed-replicas are also tried, rendering the algorithm applicable to large-scale distributed computing (i.e., highly heterogeneous parallel computers with processors having different computational power). We demonstrate the enhanced sampling of this algorithm by simulating the folding thermodynamics of a 23 amino acid miniprotein. We show that better convergence is achieved compared to constant temperature molecular dynamics simulation, with an efficient scaling to large number of computer processors. Indeed, this enhanced sampling results in (to our knowledge) the first example of a replica exchange algorithm that samples a folded structure starting from a completely unfolded state.     

Approaching mathematical model of the immune network based DNA Strand Displacement system

One biggest obstacle in molecular programming is that there is still no direct method to compile any existed mathematical model into biochemical reaction in order to solve a computational problem. In this paper, the implementation of DNA Strand Displacement system based on nature-inspired computation is observed. By using the Immune Network Theory and Chemical Reaction Network, the compilation of DNA-based operation is defined and the formulation of its mathematical model is derived. Furthermore, the implementation on this system is compared with the conventional implementation by using silicon-based programming. From the obtained results, we can see a positive correlation between both. One possible application from this DNA-based model is for a decision making scheme of intelligent computer or molecular robot.     

An annealed chaotic maximum neural network for bipartite subgraph problem

In this paper, based on maximum neural network, we propose a new parallel algorithm that can help the maximum neural network escape from local minima by including a transient chaotic neurodynamics for bipartite subgraph problem. The goal of the bipartite subgraph problem, which is an NP- complete problem, is to remove the minimum number of edges in a given graph such that the remaining graph is a bipartite graph. Lee et al. presented a parallel algorithm using the maximum neural model (winner-take-all neuron model) for this NP- complete problem. The maximum neural model always guarantees a valid solution and greatly reduces the search space without a burden on the parameter-tuning. However, the model has a tendency to converge to a local minimum easily because it is based on the steepest descent method. By adding a negative self-feedback to the maximum neural network, we proposed a new parallel algorithm that introduces richer and more flexible chaotic dynamics and can prevent the network from getting stuck at local minima. After the chaotic dynamics vanishes, the proposed algorithm is then fundamentally reined by the gradient descent dynamics and usually converges to a stable equilibrium point. The proposed algorithm has the advantages of both the maximum neural network and the chaotic neurodynamics. A large number of instances have been simulated to verify the proposed algorithm. The simulation results show that our algorithm finds the optimum or near-optimum solution for the bipartite subgraph problem superior to that of the best existing parallel algorithms.     

UpGene: Application of a web-based DNA codon optimization algorithm

Although DNA codon optimization is a standard molecular biology strategy to overcome poor gene expression, to date no public software exists to facilitate this process. Among the uses of codon optimization, human immunodeficiency virus (HIV) vaccine development represents one of the most difficult challenges. A key obstacle to an effective DNA-based vaccine is the low-level expression of HIV genes in mammalian cells, which is due primarily to the instability of HIV mRNAs resulting from AU-rich elements and rare codon usage. In this report we describe the development of a DNA optimization algorithm integrated with a PCR primer design program to redesign specific coding sequences for maximal gene expression. Using this algorithm combination, together with PCR-based gene assembly, we have successfully optimized gene sequences for simian immunodeficiency virus (SIV) strain mac239 structural antigenic proteins gag and env, resulting in high-level gene expression in eukaryotic cells. Our findings demonstrate that our user-friendly algorithm is a valuable tool for DNA-based HIV vaccine development. Moreover, it can be used to optimize any other genes of interest and is freely available online at http://www.vectorcore.pitt.edu/upgene.html.     

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.     

A parallel algorithm for estimating the secondary structure in ribonucleic acids

A parallel algorithm for estimating the secondary structure of an RNA molecule is presented in this paper. The mathematical problem to compute an optimal folding based on free-energy minimization is mapped onto a graph planarization problem. In the planarization problem we want to maximize the number of edges in a plane with no two edges crossing each other. To solve a sequence of n bases, n(n — 1)/2 processing elements are used in our algorithm.     

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.     

Parallel Clustering Algorithm for Large Data Sets with Applications in Bioinformatics

Large sets of bioinformatical data provide a challenge in time consumption while solving the cluster identification problem, and that is why a parallel algorithm is so needed for identifying dense clusters in a noisy background. Our algorithm works on a graph representation of the data set to be analyzed. It identifies clusters through the identification of densely intraconnected subgraphs. We have employed a minimum spanning tree (MST) representation of the graph and solve the cluster identification problem using this representation. The computational bottleneck of our algorithm is the construction of an MST of a graph, for which a parallel algorithm is employed. Our high-level strategy for the parallel MST construction algorithm is to first partition the graph, then construct MSTs for the partitioned subgraphs and auxiliary bipartite graphs based on the subgraphs, and finally merge these MSTs to derive an MST of the original graph. The computational results indicate that when running on 150 CPUs, our algorithm can solve a cluster identification problem on a data set with 1,000,000 data points almost 100 times faster than on single CPU, indicating that this program is capable of handling very large data clustering problems in an efficient manner. We have implemented the clustering algorithm as the software CLUMP.     

Structural rigidity of paranemic crossover and juxtapose DNA nanostructures

Crossover motifs are integral components for designing DNA-based nanostructures and nanomechanical devices due to their enhanced rigidity compared to the normal B-DNA. Although the structural rigidity of the double helix B-DNA has been investigated extensively using both experimental and theoretical tools, to date there is no quantitative information about structural rigidity and the mechanical strength of parallel crossover DNA motifs. We have used fully atomistic molecular dynamics simulations in explicit solvent to get the force-extension curve of parallel DNA nanostructures to characterize their mechanical rigidity. In the presence of monovalent Na⁺ ions, we find that the stretch modulus (γ₁) of the paranemic crossover and its topoisomer JX DNA structure is significantly higher (∼30%) compared to normal B-DNA of the same sequence and length. However, this is in contrast to the original expectation that these motifs are almost twice as rigid compared to the double-stranded B-DNA. When the DNA motif is surrounded by a solvent with Mg²⁺ counterions, we find an enhanced rigidity compared to Na⁺ environment due to the electrostatic screening effects arising from the divalent nature of Mg²⁺ ions. To our knowledge, this is the first direct determination of the mechanical strength of these crossover motifs, which can be useful for the design of suitable DNA for DNA-based nanostructures and nanomechanical devices with improved structural rigidity.     

Parallelization of a local similarity algorithm

The local similarity problem is to determine the similar regionswithin two given sequences. We recently developed a dynamicprogramming algorithm for the local similarity problem thatrequires only space proportional to the sum of the two sequencelengths, whereas earlier methods use space proportional to theproduct of the lengths. In this paper, we describe how to parallelizethe new algorithm and present results of experimental studieson an Intel hypercube. The parallel method provides rapid, high-resolutionalignments for users of our software toolkit for pairwise sequencecomparison, as illustrated here by a comparison of the chloroplastgenomes of tobacco and liverwort.