Wikiszótár

Ruzzo-Tompa-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈruzːotompɒɒlɡoritmuʃ]

Főnév

Ruzzo-Tompa-algoritmus

  1. (matematika, algoritmusok)

A Ruzzo–Tompa algoritmus egy bioinformatikai algoritmus, amelyet maximálisan átfedő szegmensek (maximally overlapping substrings) azonosítására használnak genomikus szekvenciákban. Kifejezetten a maximális részegyező szegmensek (maximal scoring subsequences) megtalálására tervezték, ahol a szegmensek pontszámait a szekvencia egy adott súlyozási rendszer alapján határozzák meg.

Ez az algoritmus hatékony megoldást nyújt a problémára, ahol egy szekvencia legnagyobb értékű részhalmazát szeretnénk azonosítani oly módon, hogy az egymással átfedésben lévő szakaszok pontszámai ne haladják meg egy bizonyos küszöbértéket.


Probléma definiálása

Adott egy szekvencia ( S ), amely egy pontszámokból álló sorozat, és célunk az összes olyan részszekvencia meghatározása, amelyek: 1. Maximális pontszámmal rendelkeznek. 2. Nem tartalmaznak negatív pontszámot (ha egy szakasz összpontszáma negatív, azt figyelmen kívül hagyjuk).

Fő lépések:

  • A pontozási szekvencia minden lehetséges részszakaszának kiszámítása.
  • Csak azok a szakaszok kerülnek kiválasztásra, amelyek összértéke pozitív.
  • A maximálisan átfedő szakaszok kerülnek előtérbe.


Ruzzo–Tompa algoritmus pszeudokód

function RuzzoTompa(scores):
    result = []  # Az összes maximális szakasz tárolására
    n = scores hossza
    current_start = 0
    current_sum = 0

    for i = 0-tól n-1-ig:
        current_sum += scores[i]
        if current_sum < 0:
            # Negatív szakasz esetén reset
            current_start = i + 1
            current_sum = 0
        else:
            # Tároljuk a szakaszt, ha az értéke pozitív
            result.append((current_start, i, current_sum))

    Térj vissza a result szakaszokkal

Python implementáció

def ruzzo_tompa(scores):
    n = len(scores)
    result = []
    current_start = 0
    current_sum = 0

    for i in range(n):
        current_sum += scores[i]
        if current_sum < 0:
            # Ha az aktuális szakasz negatívba fordul, kezdjük újra
            current_start = i + 1
            current_sum = 0
        else:
            # Maximális szakasz rögzítése
            result.append((current_start, i, current_sum))

    return result


# Példa használat
scores = [2, -1, 3, -4, 5, 1, -3, 4, -2]
result = ruzzo_tompa(scores)
print("Maximális szakaszok:")
for start, end, total in result:
    print(f"Kezdet: {start}, Vége: {end}, Összeg: {total}")

Példa bemenet és kimenet

Bemenet: [2, -1, 3, -4, 5, 1, -3, 4, -2]
Kimenet: 

Maximális szakaszok:
Kezdet: 0, Vége: 2, Összeg: 4
Kezdet: 4, Vége: 5, Összeg: 6
Kezdet: 7, Vége: 7, Összeg: 4

C++ implementáció

#include <iostream>
#include <vector>
#include <tuple>

using namespace std;

vector<tuple<int, int, int>> ruzzoTompa(const vector<int>& scores) {
    vector<tuple<int, int, int>> result;
    int n = scores.size();
    int current_start = 0;
    int current_sum = 0;

    for (int i = 0; i < n; ++i) {
        current_sum += scores[i];
        if (current_sum < 0) {
            // Ha negatív szakaszba fordul, kezdjük újra
            current_start = i + 1;
            current_sum = 0;
        } else {
            // Maximális szakasz rögzítése
            result.emplace_back(current_start, i, current_sum);
        }
    }

    return result;
}

int main() {
    vector<int> scores = {2, -1, 3, -4, 5, 1, -3, 4, -2};
    auto result = ruzzoTompa(scores);

    cout << "Maximális szakaszok:" << endl;
    for (const auto& [start, end, total] : result) {
        cout << "Kezdet: " << start << ", Vége: " << end << ", Összeg: " << total << endl;
    }

    return 0;
}

Összegzés

A Ruzzo-Tompa algoritmus fő erőssége, hogy hatékonyan azonosítja a maximális értékű részszekvenciákat. Az algoritmus időbonyolultsága (O(n)), mivel a szekvencián csak egyszer iterál végig. Ez különösen hasznos, ha nagy genomikus szekvenciák vagy nagy méretű adatfolyamok feldolgozásáról van szó.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Ruzzo-Tompa-algoritmus&oldid=3480155”