Needleman-Wunsch-algoritmus

• IPA:

Needleman-Wunsch-algoritmus

1. (matematika)

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.

1. Bemenet:

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

1. Kimenet:

  - Az optimális globális illesztés ${\displaystyle A'}$ és ${\displaystyle 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:

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

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

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

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

$${\displaystyle F(i,j)=\max {\begin{cases}F(i-1,j-1)+S(A,B),&{\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}}}$$

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

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

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 * gap
    for j in range(1, n+1):
        score = j * gap

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

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

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

    return score, 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}")

#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 * gap;
    for (int j = 1; j <= n; j++) score = j * gap;

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

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

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

    return score;
}

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;
}

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.

• 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)