Shortest common supersequence: Difference between revisions
Content added Content deleted
(use of the longest common subsequence as an external function is allowed) |
m (minor rewording: find it) |
||
| Line 2: | Line 2: | ||
The '''[[wp:shortest common supersequence|shortest common supersequence]]''' is a problem closely related to the [[longest common subsequence]], which you can use as an external function for this task. |
The '''[[wp:shortest common supersequence|shortest common supersequence]]''' is a problem closely related to the [[longest common subsequence]], which you can use as an external function for this task. |
||
Given two strings u and v, the shortest |
Given two strings u and v, find the shortest possible sequence s, which is the shortest common supersequence of u and v where both u and v are a subsequence of s. |
||
As an example, |
As an example, for the strings 'AACCTTGG' and 'ACACTGTGA' and you should get 'AACTGG'. Sometimes several solutions are possible, though they should all have the same length by definition. This example is taken from a [http://rosalind.info/problems/lcsq/ rosalind task]. |
||
Revision as of 07:06, 31 March 2013
Shortest common supersequence is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
The shortest common supersequence is a problem closely related to the longest common subsequence, which you can use as an external function for this task.
Given two strings u and v, find the shortest possible sequence s, which is the shortest common supersequence of u and v where both u and v are a subsequence of s.
As an example, for the strings 'AACCTTGG' and 'ACACTGTGA' and you should get 'AACTGG'. Sometimes several solutions are possible, though they should all have the same length by definition. This example is taken from a rosalind task.