Title :
Potential of Graph Theory Algorithm Approach for DNA Sequence Alignment and Comparison
Author :
Junid, Syed Abdul Mutalib Al ; Tahir, Nooritawati Md ; Majid, Zulkifli Abd ; Idros, Mohd Faizul Md
Author_Institution :
Fac. of Electr. Eng., Univ. Teknol. Mara, Shah Alam, Malaysia
Abstract :
Today, the need for high performance computation method for align biological sequence has increased due to exponential growth of biological sequence databases. Therefore, this paper is an attempt to study and investigate the potential of graph theory algorithm approach for optimizing the alignment process of DNA sequences towards determines the region of common between two or more DNA sequences. This study will initially involve the modification of algorithms, mathematical formulation, logic design, simulation, verification and implementation of graph-theory algorithms in DNA sequences alignment context. The design and simulation was carried out using Altera Quartus II version 7.2 EDA software and targeted to Altera Cyclone II FPGA. As a result, the proposed DNA sequences alignment using graph theory algorithm able to determine the optimal path for four DNA sequences base-pair in two clock cycle with reduction 71.42% compare to Smith Waterman algorithm. Finally, the new proposed DNA sequences using graph theory algorithm alignment can accelerate the process of DNA sequences alignment faster than existing DNA sequences alignment on hardware accelerator.
Keywords :
DNA; graph theory; molecular biophysics; DNA sequence alignment; Smith Waterman algorithm; align biological sequence databases; altera cyclone II FPGA; altera quartus II version 7.2 EDA software; graph theory algorithm; hardware accelerator; logic design; mathematical formulation; verification; Algorithm design and analysis; Bioinformatics; Clocks; DNA; Filling; Graph theory; Software algorithms; Algorithm Approach; Alignment; Comparison; DNA Sequence; Graph Theory;
Conference_Titel :
Intelligent Systems, Modelling and Simulation (ISMS), 2012 Third International Conference on
Conference_Location :
Kota Kinabalu
Print_ISBN :
978-1-4673-0886-1
DOI :
10.1109/ISMS.2012.123