PL 
EnglishDomyślny
Українська🧬 Najdłuższy wspólny podciąg — dopasowanie DP
Wyznacz najdłuższy wspólny podciąg dwóch napisów za pomocą tablicy programowania dynamicznego, a potem prześledź dopasowania po przekątnej — to algorytm stojący za narzędziami diff i porównywaniem sekwencji DNA.
O najdłuższym wspólnym podciągu (LCS)
Problem najdłuższego wspólnego podciągu (LCS) znajduje najdłuższą sekwencję znaków (niekoniecznie ciągłą), która pojawia się w tej samej względnej kolejności w obu ciągach wejściowych. Jest rozwiązywany w czasie i pamięci O(mn) za pomocą programowania dynamicznego: tabela L[i][j] przechowuje długość LCS pierwszych i znaków ciągu A i pierwszych j znaków ciągu B, z rekurencją L[i][j] = L[i−1][j−1] + 1, jeśli A[i]=B[j], w przeciwnym razie max(L[i−1][j], L[i][j−1]). LCS stanowi podstawę uniksowego narzędzia diff, dopasowywania sekwencji DNA oraz narzędzi wykrywania plagiatów, gdzie identyfikuje maksymalną wspólną strukturę między dwoma dokumentami lub genomami.
Ta symulacja wypełnia tabelę PD komórka po komórce, a następnie śledzi wstecz, by podświetlić wszystkie optymalne ścieżki dopasowania przez macierz. Możesz też zobaczyć, jak LCS wiąże się z odległością edycyjną: minimalna liczba wstawień i usunięć potrzebnych do przekształcenia A w B równa się (|A| + |B| − 2·LCS(A, B)), czyniąc oba problemy dualnymi spojrzeniami na tę samą strukturę leżącą u podstaw.
Najczęściej zadawane pytania
Jaka jest relacja rekurencyjna dla LCS?
L[i][j] = 0, jeśli i=0 lub j=0 (przypadek bazowy pustego ciągu); L[i][j] = L[i−1][j−1] + 1, jeśli A[i] = B[j] (znaki się zgadzają, przedłuż LCS); L[i][j] = max(L[i−1][j], L[i][j−1]) w przeciwnym razie (weź lepszą opcję pominięcia jednego znaku z któregokolwiek ciągu). Wsteczne śledzenie od L[m][n], podążające ruchami po przekątnej (dopasowanie) i kierunkiem maksimum, odzyskuje faktyczny ciąg LCS.
Czy LCS jest unikalny?
Nie — może istnieć wiele LCS tej samej maksymalnej długości. Na przykład LCS("ABCB", "BDCAB") ma długość 3, przy czym zarówno „BCB”, jak i „BCA” są ważnymi najdłuższymi wspólnymi podciągami. Liczba odrębnych LCS może być wykładnicza względem długości ciągów w najgorszym przypadku. Wsteczne śledzenie przez tabelę PD może dać dowolny z nich; wyliczenie wszystkich wymaga dodatkowej księgowości.
Jak LCS wiąże się z odległością edycyjną?
Gdy dozwolone są tylko wstawienia i usunięcia (bez podstawień), odległość_edycyjna(A, B) = |A| + |B| − 2·LCS(A, B). Każdy dopasowany znak w LCS unika jednego usunięcia i jednego wstawienia, oszczędzając 2 operacje. Odległość Levenshteina dodaje podstawienia jako opcjonalny skrót (koszt 1 zamiast usuń+wstaw = koszt 2). Obie tabele PD są strukturalnie identyczne, różniąc się jedynie sposobem obliczania komórki diagonalnej (niezgodności).
Czym jest algorytm Hunta-Szymanskiego dla rzadkiego LCS?
Dla sekwencji z niewieloma dopasowanymi parami (rzadkie zbiory dopasowań) algorytm Hunta-Szymanskiego znajduje LCS w czasie O((r + n) log n), gdzie r to liczba pozycji dopasowań. Najpierw wylicza wszystkie pary (i, j), gdzie A[i]=B[j], a następnie znajduje najdłuższy rosnący łańcuch w tych parach według współrzędnej y — równoważne problemowi najdłuższego rosnącego podciągu. Jest to znacznie szybsze niż O(mn), gdy alfabet jest duży lub sekwencje mają niewiele wspólnych znaków.
Czy LCS można obliczyć szybciej niż O(mn)?
Dla ogólnych sekwencji nad dowolnym alfabetem najlepsze znane algorytmy działają w O(mn/log n), wykorzystując równoległość na poziomie słowa (metody wektorów bitowych). Dla małych alfabetów metoda czterech Rosjan osiąga O(mn/log2 n). Dla losowych ciągów nad alfabetem o rozmiarze k oczekiwana długość LCS wynosi w przybliżeniu γ·n, gdzie γ zależy od k (np. γ ≈ 0,8 dla binarnego), a algorytmy wykorzystujące tę strukturę mogą być szybsze w praktyce.
Jak polecenie diff w Uniksie wykorzystuje LCS?
Uniksowe diff oblicza LCS dwóch plików traktowanych jako sekwencje linii. Linie w LCS są „niezmienione”; linie w pliku A, ale nieobecne w LCS, są „usunięte” (oznaczone −); linie w pliku B, ale nieobecne w LCS, są „dodane” (oznaczone +). Wynikiem jest minimalny skrypt edycji przekształcający jeden plik w drugi. Algorytm diff Gita (patience diff, histogram diff) używa wariantów LCS z heurystykami, by tworzyć bardziej czytelne dla człowieka porównania typowego kodu źródłowego.
Czym jest problem najdłuższego wspólnego podciągu ciągłego i czym różni się od LCS?
Najdłuższy wspólny podciąg ciągły (nie podsekwencja) wymaga, by dopasowane znaki były ciągłe w obu ciągach. Jest rozwiązywany w czasie O(mn) za pomocą tabeli PD, gdzie L[i][j] = L[i−1][j−1]+1, jeśli A[i]=B[j], w przeciwnym razie 0, a odpowiedzią jest max(L[i][j]). Bardziej efektywnie, uogólnione drzewo sufiksowe rozwiązuje to w czasie O(m+n). LCS ≥ długość najdłuższego wspólnego podciągu ciągłego ogólnie, ponieważ podsekwencje są bardziej elastyczne.
Jak LCS jest stosowany w bioinformatyce?
W dopasowywaniu sekwencji DNA lub białek LCS identyfikuje zachowane regiony między dwoma genomami lub sekwencjami białkowymi. Algorytm Needlemana-Wunscha (dopasowanie globalne) jest matematycznie równoważny LCS z konfigurowalnymi wynikami dopasowań i karami za przerwy. Identyfikacja zachowanych domen podobnych do LCS między genomami człowieka i myszy ujawnia funkcjonalnie ważne regiony podlegające presji ewolucyjnej, kierując adnotacją genów i odkrywaniem celów leków.
Jaki jest związek między LCS a najdłuższym rosnącym podciągiem?
LCS można zredukować do problemu najdłuższego rosnącego podciągu (LIS): zastąp każdy znak w A jego rangą wśród dopasowań w B, a następnie znajdź LIS wynikowej sekwencji pozycji. Odwrotnie, LIS można rozwiązać w czasie O(n log n) za pomocą sortowania cierpliwościowego. Algorytm rzadkiego LCS Hunta-Szymanskiego wykorzystuje dokładnie tę redukcję, dając O(r log n) dla rzadkich zbiorów dopasowań, gdzie r to liczba dopasowanych par.
Ile pamięci wymaga LCS i czy można ją zredukować?
Standardowe PD używa pamięci O(mn) dla pełnej tabeli. Algorytm Hirschberga (1975) oblicza LCS w czasie O(mn), ale tylko przy pamięci O(min(m,n)), używając metody dziel i zwyciężaj: dzieli problem w wierszu środkowym, znajduje, gdzie optymalna ścieżka LCS przecina ten wiersz, używając pamięci liniowej, a następnie rekurencyjnie przetwarza obie połowy. To ta sama technika używana w optymalnym pod względem pamięci dopasowywaniu sekwencji w bioinformatyce.