Проверка наличия выравнивания

• Техническое задание

• План реализации

Автор идеи: Сергей Александрович Спирин.

Проверка наличия выравнивания в паре

Алгоритм:

• прочитать выравнивание (и получить удобное внутреннее представление)
• прочитать матрицу соответствий (и получить удобное внутреннее представление)
• для каждой позиции в выравнивании, посчитать вес этой позиции

• вес выравнивания – сумма весов позиций

• если вес выравнивания больше, чем удельный порог, помноженный на длину выравнивания, то выравнивание есть, иначе выравнивания нет

Параметры алгоритма и входные данные:

• выравнивание белковых последовательностей в формате FASTA
• матрица соответствий (например, на kodomo-count: /usr/share/EMBOSS/data/EBLOSUM62)
• gap penalty: штраф за начало разрыва в выравниваниии; рекоммендуемое значение: -12
• gap extend penalty: штраф за каждую позицию разрыва в выравнивании; рекоммендуемое значение: -4
• удельный порог; рекоммендуемое значение: 1

Вес позиции:

• если для позиции в выравнивании указано два остатка, вес – значние из матрицы соответствия по соответствующим строке и столбцу

• если для позиции указан только один остаток (т.е. отмечен gap) и мы не находимся внутри разрыва, то вес – gap penalty; если мы находимся внутри разрыва, то – gap extend penaly

• в противном случае вес – 0

Пример получения парного выравнивания в формате FASTA:

...$ needle sw:cyb5_human sw:cyb5_chicken outfile.fasta -auto -aformat3 fasta

Кроме построения выравнивания, программа needle может выдвать и вес выравнивания (если мы не указываем выходной формат, в качестве формата она выбирает srspair, в котором в комментариях пишет параметры алгоритма, вес и ещё несколько свойств выравнивания).

Анализ множественного выравнивания

Основная идея:

• посчитать вес выравнивания для каждой пары последовательностей во входных данных
• построить граф, в вершинах которого последовательности, и между двумя вершинами есть ребро тогда и только тогда, когда мы считаем, что между соответсвтующими последовательностями есть выравнивание
• найти на графе интересные части и выдать список вершин в них

Интересные части могут быть:

• компонента связности в графе

• клика в графе (клика – максимальный подграф, в котором любые две вершины соединены)

Примеры получения множественного выравнивания в формете FASTA¹:

...$ seqret sw:cyb5_* sequences.fasta
...$ muscle -in sequences.fasta -out alignment.fasta

...$ seqret sw-des:trypsin sequences.fasta
...$ muscle -in sequences.fasta -out alignment.fasta

...$ seqret sw-des:homeobox sequences.fasta
...$ muscle -in sequences.fasta -out alignment.fasta