Jan. 4, 2013, 5:44 p.m. by Rosalind Team
Topics: Dynamic Programming, String Algorithms
Two Motifs, One Gene
Recall that in “Finding a Shared Spliced Motif”, we found the longest motif that could have been shared by two genetic strings, allowing for the motif to be split onto multiple exons in the process. As a result, we needed to find a longest common subsequence of the two strings (which extended the problem of finding a longest common substring from “Finding a Shared Motif”).
In this problem, we consider an inverse problem of sorts in which we are given two different motifs and we wish to interleave them together in such a way as to produce a shortest possible genetic string in which both motifs occur as subsequences.
A string
A common supersequence of strings
Given: Two DNA strings
Return: A shortest common supersequence of
ATCTGAT TGCATA
ATGCATGAT