Improving DNA computing using evolutionary algorithms

Other Title(s)

تحسين حوسبت الحمض النووي باستخدام الخوارزميات المتطورة

Dissertant

Ibrahim, Godar J.

Thesis advisor

Rashid, Tariq Ahmad
al-Ubaydi, Ahmad Tariq Sadiq

University

Salahaddin University-Hawler

Faculty

College of Engineering

Department

Software Engineering Department

University Country

Iraq

Degree

Master

Degree Date

2012

English Abstract

DNA computing relies on biochemical reactions of DNA molecules.

Since the annealing of the DNA molecules are randomly and by chance that may result in incorrect or undesirable and non-optimum results, the idea of how to improve the algorithm came up.

Evolutionary Computation focuses on probabilistic search and optimization methods which are simulating the model of organic evolution.

The optimization feature of Evolutionary Computation can be used to optimize DNA Computing.

The purpose of this thesis is to propose a simulated evolutionary DNA computing model which integrates DNA computing with Evolutionary Algorithm in order to optimize the standard DNA Computing Algorithm.

The evolutionary approach would offer the possibility to increase dimensionality by substituting the usual filtering approach with an evolutionary one.

So by means of iteratively amplifying and recombination a population of strands, removing incorrect solutions from the population, and selecting the best solutions by means of gel electrophoresis, an optimal or near-optimal solution can be evolved rather than extracted from the initial population.

So the adoption of the evolutionary paradigm to DNA computation can help us to find optimal solutions.

Shortest Path Problem (SPP) and Job Scheduling Problem (JSP) are selected to be used as case studies for testing the standard DNA computing and evolutionary DNA computing and comparing the results.

The algorithms are implemented in Java language and it has been tried to have an adaptive DNA algorithm to be applied to other problems too.

The proposed enhancement in the algorithm has four modifications.

Each operation has its own improvement on the algorithm while they are all sharing the same representation of the problem knowledge.

The four modifications are Modifying Standard DNA algorithm with adding/replacing start/end to the PCR (Polymerase Chain Reaction) dropped strands for SPP, Modifying Standard DNA algorithm with semi Crossovering the dropped PCR strands for SPP, Modifying Standard DNA algorithm with semi Crossovering the dropped SSCP (Single Strand Conformation Polymorphism) strands for SPP, and Modifying Standard DNA algorithm with Evolutionary SSCP operation for both problems.

By comparing the final results of the Standard DNA and Evolutionary DNA algorithms for 25 networks and 5 jobs with 5-10 iterations of the application running, indicates acceptable improvement in the DNA computing.

Although the average running time and memory capacity in evolutionary DNA is increased by % 778 and % 103 respectively, but the average number of final solutions is increased by % 1,731 and average cost of final solution by % 10.

Also it is noticeable that Evolutionary DNA is always generating the optimum solution for Job Scheduling problem.

Main Subjects

Media and Communication

Topics

No. of Pages

113

Table of Contents

Table of contents.

Abstract.

Chapter One : introduction.

Chapter Two : DNA computing and evolutionary strategies.

Chapter Three : proposed evolutionary DNA algorithm.

Chapter Four : experimental results.

Chapter Five : conclusions and recommendations.

References.

American Psychological Association (APA)

Ibrahim, Godar J.. (2012). Improving DNA computing using evolutionary algorithms. (Master's theses Theses and Dissertations Master). Salahaddin University-Hawler, Iraq
https://search.emarefa.net/detail/BIM-314414

Modern Language Association (MLA)

Ibrahim, Godar J.. Improving DNA computing using evolutionary algorithms. (Master's theses Theses and Dissertations Master). Salahaddin University-Hawler. (2012).
https://search.emarefa.net/detail/BIM-314414

American Medical Association (AMA)

Ibrahim, Godar J.. (2012). Improving DNA computing using evolutionary algorithms. (Master's theses Theses and Dissertations Master). Salahaddin University-Hawler, Iraq
https://search.emarefa.net/detail/BIM-314414

Language

English

Data Type

Arab Theses

Record ID

BIM-314414