Asked by abdulla elmourcy
on 8 Aug 2018

nwalign function calculates the minimum edit distance between two sequences to be like each other by calculating every possible alignment and choose the one with minimum modifications can I make matlab present these all possible alignment he did as I need to choose the one with maximum value

Answer by Stephen Cobeldick
on 8 Aug 2018

Edited by Stephen Cobeldick
on 8 Aug 2018

The *maximum* edit distance between any two strings (even two identical ones) is *infinity*, unless you add some kind of restrictions on repetitions of edits. Even then you can create an arbitrarily large edit distance, with any arbitrarily large set character set. So unless you have some other restrictions the *maximum* edit distance is not likely to be very useful.

The *minimum* edit distance can easily be calculated using the Wagner–Fischer algorithm:

>> C = {'live','eve','believe','belive'}; >> cellfun(@(c)wfEdits(c,'beleive'),C) ans = 3 4 2 1

Thus showing that 'belive' is the closest to 'beleive'. The function is:

function d = wfEdits(S1,S2) % Wagner–Fischer algorithm to calculate the edit distance / Levenshtein distance. % N1 = 1+numel(S1); N2 = 1+numel(S2); % D = zeros(N1,N2); D(:,1) = 0:N1-1; D(1,:) = 0:N2-1; % for r = 2:N1 for c = 2:N2 D(r,c) = min([D(r-1,c)+1, D(r,c-1)+1, D(r-1,c-1)+~strcmpi(S1(r-1),S2(c-1))]); end end d = D(end); % end

If you are interested in the different possible *direct* edit paths (i.e. without repetition or unnecessary diversion to other characters) then you should investigate the Needleman–Wunsch algorithm.

abdulla elmourcy
on 13 Aug 2018

abdulla elmourcy
on 13 Aug 2018

Stephen Cobeldick
on 13 Aug 2018

*"In my situation I need the opposite, I need to choose from these suggests the answer with the highest edit number."*

You need to be more specific than this, because currently this could be solved by several different interpretations. Are intermediate characters allowed (e.g. 'a' -> 'b' -> 'c')? Can edits be repeatedly applied (i.e. 'a' -> 'b' -> 'a' etc.)? Even without any intermediate characters and no edit repetitions, this still has a trivial solution:

- delete all of the first string
- add all of the second string

giving an edit distance of `numel(str1)+numel(str2)`. If that is not what you want then you need to define your problem better.

Perhaps the Needleman–Wunsch algorithm *might* do what you want, once to you adjust the scoring values to suit your problem requirements.

Clearly you will have to do some experimentation yourself, e.g. trying different scoring schemes, and learn up about this algorithm and how it works. Before using `nwalign` (or perhaps something from FEX) you could try this on one of the several online Needleman–Wunsch tools, which graphically show the path (these are easy to find with an internet search). Keep experimenting!

Sign in to comment.

Opportunities for recent engineering grads.

Apply Today
## 0 Comments

Sign in to comment.