Выравнивание последовательностей
Выравнивание последовательностей — биоинформатический метод, основанный на размещении двух или более последовательностей мономеров ДНК, РНК или белков друг под другом таким образом, чтобы легко увидеть сходные участки в этих последовательностях. Сходство первичных структур двух молекул может отражать их функциональные, структурные или эволюционные взаимосвязи[1].
Алгоритмы выравнивания последовательностей также используются в NLP.
Содержание |
[править] Графическое и текстовое представление
В большинстве представлений результата выравнивания, последовательности располагаются в строчках матрицы таким образом, что совпадающие элементы (нуклеотиды или аминокислоты) находятся один под другим (в одной колонке). «Разрывы» заменяются знаком «-» или ячейка остается пустой.
Обозначения: Буквы — Аминокислоты. Знаки: «*» — одинаковые. «.» — в одной цветовой группе. «:» — одинаковой формы.
[править] Попарное выравнивание
Попарное выравнивание используется для нахождения совпадающих участков двух последовательностей. Различают глобальное и локальное выравнивание. Глобальное выравнивание применяется к «похожим» последовательностям приблизительно одинаковой длины и наглядно показывает разницу между этими последовательностями. Локальное выравнивание применяется для преимущественно отличающихся друг от друга последовательностей, которые предположительно могут содержат одинаковые участки. Следующий пример демонстрирует различие между результатами глобального и локального выравнивания для одинаковых исходных данных
- Глобальное
SQ1: FTFTALILLAVAV
SQ2: F -- TAL-LLA-AV
- Локальное
SQ1: FTFTALILL-AVAV
SQ2: - - FTAL-LLAAV--
Глобальное выравнивание базируется на алгоритме Нидлмана-Вунша, локальное — на алгоритме Смита-Ватермана.
[править] Алгоритмы поиска
Применяются для поиска в больших базах данных последовательностей, схожих с некой заданной последовательностью по указанным критериям. Применяемое выравнивание — локальное. Для повышения скорости поиска используются различные эвристические методы. Наиболее известные программы — BLAST ([1]) и FASTA3x
[править] Множественное выравнивание
По сути является попарным выравниваем всех последовательностей в неком наборе и нахождение наиболее «оптимального» общего выравнивания. Применяется преимущественно для нахождения консервативных регионов в наборе последовательностей. Также используется в процессах установления эволюционных связей путем построения филогенетических деревьев. Так как множественное выравнивание является NP-полной задачей[2][3], различные ее решения базируются на эвристиках, генетических и иных алгоритмах комбинаторной оптимизации. Наиболее известные программы, осуществляющие множественное выравнивание — Clustal([2]), T-coffee, MUSCLE(http://www.drive5.com/muscle/) и MAFFT(http://mafft.cbrc.jp/alignment/software/).
[править] Структурное выравнивание
Применяется к белкам и RNA-последовательностям, для которых известна их вторичная и/или третичная структура.
[править] Примечания
- ↑ Mount DM. Bioinformatics: Sequence and Genome Analysis. — 2nd. — Cold Spring Harbor Laboratory Press: Cold Spring Harbor, NY., 2004. — ISBN 0-87969-608-7
- ↑ Wang L, Jiang T. (1994). «On the complexity of multiple sequence alignment». J Comput Biol 1 (4): 337–48. PMID 8790475.
- ↑ Just W. (2001). Computational complexity of multiple sequence alignment with SP-score. J Comput Biol 8(6):615-23.
