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

PDF (Generic DNA encoding design scheme to solve combinatorial problemsTable of contents)
Generic DNA encoding design scheme to solve combinatorial problems  Table of contents.PDF  Accepted Version Download (174kB)  Preview 


PDF (Generic DNA encoding design scheme to solve combinatorial problemsAbstract)
Generic DNA encoding design scheme to solve combinatorial problems  Abstract.PDF  Accepted Version Download (98kB)  Preview 


PDF (Generic DNA encoding design scheme to solve combinatorial problemsReferences)
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 