Implementation of genetic algorithm for optimizing DNA sequence alignment

Author

Al Junid, Syed Abdul Mutalib ; Reffin, Muhd Shahirad ; Majid, Zulkifi Abd ; Tahir, Nooritawati Md ; Haron, Muhammad Adib

Author_Institution

Fac. of Electr. Eng., Univ. Teknol. MARA, Shah Alam, Malaysia

fYear

2012

fDate

7-8 April 2012

Firstpage

80

Lastpage

85

Abstract

This paper presents potential of genetic algorithms (GA) for optimizing DNA sequences alignment based on dynamic programming or evolutionary programming. The ultimate objective of this paper is to accelerate the process of DNA sequences alignment towards reducing the time and space complexity. In addition, the theoretical study, design, compilation and simulation of the proposed GA were carried out using Xilinx ISE 12.3 EDA software by applying divide and conquer design technique towards finding the optimal solution. The proposed GA has shown that it can solve up to 10 DNA sequences base pair in three clock cycles with reduction time up to 84.21 % as compare to original Smith-Waterman algorithm. As a conclusion, the proposed GA has proved and able to optimize the existing DNA sequences alignment time complexity.

Keywords

DNA; biology computing; computational complexity; dynamic programming; genetic algorithms; DNA sequence alignment optimization; GA; Smith-Waterman algorithm; Xilinx ISE 12.3 EDA software; biological sequences database; clock cycles; divide and conquer design technique; dynamic programming; evolutionary programming; genetic algorithm; space complexity reduction; time complexity reduction; Business; DNA sequences; genetic algorithms; sequence alignment;

fLanguage

English

Publisher

ieee

Conference_Titel

Business Engineering and Industrial Applications Colloquium (BEIAC), 2012 IEEE

Conference_Location

Kuala Lumpur

Print_ISBN

978-1-4673-0425-2

Type

conf

DOI

10.1109/BEIAC.2012.6226111

Filename

6226111