Minimal edit distance between two circular lists?

Question

Given two circular lists, is there an efficient way to compute the optimal alignment between the two lists? For example, given circular lists:

a b b c b c a

the optimal alignment is

a b b c a b _ c

because this alignment has the smallest edit distance (note: this optimal alignment is not and need not be unique).

One way to do this is to compute the edit distance between the first list and each cyclic permutation of the second list, taking the minimum edit distance as the optimal alignment. Is there a more efficient way to do so?

songlj · Accepted Answer · 2013-01-14 07:00:03Z

3

suppose S1="abbc", S2="bca"

now let S2'=strcat(S2,S2)="bcabca", then compute edit distance between S1 and S2', you will get

--abbc- bcab-ca

just a hint, more details should be considered

answered Jan 14, 2013 at 7:00

songlj

9371 gold badge6 silver badges10 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

srubin Over a year ago

So, after strcat(,) to one of the strings, run something like Needleman-Wunsch? Seems promising.

Collectives™ on Stack Overflow

Minimal edit distance between two circular lists?

1 Answer 1

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Related