AN EFFICIENT ALGORITHM FOR SOLVING LONGEST COMMON SUBSEQUENCE PROBLEM

Abstract

Sequence alignment is an important problem in computational biology and finding the longest common subsequences(LCS) of multiple string sequences is an essential and effective technique in sequence alignment problem. In this paper solving LCS problem using dynamic programming method have been proposed with reduced time and space complexity. We developed an efficient algorithm to solve the longest common subsequence problem, using a new technique that improved the LCS algorithm with time complexity of O(m*n). The algorithm takes the advantage over the existing algorithm and improving the performance and tested on randomly generated sequences of different length.