Design and development of optimal path trace back using graph theory technique for accelerate DNA sequence alignment accelerator

This paper presents the improvement of Smith-Waterman algorithm in comparing between two DNA sequence alignments. The existing Smith-Waterman algorithm had complex memory and low performance where the time also was consumed caused by high sensitivity of the large sequences long. This new technique is been develope in order to overcome these problem. The Verilog HDL coding is been written using Quartus 2 version 9.1. The Smith-Waterman is been simplified into four modules which were initialization, score calculation, matrix filling and optimal path. The scope of the paper based on optimal path trace back using graph theory. The kind of graph theory that been used was indirected graph with linear algebra. This method had improved the accuracy of trace back and the initialization modules had achieved 93.75% reduction in memory space requirement.