Longest Common Subsequence

Advanced Computational Biology Dynamic Programming Traceback Sequence Comparison Alignment
Significance:

A subsequence keeps order but allows gaps, which is exactly what happens to homologous
sequences over evolutionary time as insertions and deletions accumulate. The longest common subsequence
between two sequences is therefore a crude but informative measure of shared ancestry, and the traceback
that recovers the actual subsequence — rather than just its length — is the same procedure used to
recover an alignment from a Needleman-Wunsch matrix.

Statement

Given two DNA strings, find a longest common subsequence: the longest string that
appears in both as a subsequence, meaning its characters occur in order but not necessarily contiguously.

When several longest common subsequences exist, print the lexicographically smallest one.

Print the subsequence on one line. If the only common subsequence is empty, print an empty line.

Input — read from standard input
Variable Type Description
s1
line 1
 str The first DNA string
1 <= len(s1) <= 500, uppercase A, C, G, T only
s2
line 2
 str The second DNA string
1 <= len(s2) <= 500, uppercase A, C, G, T only

These variables are already read for you in the starter code on the right.

Output

str the lexicographically smallest longest common subsequence

Sample Cases
Sample 1
Input
AACCTTGG
ACACTGTGA
Expected Output
AACTGG
Several longest common subsequences exist; the lexicographically smallest is chosen.
Sample 2
Input
ACGT
ACGT
Expected Output
ACGT
The strings are identical, so the whole string is the answer.

Submit also runs your code against 4 hidden test cases. Hidden inputs are never shown — if one fails you'll get its number and a description of the mismatch, not the data.

Constraints
  • 1 <= length(s1), length(s2) <= 500
  • Both strings contain only uppercase A, C, G, T
  • Among all subsequences of maximum length, output the lexicographically smallest — this makes the
    answer unique and gradeable
  • An empty result prints as an empty line
Further Reading
  • Build the standard LCS length table first, then reconstruct.
  • To get the lexicographically smallest result, build the answer forward and prefer the smallest
    character that still allows a maximum-length completion.
  • A simpler route: compute the table, then at each step pick the smallest next character whose
    remaining LCS length still equals the required remainder.
My Notes
Log in to save personal notes.
Console output will appear here when you click Run Code or Submit...
Expected: s1 (str), s2 (str)
Next Problem
UPGMA Phylogenetic Tree