Needleman-Wunsch-algoritmus

Magyar

Kiejtés

• IPA: [ ˈnɛɛdlɛmɒɱvunʃhɒlɡoritmuʃ]

Főnév

Needleman-Wunsch-algoritmus

1. (matematika)

Needleman-Wunsch-algoritmus

A **Needleman-Wunsch-algoritmus** egy dinamikus programozási módszer, amelyet két szekvencia (például DNS, fehérjék vagy általános karakterláncok) globális illesztésére fejlesztettek ki. A cél az, hogy a két szekvencia közötti optimális igazítást találjuk meg, figyelembe véve illesztési pontokat, szakadékokat (gap-eket) és helyettesítési költségeket.

Fő jellemzők

1. Bemenet:

  - Két szekvencia: $A$ és $B$.
  - Hasonlósági vagy helyettesítési mátrix ($S$).
  - Szakadék (gap) költség ($g$).

1. Kimenet:

  - Az optimális globális illesztés $A'$ és $B'$, ahol az illesztés pontszáma maximális.

1. Kulcslépések:

  - Dinamikus programozási táblázat létrehozása az optimális pontszám kiszámítására.
  - Az optimális út visszafejtése az illesztés rekonstrukciójához.

1. Időbonyolultság:

  - $O(mn)$, ahol $m$ és $n$ a két szekvencia hossza.

Algoritmus lépései

1. Pontszámtábla inicializálása

• Hozz létre egy $(m+1)\times (n+1)$ méretű táblát, ahol $m$ és $n$ a szekvenciák hossza.
• Töltsd ki az első sort és oszlopot a szakadékköltségek halmozásával:

$$F(i,0)=i\cdot g\quad {\text{és}}\quad F(0,j)=j\cdot g.$$

2. Pontszámítás

• Minden $F(i,j)$ cella a következő szabály alapján töltődik ki:

$$F(i,j)=\max {\begin{cases}F(i-1,j-1)+S(A[i],B[j]),&{\text{(illesztés vagy helyettesítés)}}\\F(i-1,j)+g,&{\text{(felülről szakadék)}}\\F(i,j-1)+g,&{\text{(balról szakadék)}}.\end{cases}}$$

3. Illesztés visszafejtése

• Kezdj az $F(m,n)$-nél, és haladj visszafelé a táblán:

 - Ha $F(i,j)=F(i-1,j-1)+S(A[i],B[j])$, akkor $A[i]$ és $B[j]$ illeszkedik.
 - Ha $F(i,j)=F(i-1,j)+g$, akkor $A[i]$ gap-et kap.
 - Ha $F(i,j)=F(i,j-1)+g$, akkor $B[j]$ gap-et kap.

Python Implementáció

import numpy as np

def needleman_wunsch(seq1, seq2, match=1, mismatch=-1, gap=-2):
    """
    Needleman-Wunsch algoritmus implementációja.
    """
    m, n = len(seq1), len(seq2)
    score = np.zeros((m+1, n+1), dtype=int)

    for i in range(1, m+1):
        score[i][0] = i * gap
    for j in range(1, n+1):
        score[0][j] = j * gap

    for i in range(1, m+1):
        for j in range(1, n+1):
            match_mismatch = score[i-1][j-1] + (match if seq1[i-1] == seq2[j-1] else mismatch)
            insert = score[i-1][j] + gap
            delete = score[i][j-1] + gap
            score[i][j] = max(match_mismatch, insert, delete)

    aligned_seq1, aligned_seq2 = "", ""
    i, j = m, n
    while i > 0 and j > 0:
        current_score = score[i][j]
        if current_score == score[i-1][j-1] + (match if seq1[i-1] == seq2[j-1] else mismatch):
            aligned_seq1 = seq1[i-1] + aligned_seq1
            aligned_seq2 = seq2[j-1] + aligned_seq2
            i -= 1
            j -= 1
        elif current_score == score[i-1][j] + gap:
            aligned_seq1 = seq1[i-1] + aligned_seq1
            aligned_seq2 = "-" + aligned_seq2
            i -= 1
        else:
            aligned_seq1 = "-" + aligned_seq1
            aligned_seq2 = seq2[j-1] + aligned_seq2
            j -= 1

    while i > 0:
        aligned_seq1 = seq1[i-1] + aligned_seq1
        aligned_seq2 = "-" + aligned_seq2
        i -= 1
    while j > 0:
        aligned_seq1 = "-" + aligned_seq1
        aligned_seq2 = seq2[j-1] + aligned_seq2
        j -= 1

    return score[m][n], aligned_seq1, aligned_seq2

