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

Saved in:

Bibliographic Details
Main Author:	Rofilde, Hasudungan
Format:	Thesis
Language:	English
Published:	2015
Subjects:	QA75 Electronic computers Computer science
Online Access:	http://umpir.ump.edu.my/id/eprint/17669/16/Generic%20DNA%20encoding%20design%20scheme%20to%20solve%20combinatorial%20problems.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-ump-ir.17669
record_format	uketd_dc
spelling	my-ump-ir.176692021-12-10T02:27:30Z Generic DNA encoding design scheme to solve combinatorial problems 2015-12 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 http://umpir.ump.edu.my/id/eprint/17669/ http://umpir.ump.edu.my/id/eprint/17669/16/Generic%20DNA%20encoding%20design%20scheme%20to%20solve%20combinatorial%20problems.pdf pdf en public masters Universiti Malaysia Pahang Faculty of Computer Systems and Software Engineering
institution	Universiti Malaysia Pahang Al-Sultan Abdullah
collection	UMPSA Institutional Repository
language	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
qualification_level	Master's degree
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
granting_institution	Universiti Malaysia Pahang
granting_department	Faculty of Computer Systems and Software Engineering
publishDate	2015
url	http://umpir.ump.edu.my/id/eprint/17669/16/Generic%20DNA%20encoding%20design%20scheme%20to%20solve%20combinatorial%20problems.pdf
_version_	1783732021867053056

Generic DNA encoding design scheme to solve combinatorial problems

Similar Items