Описание тега sequence-alignment

Описание тега Вопросы с тегом

Типовая проблема, в которой две или более последовательности должны быть выровнены друг с другом, как правило, с целью выявления сходства между ними. Эти проблемы распространены в биоинформатике, но алгоритмы, используемые для их решения, не менее важны для выравнивания других типов последовательностей, таких как текстовые строки. Для решения различных подгрупп этой проблемы было разработано множество алгоритмов.

Проблемы выравнивания последовательностей - это группа проблем, в которых у вас есть две или более последовательностей, как правило, с некоторыми потенциально похожими частями, которые вы хотите выстроить так, чтобы похожие части каждой были связаны. Часто это важный компонент при вычислении сходства последовательностей.

Выравнивание последовательностей часто важно в биоинформатике, когда последовательности ДНК, РНК или аминокислот должны быть выровнены, чтобы сделать вывод, какие мутации произошли, где и когда. Однако проблемы с выравниванием последовательностей возникают во всех доменах, в которых есть последовательности, например, при сопоставлении текста.

Динамическое программирование. Динамическое программирование - это наиболее часто используемый метод для выравнивания двух последовательностей (для выравнивания множественных последовательностей см. Ниже). Начиная с первого элемента каждой строки, каждая пара элементов либо выравнивается (если они совпадают), либо обрабатывается одним из описанных ниже операторов (если они не совпадают). Подробнее см. На этой странице.

Точный используемый алгоритм динамического программирования зависит от конкретной проблемы. Вот два наиболее распространенных:

Needleman-Wunsch - Глобальное выравнивание двух последовательностей (т.е. необходимо использовать все буквы в обеих последовательностях)
Смит-Уотерман - локальное выравнивание двух последовательностей (т. Е. Необходимо использовать только подпоследовательность каждой строки)

При выравнивании последовательностей обычно допускаются три основные операции. Проще всего думать об этих операциях как о вещах, которые могли произойти с одной из последовательностей, чтобы превратить ее в другую последовательность:

Вставка: элемент вставляется в одну из последовательностей. Обычно это представляется добавлением пробела к противоположной последовательности.
Удаление: элемент удаляется из одной из последовательностей. Обычно это вставляется путем добавления пробела к этой последовательности.
Мутация / Замена: элемент заменяется другим элементом.

У каждой из этих операций есть стоимость, связанная с ними, чтобы отразить, насколько вероятно, что они произошли бы с исходной последовательностью. Мутация / замена обычно имеет разную стоимость для разных замен (часто генерируемых из матрицы BLOSUM или PAM в биоинформатике). Вставка и удаление учитывались с каким-то штрафом за пробелы. В простых реализациях этот штраф часто представляет собой постоянную стоимость за пропуск, но в биоинформатике часто более уместен штраф за аффинный пропуск.

Выравнивание множественных последовательностей: динамическое программирование быстро становится сложным с вычислительной точки зрения дорогостоящим, поскольку число выравниваемых последовательностей увеличивается. По этой причине алгоритмы множественного выравнивания последовательностей обычно не гарантируют оптимальности. Используются самые разные техники:

Прогрессивное выравнивание: в этом методе серии попарных выравниваний используются для создания общего многостороннего выравнивания. Часто порядок, в котором выполняется это выравнивание, определяется алгоритмом иерархической кластеризации, таким как соединение соседей или UPGMA. Существует ряд инструментов для выполнения таких согласований в биоинформатике, таких как семейство Clustal и T-Coffee.
Эвристические подходы: для очень крупномасштабного множественного выравнивания последовательностей можно использовать широкий спектр эвристик. Blast - безусловно, самый популярный инструмент для этого в биоинформатике.
Модели Скрытого Маркова: HMM могут быть использованы для поиска наиболее вероятных выравниваний для набора последовательностей. HMMER - популярный инструмент биоинформатики для этого подхода.