Dopasowanie sekwencji

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.