Rosalind - Finding a Shared Spliced Motif

Sep 8, 2019 rosalind

Problem:

Please find the problem here.

Solution:

This is the classic longest common subsequence problem, it can be solved using the Levenshtein edit distance algorithm.

If we disallow replacing characters, then the edit can be visualized as an alignment of two strings as follow:

A		A	C	C	T		T	G	G
A	C	A	C		T	G	T	G		A

When the first string has a gap, this is an insertion operation. When the second string has a gap, this is a deletion operation.

To find the longest common subsequence is the same as trying the minimize the total gap length.

Code: