2 of 37

Краткий обзор

введение в молекулярную биологию
современная биология: “омы” и “омики”
алгоритмы выравнивания геномных последовательностей

глобальное и локальное выравнивание
сборка генома

протеомика

алгоритмы анализа масс-спектрометрии
свертка белков

марковские цепи в симуляции эволюционных процессов

3 of 37

Молекулярная биология

Основной интерес для молекулярной биологии представляют:

механизмы хранения и передачи генетической информации
сложные высокомолекулярные соединения:

ДНК
РНК
белки

4 of 37

Структура ДНК

ДНК человека:

46 хромосом (обычно)
3 млрд. пар оснований
из которых <1.5% белок-кодирующих
достигает 2-3 м. в длину

5 of 37

Центральная догма м.б.

6 of 37

Репликация и транскрипция

7 of 37

Трансляция

9 of 37

“Омы” и “омики”

Геномика

Транскриптомика

Микробиомика

Протеомика

Эпигеномика

10 of 37

Собственно, о биоинформатике

Методы исследования нуклеиновых кислот и белков:

PCR (полимеразно-цепная реакция)
секвенирование
масс-спектрометрия
рентгеноструктурный анализ
хроматография
электрофорез
…

Другие области:

филогенетика
эволюционные процессы

11 of 37

Методы секвенирования

12 of 37

Методы сборки генома

Средние риды, мало ошибок:

overlap consensus graph

Небольшие риды:

De Bruijn graph
string graph

Большие риды с 10% ошибок:

alignment algorithms
BLASR + MinHash
BLAST
…

13 of 37

Overlap consensus graph

14 of 37

De Bruijn graph

15 of 37

Третье поколение секвенирования

16 of 37

Обратно к графу перекрытий

Как искать перекрытия?

Задача о выравнивании

Динамическое программирование

Needleman-Wunsch
Smith-Waterman
+ scoring, affine gap penalty

Суффиксные структуры

seed-and-extend

17 of 37

Выравнивание через ДП

18 of 37

BLASR-выравнивание

Идея:

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

19 of 37

BLASR: нахождение seeds

MHAP - MinHash Approach

В частности, для оценки схожести последовательностей можно использовать индекс сходства Жаккара (Jaccard):

J(X, Y) = |S and Y| / |S or Y|

MHAP позволяет быстро считать J с помощью приближения

J(S1, S2) ~ D(Sketch1, Sketch2)

20 of 37

MHAP: оценки

21 of 37

В мире протеомики

22 of 37

Масс-спектрометрия

- по сути, “взвешивание” множества молекул в пробе одновременно

23 of 37

Масс-спектрометрия

25 of 37

Orbitrap и Фурье

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

За этим стоит сложная математика, но алгоритм, совершающий это преобразование и обратное ему, лежит в основе работы Orbitrap.

26 of 37

Идентификация белков

Для обработки белка его чаще всего бьют на подчасти-пептиды (Bottom-Up/Shotgun) вместо анализа целого белка (Top-Down)

После фильтрации пробы специальная протеаза режет выбранный пептид на все возможные префиксы и суффиксы.

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

27 of 37

Spectrum graph

Исходная задача - нахождение равных прямого и обратного пути

Модификации (из-за неточности измерений):

вес ребер (интенсивность)
tag generation
сравнение с базами данных (в случае уже изученных белков)

Глобально - еще нет оптимального алгоритма!

28 of 37

Еще немного протеомики с MS

29 of 37

Rosetta@home и FoldIt

30 of 37

MCMC

Markov chain Monte Carlo

Марковские цепи:

состояния 1, …, n
p(i,j,[n]) - вероятности перехода между состояниями
будущее зависит только от настоящего и не от прошлого

Теорема Перрона-Фробениуса:

если цепь неразложима и апериодична, то она сходится к некому стационарному распределению

Метод Монте-Карло:

симуляция вероятностных изменений, направленных в сторону увеличения функции правдоподобия

31 of 37

Metropolis-Hastings algorithm

Находимся в состоянии x
Вероятностный provider предлагает переход в состояние x’ с вероятностью Q(x, x’)
Acceptance ratio, основанный на желаемом распределении:

Стационарное распределение pi

Функция перехода Q

При alpha > 1 переходим в x’, иначе переходим в x’ с вероятностью alpha
Повторяем достаточное число раз

32 of 37

MCMC в биологии

Задача: построение филогенетического дерева по набору геномов

G - набор геномов
t, v, m - дерево, веса ребер и параметры мутации

Формула Байеса:

Формула перехода:

33 of 37

Переходы для дерева

TBR

tree bisection and reconnection

NNI

nearest neighbour interchange

SPR

subtree pruning and regraphing

1 of 37