A new fast algorithm for solving the minimum spanning tree problem based on DNA molecules computation

Exploring the Potential of DNA Computing for Complex Big Data Problems: A Case Study on the Traveling Car Renter Problem

The traveling car renter problem (TCRP) is a variant of the Traveling Salesman Problem (TSP) wherein the salesman utilizes rented cars for travel. The primary objective of this problem is to identify a solution that minimizes the cumulative operating costs. Given its classification as a non-deterministic polynomial (NP) problem, traditional computers are not proficient in effectively resolving it. Conversely, DNA computing exhibits unparalleled advantages when confronted with NP-hard problems. This paper presents a DNA algorithm, based on the Adleman-Lipton model, as a proposed approach to address TCRP. The solution for TCRP can be acquired by following a series of fundamental steps, including coding, interaction, and extraction. The time computing complexity of the proposed DNA algorithm is O(n2m) for TCRP with n cities and m types of cars. By conducting simulation experiments, the solutions for certain instances of TCRP are computed and compared to those obtained by alternative algorithms. The proposed algorithm further illustrates the potential of DNA computing, as a form of parallel computing, to address more intricate large-scale problems.

Automatic segmentation of layers in chorio-retinal complex using Graph-based method for ultra-speed 1.7 MHz wide field swept source FDML optical coherence tomography

The posterior segment of the human eye complex contains two discrete microstructure and vasculature network systems, namely, the retina and choroid. We present a single segmentation framework technique for segmenting the entire layers present in the chorio-retinal complex of the human eye using optical coherence tomography (OCT) images. This automatic program is based on the graph theory method. This single program is capable of segmenting seven layers of the retina and choroid scleral interface. The graph theory was utilized to find the probability matrix and subsequent boundaries of different layers. The program was also implemented to segment angiographic maps of different chorio-retinal layers using "segmentation matrices." The method was tested and successfully validated on OCT images from six normal human eyes as well as eyes with non-exudative age-related macular degeneration (AMD). The thickness of microstructure and microvasculature for different layers located in the chorio-retinal segment of the eye was also generated and compared. A decent efficiency in terms of processing time, sensitivity, and accuracy was observed compared to the manual segmentation and other existing methods. The proposed method automatically segments whole OCT images of chorio-retinal complex with augmented probability maps generation in OCT volume dataset. We have also evaluated the segmentation results using quantitative metrics such as Dice coefficient and Hausdorff distance This method realizes a mean descent Dice similarity coefficient (DSC) value of 0.82 (range, 0.816-0.864) for RPE and CSI layer.

A parallel biological computing algorithm to solve the vertex coloring problem with polynomial time complexity

The vertex coloring problem is a well-known combinatorial problem that requires each vertex to be assigned a corresponding color so that the colors on adjacent vertices are different, and the total number of colors used is minimized. It is a famous NP-hard problem in graph theory. As of now, there is no effective algorithm to solve it. As a kind of intelligent computing algorithm, DNA computing has the advantages of high parallelism and high storage density, so it is widely used in solving classical combinatorial optimization problems. In this paper, we propose a new DNA algorithm that uses DNA molecular operations to solve the vertex coloring problem. For a simple n-vertex graph and k different kinds of color, we appropriately use DNA strands to indicate edges and vertices. Through basic biochemical reaction operations, the solution to the problem is obtained in the O (kn2) time complexity. Our proposed DNA algorithm is a new attempt and application for solving Nondeterministic Polynomial (NP) problem, and it provides clear evidence for the ability of DNA calculations to perform such difficult computational problems in the future.

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.

Solving the maximal matching problem with DNA molecules in Adleman–Lipton model

The maximal matching problem (MMP) is to find maximal edge subsets in a given undirected graph, that no pair of edges are adjacent in the subsets. It is a vitally important NP-complete problem in graph theory and applied mathematics, having numerous real life applications in optimal combination and linear programming fields. It can be difficultly solved by the electronic computer in exponential level time. Meanwhile in previous studies deoxyribonucleic acid (DNA) molecular operations usually were used to solve NP-complete continuous path search problems, e.g. HPP, traveling salesman problem, rarely for NP-hard problems with discrete vertices or edges solutions, such as the minimum vertex cover problem, graph coloring problem and so on. In this paper, we present a DNA algorithm for solving the MMP with DNA molecular operations. For an undirected graph with [Formula: see text] vertices and [Formula: see text] edges, we reasonably design fixed length DNA strands representing vertices and edges of the graph, take appropriate steps and get the solutions of the MMP in proper length range using [Formula: see text] time. We extend the application of DNA molecular operations and simultaneously simplify the complexity of the computation.

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.

Marine yeast isolation and industrial application

Over the last century, terrestrial yeasts have been widely used in various industries, such as baking, brewing, wine, bioethanol and pharmaceutical protein production. However, only little attention has been given to marine yeasts. Recent research showed that marine yeasts have several unique and promising features over the terrestrial yeasts, for example higher osmosis tolerance, higher special chemical productivity and production of industrial enzymes. These indicate that marine yeasts have great potential to be applied in various industries. This review gathers the most recent techniques used for marine yeast isolation as well as the latest applications of marine yeast in bioethanol, pharmaceutical and enzyme production fields.