O dopasowaniach sekwencji...

...zostało powiedziane i napisane już bardzo wiele. Uważam jednak, że Wikipedia absolutnie nie wyczerpuje tematu więc postanowiłem napisać coś od siebie. Chciałem się skupić na bardziej technicznym opisie dopasowań globalnych i lokalnych.

O co tu właściwie chodzi?
Formalnie globalne dopasowanie dwóch ciągów s1 i s2 nad alfabetem (czyli zbiorem znaków z których powstały) S polega na znalezieniu dwóch odpowiadających im ciągów d1 i d2 nad alfabetem S∪{-} spełniających trzy warunki:

1. s1 otrzymuje się z d1 poprzez usunięcie wszystkich znaków - (znaków przerwy), analogicznie dla s2 i d2, itd.
   
2. długość d1 jest równa długości d2
3. nie może być takiej sytuacji, w której d1 i d2 na tych samych pozycjach jednocześnie mają znaki przerwy

Tyle teorii, co to oznacza w rzeczywistości?
Weźmy na przykład s1=ACTGGCA i s2=ACTTGACG, których alfabet S={A,C,G,T}. Naszym zadaniem jest znalezienie odpowiadającej im pary d1 i d2 nad alfabetem S'={A,C,G,T,-} gdzie '-' to znak przerwy. Tworząc globalne dopasowanie s1 i s2 otrzymujemy: d1=ACT-GGCA oraz d2=ACTTGACG (istnieje też drugi wariant: d1'=AC-TGGCA i d2'=ACTTGACG).

Fajnie, ale co z tego wynika i czemu znak przerwy jest akurat na czwartej (lub trzeciej w drugim wariancie) pozycji w d1, a nie np. na drugiej i czwartej w d1 oraz trzeciej w d2?
Sprawdźmy to, niech więc tymczasowo d1 i d2 będą równe:
d1=A-C-TGGCA
   |   || |
d2=AC-TTGACG
okazuje się, że liczba pionowych kresek, czyli "stopień uliniowienia" jest równy 4, co więcej nie jest to maksymalna możliwa liczba. Takich różnych kombinacji można znaleźć wiele (liczba dopasowań dla danych ciągów rośnie wykładniczo wraz z rozmiarem). Optymalne globalne dopasowanie (zazwyczaj właśnie na tym nam zależy), to takie globalne dopasowanie, którego stopień jest możliwie największy.

Wracając do naszego pierwotnego dopasowania:
d1=ACT-GGCA
   ||| | |
d2=ACTTGACG
łatwo odczytujemy, że jego stopień jest równy 5 i wraz z drugim wariantem:
d1=AC-TGGCA
   || || |
d2=ACTTGACG
tworzą optymalne globalne dopasowanie sekwencji s1 i s2.

Przerwy w sekwencjach są konieczne by dokonać przesunięcia fragmentu jednej sekwencji względem drugiej. Miejsce do którego należy wstawić przesunięcie jest kluczowe i właściwie to ono decyduje o stopniu dopasowania.

O dopasowaniu globalnym to w zasadzie wszystko, czymże zatem jest dopasowanie lokalne?

Właściwie można powiedzieć, że jest to pewna wariacja dopasowania globalnego. Różni się od niego tym, że przy poszukiwaniu dopasowania nie rozpatruje się całej długości obu sekwencji, tzn nie polega ono na poszukiwaniu dopasowań całych ciągów s1 i s2 tak jak to robiliśmy powyżej. Dopasowanie lokalne polega na znalezieniu globalnych dopasowań fragmentów ciągów s1 i s2. Innymi słowy chodzi o znalezienie wszystkich podciągów w s1 i s2 oraz odpowiadających im globalnych dopasowań.

Jakkolwiek tajemniczo to brzmi, wyjaśnienie jest dość proste. Rozpatrzmy nasze sekwencje ponownie: s1=ACTGGCA, s2=ACTTGACG. Możemy w nich znaleźć różne podsekwencje np. ps1=CTGG i ps2=TGAC oraz ich globalne dopasowania:
ps1=CTGG-
     ||
ps2=-TGAC
właśnie takie globalne dopasowanie fragmentu sekwencji wyjściowej nazywamy jej lokalnym dopasowaniem. Tutaj to dopasowanie ma stopień 2.

Optymalne lokalne dopasowanie polega na wybraniu spośród wszystkich lokalnych dopasowań, takich których stopień jest największy.

Istnieje wiele sposobów wyszukiwania dopasowań, te najkrótsze kilkuznakowe można spokojnie wykonać ręcznie. Jednak dłuższe, w szczególności sekwencje biologiczne (nukleotydowe lub aminokwasowe) złożone z wielu tysięcy (a nawet milionów) znaków można dopasowywać tylko przy pomocy programów komputerowych.
Do najpopularniejszych sposobów rozwiązujących ten problem należą algorytmy Needlemana-Wunscha dla dopasowań globalnych i Smitha-Watermana dla dopasowań lokalnych.