I'm trying to align a sequence of characters together, I found that sequence alignment algorithms which use dynamic programming like Needleman-Wunsch or Smith–Waterman only align one character with one character beside allowing character substitution, deletion or insertion.

For example, if I have a set of similarly sounding characters, like

monir, monier, muneer, munir, mounir, mouneer

The alignment algorithm will produce the following output

m u n i - r
| | | |   |
m o n e e r

Is there a way to adapt these algorithms (or an alternative algorithm) to consider aligning/substituting character with more than one character in order to output something like

m u n i  r
| | | |  |
m o n ee r

Please note that, I'm using the standard java implementation for these algorithms and I don't have a predefined list of similarly sounding characters, so I'm trying to aligning the similar words together in order to extract these alignments.

  • 1
    $\begingroup$ Why don't you just merge gaps into neighbouring mismatches? $\endgroup$
    – Raphael
    Apr 24, 2015 at 14:01
  • $\begingroup$ @Raphael the algorithm compare character by character to get the score of matching the characters and the gaps should not be always applicable to be matched with its neighbors $\endgroup$
    – vanilla
    Apr 24, 2015 at 20:20
  • $\begingroup$ Why not? When will it be? $\endgroup$
    – Raphael
    Apr 24, 2015 at 20:38
  • $\begingroup$ @Raphael consider these strings, how can you do that? The normal alignment will produce: (- a l s h o u a - i b i / e - l s h - - a e e b y) but actually, I need it to be aligned like (a l sh ou a i b i / e l sh - a ee b y) $\endgroup$
    – vanilla
    Apr 24, 2015 at 21:30
  • $\begingroup$ You will have to make up your mind. In the question you say that the alignments are supposed to yield (candidates for) similar-sounding (groups of) characters. Now you talk of how things "need" to be. $\endgroup$
    – Raphael
    May 4, 2015 at 8:38

2 Answers 2


You can do this with a variant of the Smith-Waterman algorithm. It assigns a penalty for an insertion or deletion, and also assigns a penalty for a substition, that depends on the two letters. (This is used for calculating the similarity of protein sequences, e.g. with a lower penalty for replacing an acidic residue with another acidic one.)

For your case, the penalty score needs to depend on the previous context, so you will have to adapt a standard implementation.


If I understood your problem correctly, a trie data structure may help you. The main challenge would be after the first mismatch, match the upcomming characters. I'm not sure how I would hack it, but it may not be that hard.

Hope it helps. Regards

  • 1
    $\begingroup$ Welcome to Computer Science! Thanks for contributing but this is far too vague for an answer. You're basically saying, "Tries might work but they might not. And maybe they're really hard to use for this. I dunno, really." That would be OK for a comment but it's not an answer. $\endgroup$ May 2, 2015 at 16:09
  • $\begingroup$ Since you cannot comment yet, one possibility is to flesh out what you said, provided it is correct. $\endgroup$
    – babou
    May 2, 2015 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.