Smith-Waterman Algorithm Traceback Optimization using Structural Modelling Technique

Nur Farah Ain Saliman and Nur Dalilah Ahmad Sabri (Universiti Teknologi Mara, Malaysia); Syed Abdul Mutalib Al Junid, Nooritawati Md Tahir and Zulkifli Abd. Majid (Universiti Teknologi MARA, Malaysia)

The optimal trace back procedure for the Smith Waterman algorithm using structural modelling techniques presents in this paper. The proposed techniques been developed, compiled and simulated using Altera Quartus II Version 9.1 EDA Tools targeted to Cyclone II EP2C35 at 50MHz clock speed. Two designs evaluated in this paper. The first design uses four Finite State Machines connected to the Smith Waterman Algorithm. While, the second design uses one Finite State Machine connected to the Smith Waterman Algorithm in parallel. Analysis demonstrated that parallel design reduce the trace back run time up to 50% from the original trace back system.

Journal: International Journal of Simulation- Systems, Science and Technology- IJSSST V13

Published: Feb 27, 2012

DOI: 10.5013/IJSSST.a.13.01.08