1
|
Wu X, Wang Z, Wu T, Bao X. Solving the Family Traveling Salesperson Problem in the Adleman-Lipton model based on DNA computing. IEEE Trans Nanobioscience 2021; 21:75-85. [PMID: 34460379 DOI: 10.1109/tnb.2021.3109067] [Citation(s) in RCA: 12] [Impact Index Per Article: 4.0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/05/2022]
Abstract
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.
Collapse
|
2
|
Chang WL, Chen JC, Chung WY, Hsiao CY, Wong R, Vasilakos AV. Quantum Speedup and Mathematical Solutions of Implementing Bio-Molecular Solutions for the Independent Set Problem on IBM Quantum Computers. IEEE Trans Nanobioscience 2021; 20:354-376. [PMID: 33900920 DOI: 10.1109/tnb.2021.3075733] [Citation(s) in RCA: 7] [Impact Index Per Article: 2.3] [Reference Citation Analysis] [Abstract] [MESH Headings] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/06/2022]
Abstract
In this paper, we propose a bio-molecular algorithm with O( n2 + m ) biological operations, O( 2n ) DNA strands, O( n ) tubes and the longest DNA strand, O( n ), for solving the independent-set problem for any graph G with m edges and n vertices. Next, we show that a new kind of the straightforward Boolean circuit yielded from the bio-molecular solutions with m NAND gates, ( m +n × ( n + 1 )) AND gates and (( n × ( n + 1 ))/2) NOT gates can find the maximal independent-set(s) to the independent-set problem for any graph G with m edges and n vertices. We show that a new kind of the proposed quantum-molecular algorithm can find the maximal independent set(s) with the lower bound Ω ( 2n/2 ) queries and the upper bound O( 2n/2 ) queries. This work offers an obvious evidence for that to solve the independent-set problem in any graph G with m edges and n vertices, bio-molecular computers are able to generate a new kind of the straightforward Boolean circuit such that by means of implementing it quantum computers can give a quadratic speed-up. This work also offers one obvious evidence that quantum computers can significantly accelerate the speed and enhance the scalability of bio-molecular computers. Next, the element distinctness problem with input of n bits is to determine whether the given 2n real numbers are distinct or not. The quantum lower bound of solving the element distinctness problem is Ω ( 2n×(2/3) ) queries in the case of a quantum walk algorithm. We further show that the proposed quantum-molecular algorithm reduces the quantum lower bound to Ω (( 2n/2 )/( [Formula: see text]) queries. Furthermore, to justify the feasibility of the proposed quantum-molecular algorithm, we successfully solve a typical independent set problem for a graph G with two vertices and one edge by carrying out experiments on the backend ibmqx4 with five quantum bits and the backend simulator with 32 quantum bits on IBM's quantum computer.
Collapse
|
3
|
Ji Z, Wang Z, Wu T, Huang W. Solving the 0-1 knapsack problem based on a parallel intelligent molecular computing model system. JOURNAL OF INTELLIGENT & FUZZY SYSTEMS 2017. [DOI: 10.3233/jifs-169321] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/15/2022]
Affiliation(s)
- Zuwen Ji
- State Key Laboratory of Simulation and Regulation of River Basin Water Cycle, China Institute of Water Resources and Hydropower Research, Beijing, P.R. China
| | - Zhaocai Wang
- State Key Laboratory of Simulation and Regulation of River Basin Water Cycle, China Institute of Water Resources and Hydropower Research, Beijing, P.R. China
- College of Information, Shanghai Ocean University, Shanghai, P.R. China
| | - Tunhua Wu
- School of Information and Engineering, Wenzhou Medical University, Wenzhou, P.R. China
| | - Wei Huang
- College of Mathematics and Information Science, Guiyang University, Guizhou, P.R. China
| |
Collapse
|
4
|
Sanches CAA, Soma NY. A general resolution of intractable problems in polynomial time through DNA Computing. Biosystems 2016; 150:119-131. [PMID: 27693626 DOI: 10.1016/j.biosystems.2016.09.008] [Citation(s) in RCA: 8] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/08/2016] [Revised: 07/15/2016] [Accepted: 09/23/2016] [Indexed: 11/29/2022]
Abstract
Based on a set of known biological operations, a general resolution of intractable problems in polynomial time through DNA Computing is presented. This scheme has been applied to solve two NP-Hard problems (Minimization of Open Stacks Problem and Matrix Bandwidth Minimization Problem) and three co-NP-Complete problems (associated with Hamiltonian Path, Traveling Salesman and Hamiltonian Circuit), which have not been solved with this model. Conclusions and open questions concerning the computational capacity of this model are presented, and research topics are suggested.
Collapse
Affiliation(s)
- C A A Sanches
- Instituto Tecnológico de Aeronáutica - CTA/ITA/IEC, Praça Mal. Eduardo Gomes, 50, São José dos Campos, SP 12228-900, Brazil.
| | - N Y Soma
- Instituto Tecnológico de Aeronáutica - CTA/ITA/IEC, Praça Mal. Eduardo Gomes, 50, São José dos Campos, SP 12228-900, Brazil.
| |
Collapse
|
5
|
Ning J, Li Y, Yu W. Molecular Sticker Model Stimulation on Silicon for a Maximum Clique Problem. Int J Mol Sci 2015; 16:13474-89. [PMID: 26075867 PMCID: PMC4490504 DOI: 10.3390/ijms160613474] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/25/2015] [Revised: 05/25/2015] [Accepted: 06/01/2015] [Indexed: 11/16/2022] Open
Abstract
Molecular computers (also called DNA computers), as an alternative to traditional electronic computers, are smaller in size but more energy efficient, and have massive parallel processing capacity. However, DNA computers may not outperform electronic computers owing to their higher error rates and some limitations of the biological laboratory. The stickers model, as a typical DNA-based computer, is computationally complete and universal, and can be viewed as a bit-vertically operating machine. This makes it attractive for silicon implementation. Inspired by the information processing method on the stickers computer, we propose a novel parallel computing model called DEM (DNA Electronic Computing Model) on System-on-a-Programmable-Chip (SOPC) architecture. Except for the significant difference in the computing medium—transistor chips rather than bio-molecules—the DEM works similarly to DNA computers in immense parallel information processing. Additionally, a plasma display panel (PDP) is used to show the change of solutions, and helps us directly see the distribution of assignments. The feasibility of the DEM is tested by applying it to compute a maximum clique problem (MCP) with eight vertices. Owing to the limited computing sources on SOPC architecture, the DEM could solve moderate-size problems in polynomial time.
Collapse
Affiliation(s)
- Jianguo Ning
- State Key Laboratory of Explosion Science and Technology, Beijing Institute of Technology, Beijing 100081, China.
| | - Yanmei Li
- State Key Laboratory of Explosion Science and Technology, Beijing Institute of Technology, Beijing 100081, China.
| | - Wen Yu
- Beijing Key Laboratory of Intelligent Telecommunication Software and Multimedia, Beijing University of Posts and Telecommunications, Beijing 100876, China.
| |
Collapse
|
6
|
Wang Z, Huang D, Meng H, Tang C. A new fast algorithm for solving the minimum spanning tree problem based on DNA molecules computation. Biosystems 2013; 114:1-7. [PMID: 23871964 DOI: 10.1016/j.biosystems.2013.07.007] [Citation(s) in RCA: 10] [Impact Index Per Article: 0.9] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/02/2013] [Revised: 04/23/2013] [Accepted: 07/08/2013] [Indexed: 11/26/2022]
Abstract
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.
Collapse
Affiliation(s)
- Zhaocai Wang
- College of Information, Shanghai Ocean University, Shanghai 201306, PR China.
| | | | | | | |
Collapse
|
7
|
Nuser MS. A Molecular Solution to the Three-Partition Problem. JOURNAL OF INFORMATION TECHNOLOGY RESEARCH 2012. [DOI: 10.4018/jitr.2012100102] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/09/2022]
Abstract
Given a set of numbers, the three-partition problem is to divide them into disjoint triplets that all have the same sum. The problem is NP-complete. This paper presents an algorithm to solve this problem using the biomolecular computing approach. The algorithm uses a distinctive encoding technique that depends on the numbers values which omits the need to an adder to find the sum. The algorithm is explained and an analysis of its complexity in terms of time, the number of strands, number of tubes, and the longest library strand used is presented. A simulation of the algorithm is implemented and tested. This algorithm further proves the ability of molecular computing in solving hard problems.
Collapse
Affiliation(s)
- Maryam S. Nuser
- Computer Information Systems Department, Yarmouk University, Irbid, Jordan
| |
Collapse
|
8
|
Shah AA, Folino G, Krasnogor N. Toward High-Throughput, Multicriteria Protein-Structure Comparison and Analysis. IEEE Trans Nanobioscience 2010; 9:144-55. [DOI: 10.1109/tnb.2010.2043851] [Citation(s) in RCA: 7] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/07/2022]
|
9
|
Shi NY, Chu CP. A molecular solution to the hitting-set problem in DNA-based supercomputing. Inf Sci (N Y) 2010. [DOI: 10.1016/j.ins.2009.11.019] [Citation(s) in RCA: 9] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 12/01/2022]
|
10
|
Chang WL, Ren TT, Luo J, Feng M, Guo M, Weicheng Lin K. Quantum algorithms for biomolecular solutions of the satisfiability problem on a quantum machine. IEEE Trans Nanobioscience 2008; 7:215-22. [PMID: 18779102 DOI: 10.1109/tnb.2008.2002286] [Citation(s) in RCA: 17] [Impact Index Per Article: 1.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/07/2022]
Abstract
In this paper, we demonstrate that the logic computation performed by the DNA-based algorithm for solving general cases of the satisfiability problem can be implemented more efficiently by our proposed quantum algorithm on the quantum machine proposed by Deutsch. To test our theory, we carry out a three-quantum bit nuclear magnetic resonance experiment for solving the simplest satisfiability problem.
Collapse
Affiliation(s)
- Weng-Long Chang
- Department of Computer Science and Information Engineering, National Kaohsiung University of Applied Sciences, Kaohsiung City 80778, Taiwan, ROC.
| | | | | | | | | | | |
Collapse
|