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

Development of Synthetic DNA Circuit and Networks for Molecular Information Processing

Deoxyribonucleic acid (DNA), a genetic material, encodes all living information and living characteristics, e.g., in cell, DNA signaling circuits control the transcription activities of specific genes. In recent years, various DNA circuits have been developed to implement a wide range of signaling and for regulating gene network functions. In particular, a synthetic DNA circuit, with a programmable design and easy construction, has become a crucial method through which to simulate and regulate DNA signaling networks. Importantly, the construction of a hierarchical DNA circuit provides a useful tool for regulating gene networks and for processing molecular information. Moreover, via their robust and modular properties, DNA circuits can amplify weak signals and establish programmable cascade systems, which are particularly suitable for the applications of biosensing and detecting. Furthermore, a biological enzyme can also be used to provide diverse circuit regulation elements. Currently, studies regarding the mechanisms and applications of synthetic DNA circuit are important for the establishment of more advanced artificial gene regulation systems and intelligent molecular sensing tools. We therefore summarize recent relevant research progress, contributing to the development of nanotechnology-based synthetic DNA circuits. By summarizing the current highlights and the development of synthetic DNA circuits, this paper provides additional insights for future DNA circuit development and provides a foundation for the construction of more advanced DNA circuits.

Solving the Family Traveling Salesperson Problem in the Adleman-Lipton model based on DNA computing

The Family Traveling Salesperson Problem (FTSP) is a variant of the Traveling Salesperson Problem (TSP), in which all vertices are divided into several different families, and the goal of the problem is to find a loop that concatenates a specified number of vertices with minimal loop overhead. As a Non-deterministic Polynomial Complete (NP-complete) problem, it is difficult to deal with it by the traditional computing. On the contrary, as a computer with strong parallel ability, the DNA computer has incomparable advantages over digital computers when dealing with NP problems. Based on this, a DNA algorithm is proposed to deal with FTSP based on the Adleman-Lipton model. In the algorithm, the solution of the problem can be obtained by executing several basic biological manipulations on DNA molecules with O(N2) computing complexity (N is the number of vertices in the problem without the origin). Through the simulation experiments on some benchmark instances, the results show that the parallel DNA algorithm has better performance than traditional computing. The effectiveness of the algorithm is verified by deducing the algorithm process in detail. Furthermore, the algorithm further proves that DNA computing, as one of the parallel computing methods, has the potential to solve more complex big data problems.

A novel bio-heuristic computing algorithm to solve the capacitated vehicle routing problem based on Adleman-Lipton model

DNA computing, as one of potential means to solve complicated computational problems, is a new field of interdisciplinary research, including computational mathematics, parallel algorithms, bioinformatics. Capacitated vehicle routing problem is one of famous NP-hard problems, which includes determining the path of a group same vehicles serving a set of clients, while minimizing the total transportation cost. Based on the bio-heuristic computing model and DNA molecular manipulations, parallel biocomputing algorithms for solving capacitated vehicle routing problem are proposed in this paper. We appropriately use different biological chains to mean vertices, edges, weights, and adopt appropriate biological operations to search the solutions of the problem with O(n²) time complexity. We enrich the application scope of biocomputing, reduce computational complexity, and verify practicability of DNA parallel algorithms through simulations.

A new parallel DNA algorithm to solve the task scheduling problem based on inspired computational model

As a promising approach to solve the computationally intractable problem, the method based on DNA computing is an emerging research area including mathematics, computer science and molecular biology. The task scheduling problem, as a well-known NP-complete problem, arranges n jobs to m individuals and finds the minimum execution time of last finished individual. In this paper, we use a biologically inspired computational model and describe a new parallel algorithm to solve the task scheduling problem by basic DNA molecular operations. In turn, we skillfully design flexible length DNA strands to represent elements of the allocation matrix, take appropriate biological experiment operations and get solutions of the task scheduling problem in proper length range with less than O(n²) time complexity.

A parallel algorithm for solving the n-queens problem based on inspired computational model

DNA computing provides a promising method to solve the computationally intractable problems. The n-queens problem is a well-known NP-hard problem, which arranges n queens on an n × n board in different rows, columns and diagonals in order to avoid queens attack each other. In this paper, we present a novel parallel DNA algorithm for solving the n-queens problem using DNA molecular operations based on a biologically inspired computational model. For the n-queens problem, we reasonably design flexible length DNA strands representing elements of the allocation matrix, take appropriate biologic manipulations and get the solutions of the n-queens problem in proper length and O(n(2)) time complexity. We extend the application of DNA molecular operations, simultaneity simplify the complexity of the computation and simulate to verify the feasibility of the DNA algorithm.

DNA based computing for understanding complex shapes

This study deals with a computing method called DNA based computing (DBC) that takes inspiration from the Central Dogma of Molecular Biology. The proposed DBC uses a set of user-defined rules to create a DNA-like sequence from a given piece of problem-relevant information (e.g., image data) in a dry-media (i.e., in an ordinary computer). It then uses another set of user-defined rules to create an mRNA-like sequence from the DNA. Finally, it uses the genetic code to translate the mRNA (or directly the DNA) to a protein-like sequence (a sequence of amino acids). The informational characteristics of the protein (entropy, absence, presence, abundance of some selected amino acids, and relationships among their likelihoods) can be used to solve problems (e.g., to understand complex shapes from their image data). Two case studies ((1) fractal geometry generated shape of a fern-leaf and (2) machining experiment generated shape of the worn-zones of a cutting tool) are presented elucidating the shape understanding ability of the proposed DBC in the presence of a great deal of variability in the image data of the respective shapes. The implication of the proposed DBC from the context of Internet-aided manufacturing system is also described. Further study can be carried out in solving other complex computational problems by using the proposed DBC and its derivatives.

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.

A SEMI-GENERAL METHOD TO SOLVE THE COMBINATORIAL OPTIMIZATION PROBLEMS BASED ON NANOCOMPUTING

Nanocomputing describes computing that uses nanoscale devices. It is reasonable to search for nanoscale particles, such as molecules, that do not require difficult fabrication steps. DNA is recognized as a nanomaterial, not as a biological material, in the research field of nanotechnology. This paper proposes a semi-general method to solve combinatorial optimization problems based on DNA computing. It is obvious that the DNA molecule is one of the most promising functional nanomaterials. However, the application of DNA molecules is still under study because of the big gap that exists between theory and practice.

An evolutionary Monte Carlo algorithm for predicting DNA hybridization

Many DNA-based technologies, such as DNA computing, DNA nanoassembly and DNA biochips, rely on DNA hybridization reactions. Previous hybridization models have focused on macroscopic reactions between two DNA strands at the sequence level. Here, we propose a novel population-based Monte Carlo algorithm that simulates a microscopic model of reacting DNA molecules. The algorithm uses two essential thermodynamic quantities of DNA molecules: the binding energy of bound DNA strands and the entropy of unbound strands. Using this evolutionary Monte Carlo method, we obtain a minimum free energy configuration in the equilibrium state. We applied this method to a logical reasoning problem and compared the simulation results with the experimental results of the wet-lab DNA experiments performed subsequently. Our simulation predicted the experimental results quantitatively.

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

Solving maximum cut problems in the Adleman-Lipton model

In this paper, we consider a procedure for solving maximum cut problems in the Adleman-Lipton model. The procedure works in O(n2) steps for maximum cut problems of an undirected graph with n vertices.