Answers.Body: <p>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.</p>
  <blockquote>
  <p>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.</p>
  </blockquote>
  <p><a href="https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-28T20:08:21.377Z
Answers.LastActivityDate: 2021-09-28T20:08:21.377Z
Answers.UserDisplayName: Bioathlete
Body: <p>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)?</p>
  <p>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.</p>
  
Tags: <phylogenetics><algorithms>
Title: Given two ADN sequence, can there be multiple optimal alignement? And how to optimally find them?
ThreadText: # Given two ADN sequence, can there be multiple optimal alignement? And how to optimally find them?
  
  (Asked by: username_0 on 2021-09-27)
  
  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.
  
  **Tags:** phylogenetics, algorithms
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-09-28. Score: 1
  
  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>
  
  
  ---
  
  