1
$\begingroup$

Given two sequences, I know we can determine optimal alignment of sequence with the Needleman–Wunsch algorithm. But is it possible that two alignments have multiple optimal alignment (I guess it would mean that multiple alignement have the same score)?

And if possible, how would you find them via an algorithm? Just looking for a general idea on how to go about it, I can't see how you could do it beside by checking for all possible combinations.

$\endgroup$
1
$\begingroup$

As Needleman-Wunsch is a Dynamic Programming algorithm you do need to complete the entire matrix to find the optimal solution and it is possible to have multiple best alignments.

The algorithm assigns a score to every possible alignment, and the purpose of the algorithm is to find all possible alignments having the highest score.

https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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