Question: Finding suboptimal alignments
0
gravatar for trinityduke100
3 days ago by
trinityduke10010 wrote:

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

dna alignment sequencing • 61 views
ADD COMMENTlink modified 3 days ago by Mensur Dlakic9.0k • written 3 days ago by trinityduke10010

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

ADD REPLYlink modified 3 days ago • written 3 days ago by Pierre Lindenbaum134k

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

ADD REPLYlink written 3 days ago by trinityduke10010

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.

ADD REPLYlink written 3 days ago by Pierre Lindenbaum134k

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

ADD REPLYlink written 3 days ago by trinityduke10010
0
gravatar for Mensur Dlakic
3 days ago by
Mensur Dlakic9.0k
USA
Mensur Dlakic9.0k wrote:

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.

ADD COMMENTlink modified 3 days ago • written 3 days ago by Mensur Dlakic9.0k

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.

ADD REPLYlink written 2 days ago by trinityduke10010

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.

ADD REPLYlink written 2 days ago by Mensur Dlakic9.0k

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

ADD REPLYlink written 1 day ago by trinityduke10010
Please log in to add an answer.

Help
Access

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
Powered by Biostar version 2.3.0
Traffic: 1728 users visited in the last hour
_