Suppose we are given two short DNA sequencesseq1
andseq2
.Suppose we are also given a set of operations:
Consider the two sequences below
1 2 |
|
What is the minimum number of operations required to convert one sequence into the other?
Brilli the ant sees a square matrix consisting of only 's and s. He is given the task of finding the largest square space( the largest square submatrix consisting of only 's) . For example if he was given the below table, the shaded area would be the largest square area:
Unfortunately Brilli is given a matrix of much larger size. Being the competent programmer that he is, he divides the problem into subproblems and comes up with a brilliant dynamic programming solution.
His dynamic programming solution considers the subproblem . being the side length of the largest square space whose bottom-right corner is at .
Once he solves the problem, his table has the following values:
Given that there is a 1 at [16][15], what is the value of ?
The longest common subsequence (LCS) problem is defined as follows:
Given two strings: string of length and string of length , the goal is to produce their longest common subsequence: the longest sequence of characters that appear left-to-right (but not necessarily in a contiguous block) in both strings.
For example:
=BZHAC
=HKABFT
Then the longest common subsequence has a length of
and isHAB
.
Suppose you have the following snippets of two genes which you suspect to code for homologous proteins, but to have diverged long ago on the evolutionary scale. Find their LCS, what is its length?
1 23 4 5 6 7 8 9 10 11 12 |
|