Dopasowanie sekwencji, uliniowienie sekwencji – sposób dopasowania sekwencji nukleotydów w kwasach nukleinowych lub sekwencji aminokwasów w białkach w celu identyfikacji rejonów wykazujących podobieństwo, będący konsekwencją funkcjonalnych, strukturalnych lub ewolucyjnych powiązań między sekwencjami. Zestawione sekwencje są zwykle przedstawiane jako wiersze macierzy. Między reszty wprowadza się przerwy w taki sposób, że reszty zbliżonych do siebie sekwencji tworzą kolejne kolumny.
Jeśli dwie dopasowywane sekwencje mają wspólne pochodzenie, niedopasowania mogą być interpretowane jako mutacje punktowe, a przerwy jako mutacje polegające na delecji lub insercji, które zaszły w jednej lub obu liniach od czasu, kiedy obie sekwencje uległy rozdzieleniu. W przypadku dopasowywania sekwencji białek, stopień podobieństwa między aminokwasami zajmującymi konkretną pozycję, może stanowić zgrubną miarę tego, jak konserwatywny jest dany rejon lub motyw. Brak substytucji lub obecność jedynie konserwatywnych substytucji (to znaczy zamiany reszty na inną, ale o podobnych właściwościach chemicznych) w określonym rejonie sekwencji sugeruje, że jest on ważny strukturalnie lub funkcjonalnie. Dopasowywanie sekwencji może być także stosowane dla sekwencji pochodzenia pozabiologicznego, na przykład danych finansowych lub sekwencji występujących w językach naturalnych.
Bardzo krótkie lub bardzo podobne sekwencje mogą być dopasowane ręcznie. Bardzo często jednak konieczne jest dopasowanie licznych, bardzo długich i zmiennych sekwencji, które nie mogą być dopasowane wyłącznie ludzkim wysiłkiem. Zamiast tego, wysiłek wkładany jest w opracowanie algorytmów umożliwiające wysokiej jakości dopasowania, ewentualnie wprowadzanie poprawek do uzyskanych w ten sposób rezultatów, (szczególnie w przypadku sekwencji nukleotydowych). Ogólnie rzecz biorąc, metody obliczeniowe do dopasowywania sekwencji mogą być dwojakiego rodzaju: dopasowanie globalne i dopasowanie lokalne. Obliczanie dopasowania globalnego jest formą optymalizacji globalnej, w której dopasowanie musi obejmować całą długość wszystkich analizowanych sekwencji. Przeciwnie, dopasowanie lokalne identyfikuje podobne rejony w obrębie długich sekwencji, które – rozpatrywane w całości – nie muszą wykazywać znacznego podobieństwa. Dopasowania lokalne są zazwyczaj preferowane, ale ich obliczenie może być trudniejsze z uwagi na dodatkowe wyzwanie określenia rejonów wykazujących podobieństwo. Różnorodne algorytmy były stosowane do dopasowań sekwencji, w tym powolne, ale formalnie optymalizujące metody, jak programowanie dynamiczne, także efektywne metody heurystyczne czy probabilistyczne, zaprojektowane dla szeroko zakrojonych przeszukiwań baz danych.
Sposoby przedstawienia
Dopasowania są często prezentowane zarówno graficznie, jak i w formacie tekstowym. W prawie wszystkich sposobach przedstawienia dopasowań sekwencje zapisywane są w wierszach, ułożonych tak że dopasowane reszty tworzą kolejne kolumny. W formatach tekstowych, dopasowane kolumny, zawierające identyczne lub podobne symbole (reszty) są oznaczone znaczkami określającymi stopień konserwatywności. Jak na powyższym obrazku gwiazdka (ewentualnie pionowa linia „I”) są używane, aby zaznaczyć identyczność pomiędzy dwiema sekwencjami w danej pozycji; rzadziej używane symbole to dwukropek na oznaczenie konserwatywnych substytucji i kropka dla podstawień semikonserwatywnych. Wiele programów wizualizujących sekwencje używają kolorów stosownie do właściwości poszczególnych elementów sekwencji. W przypadku DNA i RNA sprowadza się to do przypisania każdemu nukleotydowi innego koloru. W dopasowaniach sekwencji białek, jak na rycinie powyżej, kolory są często użyte do oznaczenia właściwości aminokwasów, ułatwiając ocenę konserwatywności danego podstawienia. W przypadku dopasowania wielu sekwencji, ostatni wiersz stanowi często sekwencję konsensusową; sekwencja konsensusowa jest również często przedstawiona graficznie w postaci logo sekwencyjnego,w którym rozmiar każdego nukleotydu lub oznaczenia literowego aminokwasu odpowiadają stopniowi jego zakonserwowania.
Dopasowania sekwencji mogą być przechowywane w różnorodnych plikach w formacie tekstowym, z których wiele zostało rozwiniętych w połączeniu z konkretnym programem do dopasowań.
Dopasowania globalne i lokalne
Dopasowania globalne, obejmujące pełny zakres wszystkich sekwencji, są najbardziej użyteczne, gdy zestawiane sekwencje są podobne i o zbliżonych rozmiarach. (Co nie znaczy jednak, że dopasowania globalne nie mogą kończyć się przerwami). Ogólna technika dopasowania globalnego jest znana jako algorytm Needlemana-Wunscha i jest oparta na programowaniu dynamicznym. Dopasowania lokalne są bardziej przydatne dla sekwencji nie wykazujących w całości większego podobieństwa, co do których istnieje przypuszczenie, że zawierają podobne podsekwencje czy motywy. Algorytm Smitha-Watermana jest ogólną techniką dopasowania lokalnego, opartą na programowaniu dynamicznym. W przypadku sekwencji dostatecznie podobnych, rezultaty dopasowań globalnego i lokalnego są takie same.
Metody mieszane, znane jako semiglobalne, starają się znaleźć najlepsze możliwe dopasowanie obejmujące początek i koniec jednej lub drugiej z sekwencji. Mogą one być szczególnie użyteczne, gdy cześć 3' końcowa jednej sekwencji zachodzi na część 5' końcową drugiej z sekwencji. W takim wypadku ani globalne, ani lokalne dopasowanie nie jest w pełni odpowiednie: metody globalne starałoby się wymusić na dopasowaniu objęcie rejonu poza obszarem pokrywania, podczas gdy dopasowania lokalne mogłoby nie w pełni pokrywać rejon pokrywania.
Dopasowanie par sekwencji
Metody dopasowywania par sekwencji są używane w celu znalezienia możliwie najlepszych dopasowań lokalnych lub globalnych dwóch analizowanych sekwencji. Metody te mogą być użyte do dopasowania jednocześnie tylko dwóch sekwencji, ale ich obliczanie jest efektywne i są one często używane, gdy nie jest potrzebna wysoka precyzja (np. w czasie szukania w bazie danych sekwencji o znacznej homologii względem naszej sekwencji. Trzy główne metody tworzenia dopasowań par sekwencji to metody dot-matrix, programowanie dynamiczne i metody „k” - krotek (metody oparte na słowach);. Metody dopasowywania wielu sekwencji mogą zostać także zastosowane do dopasowań par. Chociaż każda z metod ma swoje słabe i mocne strony, wszystkie trzy metody dopasowań par sekwencji mają trudności z silnie repetytywnymi sekwencjami o niskiej ilości informacji – szczególnie gdy ilość powtórzeń w obu sekwencjach jest różna. Jednym ze sposobów wyrażania ilościowego użyteczności danego dopasowania pary sekwencji jest 'maximum unique match', czyli najdłuższa podsekwencja, która występuje w obu dopasowywanych sekwencji. Dłuższe zazwyczaj odzwierciedlają bliższe pokrewieństwo.
Metody dot-matrix
Dot-matrix, dostarczająca rodzinę dopasowań dla poszczególnych rejonów sekwencji, jest prostym podejściem jakościowym, jednak analiza wyników na dużą skalę jest czasochłonna. Pewne cechy sekwencji – insercje, delecje, powtórzenia proste czy odwrócone – są łatwo dostrzegalne na graficznej wizualizacji dot-matrix. Konstruując taką wizualizację zapisujemy nasze dwie sekwencje, odpowiednio, w pierwszym wierszu i pierwszej kolumnie dwuwymiarowej macierzy. W miejscu odpowiadającym identycznym/podobnym pozycjom w obu sekwencjach stawiana jest kropka. Niektóre implementacje różnicują rozmiar lub intensywność kropki w zależności od stopnia podobieństwa w odpowiednich pozycjach, przez co można odróżnić substytucje mniej i bardziej konserwatywne. W przypadku bardzo zbliżonych sekwencji na takiej macierzy kropki układają się w pojedynczą linię wzdłuż głównej przekątnej.
Macierze takie mogą zostać użyte do oszacowania powtarzalności pojedynczej sekwencji. wówczas ta sama sekwencja jest zapisana w pierwszym wierszu/kolumnie, a rejony o znacznym podobieństwie utworzą linie poza główną przekątną. Z taką sytuacją mamy do czynienia, gdy białko składa się z wielu podobnych domen strukturalnych.
Programowanie dynamiczne
Technika programowania dynamicznego może być zastosowana do dopasowań globalnych przez algorytm Needlemana-Wunscha, oraz dopasowań lokalnych przez algorytm Smitha-Watermana. Typowo, dopasowania białek wykorzystują macierz substytucji, zawierającą wkład identycznych aminokwasów i różnych substytucji do wartości dopasowania, oraz kary za przerwy, tj. zestawienie aminokwasu w jednej z sekwencji z przerwą w drugiej. Dopasowania DNA i RNA mogą wykorzystywać macierz wartości, ale często po prostu przypisana jest dodatnia wartość dopasowaniom, ujemna niedopasowaniom, podobnie przewidziana jest kara za przerwy.
Programowanie dynamiczne może być użyteczne przy dopasowywaniu sekwencji nukleotydowej do sekwencji białka, zadanie to jest utrudnione przez możliwe mutacje powodujące zmianę ramki odczytu (insercje lub delecje). Metody framesearch tworzą serię dopasowań globalnych lub lokalnych par sekwencji – sekwencji nukleotydowej dostarczonej w zapytaniu i przeszukiwanego zestawu sekwencji białek, lub vice versa. Chociaż metoda ta jest bardzo powolna, jest użyteczna w przypadku sekwencji zawierających wiele indeli, które może być bardzo trudno dopasować przy użyciu bardziej efektywnych metod heurystycznych. W praktyce metoda ta wymaga znacznej mocy obliczeniowej lub systemu, którego architektura jest ukierunkowana na programowanie dynamiczne.