COMPARATIVE ANALYSIS OF DYNAMIC PROGRAMMING ALGORITHMS TO FIND SIMILARITY IN GENE SEQUENCES

Shankar Biradar, Vinod Desai, Basavaraj Madagouda, Manjunath Patil

Abstract: There exist many computational methods for finding similarity in gene sequence, finding suitable methods that gives optimal similarity is difficult task. Objective of this project is to find an appropriate method to compute similarity in gene/protein sequence, both within the families and across the families. Many dynamic programming algorithms like Levenshtein edit distance; Longest Common Subsequence and Smith-waterman have used dynamic programming approach to find similarities between two sequences. But none of the method mentioned above have used real benchmark data sets. They have only used dynamic programming algorithms for synthetic data. We proposed a new method to compute similarity. The performance of the proposed algorithm is evaluated using number of data sets from various families, and similarity value is calculated both within the family and across the families. A comparative analysis and time complexity of the proposed method reveal that Smith-waterman approach is appropriate method when gene/protein sequence belongs to same family and Longest Common Subsequence is best suited when sequence belong to two different families.

Keywords: Bioinformatics, Gene, Gene Sequencing, Edit distance, String Similarity

DOI: https://doi.org/10.15623/ijret.2013.0208049