Hypergraph-Based Numerical Spiking Neural Membrane Systems with Novel Repartition Protocols.

The classic spiking neural P (SN P) systems abstract the real biological neural network into a simple structure based on graphs, where neurons can only communicate on the plane. This study proposes the hypergraph-based numerical spiking neural membrane (HNSNM) systems with novel repartition protocols. Through the introduction of hypergraphs, the HNSNM systems can characterize the high-order relationships among neurons and extend the traditional neuron structure to high-dimensional nonlinear spaces. The HNSNM systems also abstract two biological mechanisms of synapse creation and pruning, and use plasticity rules with repartition protocols to achieve planar, hierarchical and spatial communications among neurons in hypergraph neuron structures. Through imitating register machines, the Turing universality of the HNSNM systems is proved by using them as number generating and accepting devices. A universal HNSNM system consisting of 41 neurons is constructed to compute arbitrary functions. By solving NP-complete problems using the subset sum problem as an example, the computational efficiency and effectiveness of HNSNM systems are verified.

Global exact optimisations for chloroplast structural haplotype scaffolding.

BACKGROUND: Scaffolding is an intermediate stage of fragment assembly. It consists in orienting and ordering the contigs obtained by the assembly of the sequencing reads. In the general case, the problem has been largely studied with the use of distances data between the contigs. Here we focus on a dedicated scaffolding for the chloroplast genomes. As these genomes are small, circular and with few specific repeats, numerous approaches have been proposed to assemble them. However, their specificities have not been sufficiently exploited. RESULTS: We give a new formulation for the scaffolding in the case of chloroplast genomes as a discrete optimisation problem, that we prove the decision version to be [Formula: see text]-Complete. We take advantage of the knowledge of chloroplast genomes and succeed in expressing the relationships between a few specific genomic repeats in mathematical constraints. Our approach is independent of the distances and adopts a genomic regions view, with the priority on scaffolding the repeats first. In this way, we encode the structural haplotype issue in order to retrieve several genome forms that coexist in the same chloroplast cell. To solve exactly the optimisation problem, we develop an integer linear program that we implement in Python3 package khloraascaf. We test it on synthetic data to investigate its performance behaviour and its robustness against several chosen difficulties. CONCLUSIONS: We succeed to model biological knowledge on genomic structures to scaffold chloroplast genomes. Our results suggest that modelling genomic regions is sufficient for scaffolding repeats and is suitable for finding several solutions corresponding to several genome forms.

Networks of polarized splicing processors as problem solvers.

In this paper we show how Networks of Polarized Splicing Processors (NPSPs) can be used as problem solvers. We give a detailed uniform solution for the 3-coloring problem using O(m*n) time and we briefly discuss a solution for the 3-SAT problem in O(n*m) time. We also give the complete algorithm that can solve the n-queens completion problem in O(n*(n-m)) time, hence the n-queens problem in O(n2) time. All of the solutions use NPSPs with 2 nodes.

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(n2) time complexity.

A Parallel Biological Optimization Algorithm to Solve the Unbalanced Assignment Problem Based on DNA Molecular Computing.

The unbalanced assignment problem (UAP) is to optimally resolve the problem of assigning n jobs to m individuals (m < n), such that minimum cost or maximum profit obtained. It is a vitally important Non-deterministic Polynomial (NP) complete problem in operation management and applied mathematics, having numerous real life applications. In this paper, we present a new parallel DNA algorithm for solving the unbalanced assignment problem using DNA molecular operations. We reasonably design flexible-length DNA strands representing different jobs and individuals, take appropriate steps, and get the solutions of the UAP in the proper length range and O(mn) time. We extend the application of DNA molecular operations and simultaneity to simplify the complexity of the computation.

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.

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.

Progress in DNA Computer / 生物化学与生物物理进展

DNA computer is a new research field which combines bot h the computer science and molecular biology. DNA computer is proposed to solve a class of hard problems of mathematical complexity by using a set of DNA sequen ces encoding all candidate solutions to the computational problem of interest an d find out the correct answers by serial manipulations of biochemical reactions. DNA computer is exactly a biomolecular computer which stores a vast quantity of information with high density. DNA computer, by means of its huge parallel comp utation and brute force search strategy, can solve the NP complete problems with polynomial time. The recent advances and principle of DNA computer are introduc ed. The future development and the bioinformatical significance of DNA computer are also analyzed and discussed.