Refinements of Longest Common Subsequence algorithm

This paper reports on experiments performed to investigate possible improvements of the Longest Common Subsequence (LCS). LCS algorithm in its basic format has a time cost of O(mn) when comparing two sequences of length m and n. The algorithm has been refined and resulted in reduction and savings in cost that are valuable improvements in efficiencies for sequences comparisons. Two refinements where done on the algorithm. First refinement improved the cost 50% -at the best case but it still costs O(mn) at its worst case. The second refinement improved the performance of the basic implementation by 50% at the worst case scenario with much better cost at other cases. Experimental validations of these improvements used real data sets with sequences of sizes ranging from 5 characters up to 44795 characters. Results obtained have showed the utility of the two LCS algorithm refinements which were developed and experimentally validated.