I'm trying to work through some problems in this textbook in my spare time and I came across this very interesting problem that I'm unable to find a solution for. Can anyone suggest an efficient algorithm for this problem? Here's a link to the problem:
The scs link refers to lcs, which in turn describes a dynamic programming algorithm.
Given a=0110 and b=0101, we get an alignment:
a = 01-10
b = 0101-
lcs = 01 1
scs = 01010
The '-' denotes a "gap", a deletion -- this sequence lacks (has lost) what the other has at this position.
Alternatively, an insertion has occurred in the other sequence, i.e. it has an additional position.
(Bioinformatics' terminology; genes, mutation, evolution, common ancestor.)