A Modified Algorithm to Find Longest Common Subsequences and Optimizing Space, Time

Abstract

"In the study of Longest Common Subsequence (LCS) is an important topic and an important component in the application of Computational Mathematics. The LCS problem is to find a subsequence which is common to at least two or more given sequences. The largest length subsequence is called as LCS. Due to high demands for computational time, power and memory, this paper introduces a new efficient modified algorithm to find the longest common subsequences in two different sequences X and Y. The sequences represented in memory in vertical and horizontal directions. An array is established where each sequence assigned in this array. A new node is added to it for every match between two sequences. If two or more matches in different locations in Sequence Y share the same in X, the corresponding node will construct the LCS in various ways. Continuing in this process we obtain a group of LCS between the sequences X and Y. The proposed modified algorithm has been implemented and tested using Matlab language. This algorithm shows very good speedups and indicated efficiently minimizing the space complexity and optimizing the time taken to execute and impressive improvements has been achieved"