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...
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2015
|
| Subjects: | |
| Online Access: | http://umpir.ump.edu.my/id/eprint/17669/16/Generic%20DNA%20encoding%20design%20scheme%20to%20solve%20combinatorial%20problems.pdf |
| _version_ | 1796992130946695168 |
|---|---|
| author | Rofilde, Hasudungan |
| author_facet | Rofilde, Hasudungan |
| author_sort | Rofilde, Hasudungan |
| collection | UMP |
| 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. |
| first_indexed | 2024-03-06T12:15:32Z |
| format | Thesis |
| id | UMPir17669 |
| institution | Universiti Malaysia Pahang |
| language | English |
| last_indexed | 2024-03-06T12:15:32Z |
| publishDate | 2015 |
| record_format | dspace |
| spelling | UMPir176692021-12-10T02:27:30Z 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 pdf en http://umpir.ump.edu.my/id/eprint/17669/16/Generic%20DNA%20encoding%20design%20scheme%20to%20solve%20combinatorial%20problems.pdf Rofilde, Hasudungan (2015) Generic DNA encoding design scheme to solve combinatorial problems. Masters thesis, Universiti Malaysia Pahang (Contributors, UNSPECIFIED: UNSPECIFIED). |
| spellingShingle | QA75 Electronic computers. Computer science Rofilde, Hasudungan Generic DNA encoding design scheme to solve combinatorial problems |
| title | 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_short | Generic DNA encoding design scheme to solve combinatorial problems |
| title_sort | generic dna encoding design scheme to solve combinatorial problems |
| topic | QA75 Electronic computers. Computer science |
| url | http://umpir.ump.edu.my/id/eprint/17669/16/Generic%20DNA%20encoding%20design%20scheme%20to%20solve%20combinatorial%20problems.pdf |
| work_keys_str_mv | AT rofildehasudungan genericdnaencodingdesignschemetosolvecombinatorialproblems |