Майнор по биоинформатике

Дмитрий Коновалов

Лекция 5

Поиск схожих последовательностей. Алгоритм и программа BLAST. Статистика локального выравнивания.

�

Молекулярная эволюция – эволюция текстов

Гомология

Крыло птицы

Крыло летучей мыши

рука человека

Определения:

гомологичными в биологии называют сопоставимые части сравниваемых биологических объектов.

гомологичными в биоинформатике называют последовательности, которые произошли от общего предка

гомология и аналогия

  Гомология (общий предок) против  аналогии (конвергентная эволюция)

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

крыло птицы

крыло бабочки

крыло летучей мыши

крыло мухи

Cхожесть последовательностей и гомология

Если две (сложные) последовательности обладают значительной схожестью между первичными последовательностями, у них общий предок и, возможно, одинаковые функции.�

(хотя некоторые белки обретают совершенно новые функции, как, например, появление альфа-кристаллина).

Следующее утверждение основано на наблюдении и не является истинным a priori:

​

Элементы теории локального выравнивания

• Задача: по заданной последовательности найти другие в базе данных последовательностей, которые “показывают схожесть” на статистически значимом уровне.

Типы выравнивания

Алгоритмы выравнивания будут отличаться от типа выравнивания которое мы строим.

8

Две задачи.

​

Есть последовательность гена, нужно найти его в геноме. - локальная гомология. Ищем подпоследовательность.

​

Есть белковые последовательности от 2х родственных организмов, определить места и типы мутаций. Гомология по всей длине последовательности, для каждой буквы должен найтись родственник.

Что такое схожесть?

0 ATGCGCAATTGC

​

1 CTACGCATTTGC

2 AAGCACAACCCC

​

Какая из последовательностей более схожа с последовательностью 0?

Что такое схожесть?

0 ATGCGCAATTGC

​

1 CTACGCATTTGC 9/12

2 AAGCACAACTCT 7/12

​

Identity

Что такое схожесть?

0 ATGCGCAATT

​

1 CTACTCTAAT 5/10

2 TCCCGCAACC 5/10

​

Какую последовательность выбрать в этом случае?

Что такое схожесть?

0 ATGCGCAATT

​

1 CTACTCTAAT 5/10

2 TCCCGCAACC 5/10

​

Какую последовательность выбрать в этом случае?

Алгоритм BLAST

• Программы BLAST (Basic Local Alignment Search Tools) представляют собой набор алгоритмов для сравнения последовательностей. Были впервые опубликованы в 1990 году для поиска оптимального локального выравнивания данной последовательности с другими в базе данных последовательностей.

​

• Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ (1990) “Basic local alignment search tool.” J. Mol. Biol. 215:403-410.
• Altschul SF, Madden TL, Schaeffer AA, Zhang J, Zhang Z, Miller W, Lipman DJ (1997) “Gapped BLAST and PSI-BLAST: a new generation of protein database search programs.” NAR 25:3389-3402.

13

Алгоритм BLAST

• Вес совпадений считается по матрицам счета
• Последовательности разбиты на слова (words) (по умолчанию длина n=3)
• Обеспечивает скорость и вычислительную эффективность
• Алгоритм BLAST расширяет исзначальный “зародыш” (“seed”) до сегмента с большим весом (High Scoring Pairs, HSP)

14

Параметр, можно менять

При поиске близких последовательностей важна статистика

• Различие между настоящим совпадением и артефактом делается с помощью оценок вероятности, что совпадение могло быть случайным.
• Мы обсудим значение весов (scores, S) и ожиданий (e-values, E), которые ассоциируются с выравниваниями, отобранными BLAST.

15

Как считается вес (score, S)

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

​

16

Матрица весов

• Матрицы замен используются для аминокислотных выравниваний

​

• Более простая унитарная матрица используется для ДНК-выравнивания (+1 для совпадения, -2 для несовпадения)

17

17

6

5. Получение матрицы BLOSUM62

BLOSUM vs PAM

• По умолчанию в программе BLAST 2.0 используется матрица BLOSUM 62. Хотя она предназначена для поиска умеренно разошедшихся белков, ее использование довольно эффективно при поиске более близких последовательностей. Поиск дальних родственников может оказаться более эффективен с другими матрицами.

19

BLOSUM 45 BLOSUM 62 BLOSUM 90

PAM 250 PAM 160 PAM 100

Более разошедшиеся Менее разошедшиеся

Что означают значения веса (score) и ожидания (e-value).

• Качество выравнивания представлено весом Score (S).
• Вес выравнивания расчитывается как сумма замен и пропусков. Вес замен берется из матриц (PAM, BLOSUM), а вес пропусков назначается эмпирически.

​

• Значимость каждого выравнивания вычисляется в виде ожидания E value (E).
• Ожидание. Число различных выравниваний с весом равным или большим, чем S, которое ожидается найти в данной базе данных случайным образом. Чем меньше E-value, тем более значим вес.
• E-value - это не вероятность, а ожидание. Причина, по которой программы BLAST выдают не вероятности, а ожиданиe, состоит в том, что гораздо легче понять значения ожидания в 5 или 10 последовательностей, чем вероятности 0.993 и 0.99995. Однако при E<0.01 значения вероятностей и ожиданий практически совпадают.

​

20

Что надо знать о E-values

• Низкие значения E-values означают, что последовательности гомологичны
• Однако, высокие не означают негомологичность
• Статистическая значимость зависит как от размера выравненного участка так и от размера базы данных
• Important consideration for comparing results across different searches
• E-value увеличивается с увеличением размера базы данных
• E-value уменьшается с увеличением размера участка выравнивания

21

Как работает BLAST?

• Качество и относительная скорость поиска программ BLAST (важные свойства при учете того, что базы данных постоянно растут) достигается с помощью подхода, при котором исходная последовательность и последовательности базы данных разбиваются на фрагменты (слова, "words"), и первоначальный поиск совпадений производится между фрагментами.

​

• После изначального нахождения совпадающих “слов” выравнивание расширяется по обоим направлениям с целью сгенерить выравнивание с весом, превышающим некоторое пороговое значение S.

​

22

Алгоритм BLAST

23

Алгоритм BLAST

24

Расширение выравнивания до достижения максимального веса� High Scoring Segment Pair (HSP)

25

Минимальный вес (S)

Пороговый вес для первого совпадающего слова (T)

Расширение сегмента вдоль выравнивания

• Прекращает расширение, когда вес выравнивания уменьшается на X ниже полученного максимального значения

​

• Не рассматривает сегменты с весом < S

​

​

ASKIOPLLWLAASFLHNEQAPALSDAN

JWQEOPLWPLAASOIHLFACNSIFYAS

Score=15

Score=17

Score=14

Как работает BLAST?

Как работает BLAST?

​

Параметры

​

W : Размер слова (Word) – найти совпадающие слова между последовательностями

длина 2-3 для aминокислот, 6-11 для нуклеотидов.

​

T : Порог (Threshold) – оставить только слова с весом >T

обычно 11-13

​

X : Потеря веса – остановить расширять выравнивание, когда потеря >X

​

S : Вес (Score) – Финальный вeс сегмента

​

Как работает BLAST?

Алгоритм:

​

1. Выравнивает исходную последовательность с последовательностью из базы данных.

​

• Находит “хиты” (“hits”): короткие выровненные сегменты длины W без пробелов с весом не меньше T.

​

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

Этот шаг потребляет основное время процессора (>90%)

​

Программы BLAST

31

Дополнительные программы BLAST

32