algorithme de Needleman-Wunsch

L'algorithme de Needleman-Wunsch est un algorithme qui effectue un alignement global maximal de deux chaînes de caractères. Il est couramment utilisé en bio-informatique pour aligner des séquences de protéines ou de nucléotides. L'algorithme a été présenté en 1970 par et dans leur article A general method applicable to the search for similarities in the amino acid sequence of two proteins. L'algorithme de Needleman-Wunsch est un exemple de programmation dynamique, tout comme l'algorithme de Wagner et Fischer pour le calcul de la distance de Levenshtein auquel il est apparenté. Il garantit de trouver l'alignement de score maximal. Ce fut la première application de la programmation dynamique pour la comparaison de séquences biologiques. Les scores pour les caractères alignés sont spécifiés par une matrice de similarité. Ici, est la similarité des caractères i et j. Elle utilise une 'pénalité de trou', appelée ici d.