Generic DNA encoding design scheme to solve combinatorial problems

Combinatorial problems arise in many areas of computer science and application domains. It involves finding groupings, ordering, or assignment of a discrete; finite set of objects that satisfy given conditions. The complexity of combinatorial problems is classified as NP meaning that algorithms are...

Full description

Bibliographic Details
Main Author:	Rofilde, Hasudungan
Format:	Thesis
Language:	English English English
Published:	2015
Subjects:	QA75 Electronic computers. Computer science
Online Access:	http://umpir.ump.edu.my/id/eprint/17669/ http://umpir.ump.edu.my/id/eprint/17669/ http://umpir.ump.edu.my/id/eprint/17669/1/Generic%20DNA%20encoding%20design%20scheme%20to%20solve%20combinatorial%20problems%20-%20Table%20of%20contents.PDF http://umpir.ump.edu.my/id/eprint/17669/6/Generic%20DNA%20encoding%20design%20scheme%20to%20solve%20combinatorial%20problems%20-%20Abstract.PDF http://umpir.ump.edu.my/id/eprint/17669/7/Generic%20DNA%20encoding%20design%20scheme%20to%20solve%20combinatorial%20problems%20-%20References.PDF

id	ump-17669
recordtype	eprints
spelling	ump-176692017-05-05T02:53:03Z http://umpir.ump.edu.my/id/eprint/17669/ Generic DNA encoding design scheme to solve combinatorial problems Rofilde, Hasudungan QA75 Electronic computers. Computer science Combinatorial problems arise in many areas of computer science and application domains. It involves finding groupings, ordering, or assignment of a discrete; finite set of objects that satisfy given conditions. The complexity of combinatorial problems is classified as NP meaning that algorithms are yet to exist to efficiently solve the problem. However, DNA computing can solve the problem in linear time since the parallel processing power of DNA computing is able to generate a solution in a single process. DNA encoding is the first important step in DNA computing phases. Currently, data encoding in DNA computing is tightly coupled with an algorithm that solves an instance of the problem. Solving another problem requires developing specific encoding and computations anew to prove DNA encoding and form the algorithm which is costly. This study proposes a generic DNA encoding schema capable of representing different combinatorial problems. To render the generic encoding scheme capable of solving the different problems, we introduce graph modelling to describe all possible solutions for the problem, where the parameters are converted into vertices and edges before encoding it into DNA sequences. From graph modelling, we construct the encoding scheme consisting of three parts: (1) vertex that links to another vertex, (2} edges that contain information and (3) vertex that links to another vertex. To prove the concept, we employ four different combinatorial problems: Traveling Salesman Problem, Distribution Centre Location Problem, Scheduling Robotic Cell Problem, and Vertex Colouring Problem. Computer simulations show that the proposed generic encoding can generate the desired solution and biological operations could produce solutions for each problem. This approach was applied successfully to solve four hard combinatorial problems. Using this encoding scheme would enable researchers to solve other hard problems whilst also improving the algorithm. 2015-12 Thesis NonPeerReviewed application/pdf en http://umpir.ump.edu.my/id/eprint/17669/1/Generic%20DNA%20encoding%20design%20scheme%20to%20solve%20combinatorial%20problems%20-%20Table%20of%20contents.PDF application/pdf en http://umpir.ump.edu.my/id/eprint/17669/6/Generic%20DNA%20encoding%20design%20scheme%20to%20solve%20combinatorial%20problems%20-%20Abstract.PDF application/pdf en http://umpir.ump.edu.my/id/eprint/17669/7/Generic%20DNA%20encoding%20design%20scheme%20to%20solve%20combinatorial%20problems%20-%20References.PDF Rofilde, Hasudungan (2015) Generic DNA encoding design scheme to solve combinatorial problems. Masters thesis, Universiti Malaysia Pahang. http://iportal.ump.edu.my/lib/item?id=chamo:97831&theme=UMP2
repository_type	Digital Repository
institution_category	Local University
institution	Universiti Malaysia Pahang
building	UMP Institutional Repository
collection	Online Access
language	English English English
topic	QA75 Electronic computers. Computer science
spellingShingle	QA75 Electronic computers. Computer science Rofilde, Hasudungan Generic DNA encoding design scheme to solve combinatorial problems
description	Combinatorial problems arise in many areas of computer science and application domains. It involves finding groupings, ordering, or assignment of a discrete; finite set of objects that satisfy given conditions. The complexity of combinatorial problems is classified as NP meaning that algorithms are yet to exist to efficiently solve the problem. However, DNA computing can solve the problem in linear time since the parallel processing power of DNA computing is able to generate a solution in a single process. DNA encoding is the first important step in DNA computing phases. Currently, data encoding in DNA computing is tightly coupled with an algorithm that solves an instance of the problem. Solving another problem requires developing specific encoding and computations anew to prove DNA encoding and form the algorithm which is costly. This study proposes a generic DNA encoding schema capable of representing different combinatorial problems. To render the generic encoding scheme capable of solving the different problems, we introduce graph modelling to describe all possible solutions for the problem, where the parameters are converted into vertices and edges before encoding it into DNA sequences. From graph modelling, we construct the encoding scheme consisting of three parts: (1) vertex that links to another vertex, (2} edges that contain information and (3) vertex that links to another vertex. To prove the concept, we employ four different combinatorial problems: Traveling Salesman Problem, Distribution Centre Location Problem, Scheduling Robotic Cell Problem, and Vertex Colouring Problem. Computer simulations show that the proposed generic encoding can generate the desired solution and biological operations could produce solutions for each problem. This approach was applied successfully to solve four hard combinatorial problems. Using this encoding scheme would enable researchers to solve other hard problems whilst also improving the algorithm.
format	Thesis
author	Rofilde, Hasudungan
author_facet	Rofilde, Hasudungan
author_sort	Rofilde, Hasudungan
title	Generic DNA encoding design scheme to solve combinatorial problems
title_short	Generic DNA encoding design scheme to solve combinatorial problems
title_full	Generic DNA encoding design scheme to solve combinatorial problems
title_fullStr	Generic DNA encoding design scheme to solve combinatorial problems
title_full_unstemmed	Generic DNA encoding design scheme to solve combinatorial problems
title_sort	generic dna encoding design scheme to solve combinatorial problems
publishDate	2015
url	http://umpir.ump.edu.my/id/eprint/17669/ http://umpir.ump.edu.my/id/eprint/17669/ http://umpir.ump.edu.my/id/eprint/17669/1/Generic%20DNA%20encoding%20design%20scheme%20to%20solve%20combinatorial%20problems%20-%20Table%20of%20contents.PDF http://umpir.ump.edu.my/id/eprint/17669/6/Generic%20DNA%20encoding%20design%20scheme%20to%20solve%20combinatorial%20problems%20-%20Abstract.PDF http://umpir.ump.edu.my/id/eprint/17669/7/Generic%20DNA%20encoding%20design%20scheme%20to%20solve%20combinatorial%20problems%20-%20References.PDF
first_indexed	2023-09-18T22:24:33Z
last_indexed	2023-09-18T22:24:33Z
_version_	1777415878948683776

Generic DNA encoding design scheme to solve combinatorial problems

Similar Items