Longest common subsequence
The Longest-common subsquence problem is the search for an efficient method of finding the longest common subsquence (LCS). This computer science problem has gain promience thanks in part to the Bioinformatics field.
An old method of searching for LCS was to employ a brute force policy: Given a sequence X, determine all possible of subsequences of X, and check to see if each subsequence was a subsequence of Y, keeping track of the longest subsequence found. Each subsequence of X would be in the set of {1,2,3,4,....,k}. Using number theory proofs, we find that there would be 2k subsequences of X. This would be in exponential time, making this search extremely ineffective for long sequences, such as human DNA strands.
- TODO: Add in algorithm which calculates LCS in linear time
Modern LCS search methods have yielded algorithms which have cut down the exponential time to linear time. The LCS continues to be examined by computer scientists, trying to find an even faster time, perhaps one in logarithmic time.