Porównywarka sekwencji kwasów nukleinowych

Algorytm Needleman-Wunsch

Algorytm Needleman-Wunsch jest klasyczną metodą używaną do porównywania dwóch sekwencji DNA, RNA lub białek. Jego głównym celem jest zidentyfikowanie optymalnego dopasowania globalnego między dwiema sekwencjami.

Charakterystyki i parametry algorytmu w tym skrypcie:

  1. Cel: Znalezienie optymalnego globalnego dopasowania między dwiema sekwencjami.
  2. Macierz Wyników: Jest to dwuwymiarowa tablica (macierz), w której każda komórka (i, j) reprezentuje najlepszy wynik dopasowania dla podsekwencji s1[0:i] i s2[0:j].
  3. Wartości początkowe: Pierwszy wiersz i pierwsza kolumna są inicjowane wartościami opartymi na karze za przerwę (gap penalty).
  4. Kary i nagrody:
    • Kary za przerwę (gap): -1
    • Kara za niezgodność (mismatch): -1
    • Nagroda za dopasowanie (match): 2
  5. Funkcja Skoringowa: Dla każdej komórki (i, j) w macierzy wyników:
    • Jeśli s1[i] dopasowuje się do s2[j], dodaje się nagrodę za dopasowanie.
    • W przeciwnym razie dodaje się karę za niezgodność.
    • Wartość komórki jest maksimum z trzech możliwych wartości: dopasowanie/mismatch z przekątną, przerwa z lewej strony i przerwa z góry.
  6. Śledzenie Ścieżki: Po wypełnieniu całej macierzy wyników algorytm zaczyna od prawego dolnego rogu i idzie w kierunku lewego górnego rogu, identyfikując optymalną ścieżkę na podstawie wartości w sąsiednich komórkach.
  7. Wynik: Dwie sekwencje wynikowe z maksymalnym dopasowaniem globalnym.