dna and text sequence alignment common text-processing problemwhich arises in genetics and software engineeringis to test the similarity between two text strings in genetics applicationthe two strings could correspond to two strands of dnafor which we want to compute similarities likewisein software engineering applicationthe two strings could come from two versions of source code for the same programfor which we want to determine changes made from one version to the next indeeddetermining the similarity between two strings is so common that the unix and linux operating systems have built-in programnamed difffor comparing text files given string xn- subsequence of is any string that is of the form xi xi xik where + that isit is sequence of characters that are not necessarily contiguous but are nevertheless taken in order from for examplethe string aaag is subsequence of the string cgat aat gaga the dna and text similarity problem we address here is the longest common subsequence (lcsproblem in this problemwe are given two character stringsx xn- and ym- over some alphabet (such as the alphabet { ,cgt common in computational geneticsand are asked to find longest string that is subsequence of both and one way to solve the longest common subsequence problem is to enumerate all subsequences of and take the largest one that is also subsequence of since each character of is either in or not in subsequencethere are potentially different subsequences of each of which requires (mtime to determine whether it is subsequence of thusthis brute-force approach yields an exponential-time algorithm that runs in ( mtimewhich is very inefficient fortunatelythe lcs problem is efficiently solvable using dynamic programming the components of dynamic programming solution as mentioned abovethe dynamic programming technique is used primarily for optimization problemswhere we wish to find the "bestway of doing something we can apply the dynamic programming technique in such situations if the problem has certain propertiessimple subproblemsthere has to be some way of repeatedly breaking the global optimization problem into subproblems moreoverthere should be way to parameterize subproblems with just few indiceslike ijkand so on subproblem optimizationan optimal solution to the global problem must be composition of optimal subproblem solutions subproblem overlapoptimal solutions to unrelated subproblems can contain subproblems in common