Pairwise Sequence Alignment by Differential Evolutionary Algorithm with New Mutation Strategy
Lakshmi Naga Jayaprada.Gavarraju1, K. Karteeka Pavan2
1Lakshmi Naga Jayaprada. Gavarraju, Assoc.Prof, Dept. of Computer Science & Engineering, Narasaraopeta Engineering College [Autonomous], Narasaraopet, Guntur(Dt), A.P., India.
2Kanadam Karteeka Pavan, Professor & Head Department of Computer Applications, R.V.R.& J.C.College of Engineering [Autonomous], Chowdavaram , Guntur , A.P., India.
Manuscript received on November 25, 2019. | Revised Manuscript received on December 08, 2019. | Manuscript published on December 30, 2019. | PP: 445-453 | Volume-9 Issue-2, December, 2019. | Retrieval Number: B3136129219/2019©BEIESP | DOI: 10.35940/ijeat.B3136.129219
Open Access | Ethics and Policies | Cite | Mendeley
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: Sequence alignment is a significant facet in the bio-informatics research field for the molecular sequence analysis. Arrangement of two biological sequences by maximizing the similarities between the sequences by incorporating and adjusting gaps is Pairwise Sequence Alignment (PSA). Arrangement of multiple sequences is Multiple Sequence Alignment (MSA). Though Dynamic programming can produce optimal sequence alignment for PSA it suffers from a problem when multiple optimal paths are present and trace back is required. Back tracking becomes complex and it is also not suitable for MSA. So many meta-heuristic algorithms like Genetic Algorithm (GA) and Differential Evolutionary Algorithm (DE) are developed in the recent years to resolve the issue of optimization. Both GA and DE are used to produce optimal sequence alignment. But Compared to GA, DE is able to produce more optimal sequence alignment. To further enhance the performance of DE a new mutant is proposed by considering best, worst and a random candidate solution and applied on DE. It is named as New Differential Evolutionary Algorithm (NDE). By taking the test sequences from a bench mark data set “prefab4ref” tests are performed on GA, All DE mutants and NDE and it is observed that the proposed algorithm NDE outperformed all the other algorithms.
Keywords: Sequence Alignment, Biological Sequences, Pairwise Sequence Alignment, Multiple Sequence Alignment, Genetic Algorithm, Differential Evolutionary Algorithm