seq1 = "GATTACA"
seq2 = "GCATGCU"
score, aligned_seq1, aligned_seq2 = needleman_wunsch(seq1, seq2)
print(f"Pontszám: {score}")
print(f"Illesztett szekvenciák:\n{aligned_seq1}\n{aligned_seq2}")

C++ Implementáció

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int needlemanWunsch(const string& seq1, const string& seq2, int match, int mismatch, int gap, string& alignedSeq1, string& alignedSeq2) {
    int m = seq1.size(), n = seq2.size();
    vector<vector<int>> score(m + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; i++) score[i][0] = i * gap;
    for (int j = 1; j <= n; j++) score[0][j] = j * gap;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int matchMismatch = score[i-1][j-1] + (seq1[i-1] == seq2[j-1] ? match : mismatch);
            int insert = score[i-1][j] + gap;
            int delete_ = score[i][j-1] + gap;
            score[i][j] = max({matchMismatch, insert, delete_});
        }
    }

    int i = m, j = n;
    alignedSeq1 = "";
    alignedSeq2 = "";
    while (i > 0 && j > 0) {
        if (score[i][j] == score[i-1][j-1] + (seq1[i-1] == seq2[j-1] ? match : mismatch)) {
            alignedSeq1 = seq1[i-1] + alignedSeq1;
            alignedSeq2 = seq2[j-1] + alignedSeq2;
            i--; j--;
        } else if (score[i][j] == score[i-1][j] + gap) {
            alignedSeq1 = seq1[i-1] + alignedSeq1;
            alignedSeq2 = "-" + alignedSeq2;
            i--;
        } else {
            alignedSeq1 = "-" + alignedSeq1;
            alignedSeq2 = seq2[j-1] + alignedSeq2;
            j--;
        }
    }

    while (i > 0) {
        alignedSeq1 = seq1[i-1] + alignedSeq1;
        alignedSeq2 = "-" + alignedSeq2;
        i--;
    }
    while (j > 0) {
        alignedSeq1 = "-" + alignedSeq1;
        alignedSeq2 = seq2[j-1] + alignedSeq2;
        j--;
    }

    return score[m][n];
}

int main() {
    string seq1 = "GATTACA";
    string seq2 = "GCATGCU";
    string alignedSeq1, alignedSeq2;

    int score = needlemanWunsch(seq1, seq2, 1, -1, -2, alignedSeq1, alignedSeq2);

    cout << "Pontszám: " << score << endl;
    cout << "Illesztett szekvenciák:\n" << alignedSeq1 << "\n" << alignedSeq2 << endl;

    return 0;
}

Alkalmazások

1. Bioinformatika: DNS, RNS és fehérjeszekvenciák illesztése.
2. Szövegfeldolgozás: Szerkesztési távolság számítása.
3. Verziókezelő rendszerek: Különbségek azonosítása fájlok között.

Fordítások

Tartalom

angol: Needleman–Wunsch algorithm (en)

További információk

• Needleman-Wunsch-algoritmus - Értelmező szótár (MEK)
• Needleman-Wunsch-algoritmus - Etimológiai szótár (UMIL)
• Needleman-Wunsch-algoritmus - Szótár.net (hu-hu)
• Needleman-Wunsch-algoritmus - DeepL (hu-de)
• Needleman-Wunsch-algoritmus - Яндекс (hu-ru)
• Needleman-Wunsch-algoritmus - Google (hu-en)
• Needleman-Wunsch-algoritmus - Helyesírási szótár (MTA)
• Needleman-Wunsch-algoritmus - Wikidata
• Needleman-Wunsch-algoritmus - Wikipédia (magyar)