Выравнивание последовательностей

В биоинформатике, выравнивание последовательностей — размещение последовательностей ДНК, РНК, и белков для того, чтобы увидеть места схожести, которые могут быть следствием функциональных, структурных или эволюционных взаимосвязей между последовательностями.^[1]

Алгоритмы выравнивания последовательностей также используются в NLP.

Графическое и текстовое представление

В большинстве представлений результата выравнивания, последовательности располагаются в строчках матрицы таким образом, что совпадающие элементы (нуклеотиды или аминокислоты) находятся один под другим (в одной колонке). «Разрывы» заменяются знаком «-» или ячейка остается пустой.

Выравнивание двух последовательностей аминокислот («цинковых пальцев»), сгенерированное программой ClustalW. В левой колонке находятся идентификаторы этих последовательностей в базе GenBank.
Обозначения: Буквы — Аминокислоты. Знаки: «*» — одинаковые. «.» — в одной цветовой группе. «:» — одинаковой формы.

Попарное выравнивание

Попарное выравнивание используется для нахождения совпадающих участков двух последовательностей. Различают глобальное и локальное выравнивание. Глобальное выравнивание применяется к «похожим» последовательностям приблизительно одинаковой длины и наглядно показывает разницу между этими последовательностями. Локальное выравнивание применяется для преимущественно отличающихся друг от друга последовательностей, которые предположительно могут содержат одинаковые участки. Следующий пример демонстрирует различие между результатами глобального и локального выравнивания для одинаковых исходных данных

• Глобальное

SQ1: FTFTALILLAVAV
SQ2: F--TAL-LLA-AV

• Локальное

SQ1: FTFTALILL-AVAV
SQ2: --FTAL-LLAAV--

Глобальное выравнивание базируется на алгоритме Нидлмана-Вунша, локальное — на алгоритме Smith-Waterman.

Алгоритмы поиска

Применяются для поиска в больших базах данных последовательностей, схожих с некой заданной последовательностью по указанным критериям. Применяемое выравнивание — локальное. Для повышения скорости поиска используются различные эвристические методы. Наиболее известные программы — BLAST ([1]) и FASTA3x

Множественное выравнивание

По сути является попарным выравниваем всех последовательностей в неком наборе и нахождение наиболее «оптимального» общего выравнивания. Применяется преимущественно для нахождения консервативных регионов в наборе последовательностей. Также используется в процессах установления эволюционных связей путем построения филогенетических деревьев. Так как множественное выравниваение является NP-полной задачей^[2][3], различные ее решения базируются на эвристиках, генетических и иных алгоритмах комбинаторной оптимизации. Наиболее известные программы, осуществляющие множественное выравнивание — Clustal([2]) и T-coffee

Структурное выравнивание

Применяется к белкам и RNA-последовательностям, для которых известна их вторичная и/или третичная структура.

Примечания

1. ↑ Mount DM. Bioinformatics: Sequence and Genome Analysis. — 2nd. — Cold Spring Harbor Laboratory Press: Cold Spring Harbor, NY., 2004. — ISBN 0-87969-608-7
2. ↑ Wang L, Jiang T. (1994). «On the complexity of multiple sequence alignment». J Comput Biol 1 (4): 337–48. PMID 8790475.
3. ↑ Just W. (2001). Computational complexity of multiple sequence alignment with SP-score. J Comput Biol 8(6):615-23.