Similarity between DNA Sequences
DNA sequences (genes) can be represented as sequences of four letters ACGT, corresponding to the four submolecules forming DNA. When biologists find a new sequence, they typically want to know what other sequences it is most similar to. One way of computing how similar two sequences are is to find the longest DNA sequence which is a subsequence of both sequences.
You are to find the longest DNA sequence which is both a subsequence of two given sequences. A subsequence of some sequence is a new sequence which is formed from the original sequence by deleting some of the elements without disturbing the relative positions of the remaining elements. In some cases, the result will be the empty string. When there are more than one longest subsequence, you may break ties by selecting the one more close to the left on the first DNA sequence.
The input has two lines, each containing a DNA sequence (maximum 64 characters each).
The first two lines of the output contain the original ADN sequences given in the input. The third line contains the statement "Longest common sequence:" and, finally, the last line contains the longest common sequence between the two given DNA sequences. If there are no common subsequences, this fourth line is not written.
Sample Input 1
Sample Output 1
ACGGTGTCGTG CGTTCGGCTA Longest common sequence: CGTTCGT
Sample Input 2
Sample Output 2
ATGC CGTA Longest common sequence: A