Given sequence S and T, find a sequence X and Y such that S and T belong to the shuffle of X and Y. (X and Y may not exist)

user_12247844 0
Viewed 502

I have to make a dynamic programming algorithm that solve this problem : Given sequence S and T, find a sequence X and Y such that S and T belong to the shuffle of X and Y.

Sequence S and T are given with each having length n . We want to find a sequence X and a sequence Y each of length k an l such that S and T belong to the shuffle product of X and Y. Knowing that (k+l = n)

How to I go about solving this using dynamic programming. I'm interested in knowing what could be the policy for using past results. As of now I have no idea.

Can someone do an example with S = GTACA and T = AGCAT Let's assume that my table looks like this:

empty table

We want the green cell to provide sequence X and Y or provide nothing (In the case X and Y don't exist)

selection of past solutions

I have noticed that in many dynamic programming problems the past solution for building the current one is selected from either the cell at the left (red) or top (yellow) or diagonal (blue) of the current cell (outline in green). I still struggle to know how to select given my specific problem.

UPDATE

When I try to find the longest common subsequence as suggested by the answer below I get AGCA following this (from the wikipedia article suggested below.) from the wikipedia articles

My dynamic programming table looks like this: my table

If I made a mistake please tell me where so I can correct it.

dynamic-programming genetic-algorithm dynamic data-structures algorithm
1 Answers

This seems to be the Longest common subsequence problem in disguise: Given S and T you find the longest common subsequence. That would be X. The left out elements would be the sequence Y if they appear in the same order in S and T, or they indicate that no such X and Y exist if they don't appear in the same order.

In your example the longest common subsequence is ACA. Therefore X = ACA and the left out elements in S and T are GT, appearing in the same order in both. Consequently Y = GT.

EDIT: Your dynamic programming table is incorrect. For example in the 3rd row and 4th column the cell should have the two sequences A and G, not a single sequence AG. To quote from Wikipedia:

If they are not equal, then the longer of the two sequences [...] is retained. (If they are the same length, but not identical, then both are retained.)

Here is the full table (sans empty sequences):

  | G   T    A       C             A
-------------------------------------------
A |          A       A             A
G | G   G    A,G     A,G           A,G 
C | G   G    A,G     AC,GC         AC,GC
A | G   G    GA      AC,GA,GC      ACA,GCA
T | G   GT   GA,GT   AC,GA,GC,GT   ACA,GCA

This gives us two solutions for X, but only one of them gives us a valid Y:

  • If X = ACA then Y = GT based on both S and T -- valid solution.
  • If X = GCA then Y = TA based on S but AT based on T -- so this is not a solution.

I acknowledge that the above answer is not a complete solution to the problem. By the reasoning I gave in my comment below it follows only that X or Y are subsequences of the LCS. What subsequence is that still needs to be somehow determined.

user_2771760
Related