UMP Institutional Repository

Generic DNA encoding design scheme to solve combinatorial problems

Rofilde, Hasudungan (2015) Generic DNA encoding design scheme to solve combinatorial problems. Masters thesis, Universiti Malaysia Pahang.

[img]
Preview
PDF (Generic DNA encoding design scheme to solve combinatorial problems-Table of contents)
Generic DNA encoding design scheme to solve combinatorial problems - Table of contents.PDF - Accepted Version

Download (174kB) | Preview
[img]
Preview
PDF (Generic DNA encoding design scheme to solve combinatorial problems-Abstract)
Generic DNA encoding design scheme to solve combinatorial problems - Abstract.PDF - Accepted Version

Download (98kB) | Preview
[img]
Preview
PDF (Generic DNA encoding design scheme to solve combinatorial problems-References)
Generic DNA encoding design scheme to solve combinatorial problems - References.PDF - Accepted Version

Download (322kB) | Preview

Abstract

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.

Item Type: Thesis (Masters)
Additional Information: Thesis (Master of Computer Science) -- Universiti Malaysia Pahang – 2015
Uncontrolled Keywords: DNA; combinatorial problems
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Faculty/Division: Faculty of Computer System And Software Engineering
Depositing User: Ms. Nurezzatul Akmal Salleh
Date Deposited: 05 May 2017 02:53
Last Modified: 05 May 2017 02:53
URI: http://umpir.ump.edu.my/id/eprint/17669
Download Statistic: View Download Statistics

Actions (login required)

View Item View Item