Finding suboptimal alignments

Question

[trinityduke100]

I have been trying to find an efficient way to find the suboptimal alignments given two sequences.

I understand that we can use Needleman-Wunsch algorithm to find optimal alignments but what about suboptimal alignments?

Is there a way to find suboptimal alignments?

Could we use forward algorithm to find suboptimal alignments?

Lets say we have the following two sequences

AAGTC AGGTC

[Pierre Lindenbaum]

I understand that we can use Needleman-Wunsch algorithm to find optimal alignments but what about suboptimal alignments?

https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm

[trinityduke100]

But what I understand is that Smith-Waterman algorithm is for local alignment and not for global alignment?

[Pierre Lindenbaum]

ah ok, I misunderstood your question. For a global alignement, when back-scanning the matrix, you can explore the alternate ways to build the best alignment instead of following the 'best' path.

[trinityduke100]

But given that there are exponentially large number of possible alignments, isn't there any efficient alternative?

Answer 1

[Mensur Dlakic]

You have already asked a variant of this question here, and I thought you got a good number of responses. I don't know why exactly you would need all or most sub-optimal alignments, but this I do know - most people are interested only in optimal alignments. That's why there are efficient algorithms for optimal alignments, and I am guessing not so for suboptimal alignments.

I already suggested to you here a small program for global alignments, which is short and I think easy to understand. If you know how to modify the code, it should be easily adaptable to get what you want. Frankly, I don't think you will find a ready solution that outputs sub-optimal alignment because that's not a goal of either alignment or sequence search programs. They do create all the alignments as part of the process, but they do not report sub-optimal alignment because in most cases they are not needed.

[trinityduke100]

I completely understand you but I am testing a mathematical model of a noisy channel. For which I need the probability of the suboptimal alignments occurring.

Is there any other (efficient) way to find the suboptimal alignments? One method that was suggested was to use forward backward algorithm, but I cannot understand how this will help in finding the suboptimal alignments.

[Mensur Dlakic]

I would prefer not to state the obvious, but you keep asking the same question. I have answered it to the best of my ability, most recently (and most obviously) in the second paragraph above.

Frankly, I don't think you will find a ready solution that outputs sub-optimal alignment because that's not a goal of either alignment or sequence search programs.

[trinityduke100]

No worries. Thank you very much and apologies for repeatedly asking the same thing.