Расшифровка ДНК как египетские иероглифы

Чем занимается сравнительная геномика

На основе материалов майнора 2022-23 года Антонова Ивана

И моих материалах для магистров АДБМ

Египетские пирамиды

Египетские иероглифы

3

Все известные последовательности ДНК находятся здесь

4

Участок ДНК

5

Поиск повторений в египетских текстах

6

Некоторые повторения в египетских текстах

7

“язык”

Некоторые повторения в египетских текстах

8

“исчезнуть”

Некоторые повторения в египетских текстах

9

“красивые девушки”

Биологические повторы

10

“Сайт связывания с рибосомой”

Повторы могут немного отличаться друг от друга

11

Повторы могут немного отличаться друг от друга

12

Программа MEME – ищет повторы

13

A G G A G G

A G G A G T

A G G A G G

A G G A G G

MEME

MEME

Розетский камень

14

Jean-Francois Champollion

15

AB INITIO ПРЕДСКАЗАНИЕ БЕЛОК-КОДИРУЮЩИХ ГЕНОВ

Рамка считывания

Как таблица генетического кода помогает найти потенциальные гены?

17

Как фотография хранится в памяти компьютера?

Фотография состоит из пикселей

Трансляция

00000001011101010101000011111010 … 010101011111

Black

Dark red

Red

Red

Новая строка

ATGAAACCCGGGGTTTACCCCATGG … TGA

M

STOP!

A

C

G

W

N

Q

M

Вернемся к ДНК!

Таблицы конвертации

22

Black

Dark red

Red

White

Новая строка

00000000

​

01110101

​

01010000

​

11111111

…

​

01010101

Метионит (M)

Глутамин (Q)

Валин (V)

Цистеин (C)

Стоп-кодон

ATG

​

CAG

​

GTG

​

TGT

…

​

TGA

​

TAA

​

TAG

Стоп-кодон

Стоп-кодон

Генетический код: кодон => аминокислота

23

Рамка считывания

00000001011101010101000011111010 … 010101011111

Black

Dark red

Red

Red

Новая строка

Что еще важно, чтобы получить правильную фотографию?

00000001011101010101000011111010 … 010101011111

Green

Dark green

Gray

New Line

New Line

Та же картинка, прочитанная в рамке +1

Много байтов «новая строка» + преждевременный байт окончания файла

Трансляция ДНК в 3х рамках считывания

C T A A C T C T T A A T A T G A A A G A T …

Leu

Thr

Leu

Asn

Ser

Asp

Основная рамка:

Glu

Открытая рамка считывания

Open reading frame (ORF)

Кодирующий потенциал

AB INITIO ПРЕДСКАЗАНИЕ БЕЛОК-КОДИРУЮЩИХ ГЕНОВ

Алгоритм GeneMark

СКРЫТЫЕ�Модели Маркова�����

Hidden Markov�Models

Hidden Markov Models - HMM

31

Hidden variables

Observed data

Пример: Нечестное казино

32

Собственно, что скрыто в данной модели?

Пример: Нечестное казино

33

Часто говорят, что P(x) – вероятность того, что x сгенерирован данной моделью

p1=p2=p3=p4=p5=p6=1/6

P6=1/2

p1=p2=p3=p4=p5=1/10

• Известно:
• Структура модели
• Вероятности переходов
• Скрыто: Что делает казино
• FFFFFLLLLLLLFFFF...
• Наблюдаемые: последовательность бросков кости
• 3415256664666153...
• Что нам нужно вычислить?:
• Когда использовалась честная кость?
• Когда использовалась нечестная кость?
• Ответ представляет собой последовательность�FFFFFFFLLLLLLFFF...

• Модель присваивает вероятность каждому объяснению наблюдений:� P(326|FFL) � = P(3|F)·P(F→F)·P(2|F)·P(F→L)·P(6|L)� = 1/6 · 0.99 · 1/6 · 0.01 · ½

​

• Максимальное правдоподобие: нахождение более вероятного объяснения
• Найти путь, который с наибольшей вероятностью сгенерирует наблюдаемую последовательность
• Полная вероятность: вероятность, что наблюдаемая последовательность была сгенерирована HMM
• Рассмотреть все пути, которые могли бы сгенерировать наблюдаемую последовательность

Имея модель, мы можем сгенерировать последовательность: первое состояние выбирается из распределения вероятностей состояний - a,

• в этом состоянии наблюдение генерируется (испускается, emitted) по вероятностям e

A “parse” of a sequence

x₁

x₂

x₃

x_L

2

1

K

2

Совместная вероятность последовательности наблюдений x и последовательности состояний π

Нечестное казино

Как GeneMark предсказывает гены?

X = WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

2 модели: честная или шулерская кость

X = GATGGGATTGGGGTTTTCCCCTCCCATGTGCTCAAGACTGGCGCTAAAAGTTTTGAGCTTCTCAAAAGTC

2 модели: белок-кодирующая область или некодирующая

• We can now evaluate any path through hidden states, given the emitted sequences
• How do we find the best path?

– Try all possibilities? Not practical, exponential number of paths

– 1 human gene ~ 100,000 nucleotides 2^100,000 paths for 2 states!

• Instead: Dynamic programming Viterbi algortithm

– Store partial computation (max score to position i through state k)

Define V_k(i) = Probability of most likely path through state π_i =k

– Use it to compute max score to position i+1 through each state k’

Compute V_k’(i+1) as a function of maxk { V_k(i) }

– Simple computation, just include emission score + cost of transition

V_k(i+1) = e_k(x_i+1) * max_j a_jk Vj (i)

DP works because of optimal sub-structure

Best path through a given state is:

• Best path to previous state
• Best transition from previous state to this state
• Best path to the end state

Finding the optimal path

Наиболее вероятный путь

Наиболее вероятный путь π^* удовлетворяет

Чтобы найти π^*, рассмотрим все возможные пути у которые могут испускать x

Пусть

Тогда

The Viterbi Algorithm

• Инициализация (i = 0)��
• Рекурсия (i = 1, . . . , L): Для каждого k��
• Остановка:

To find π^*, use trace-back, as in dynamic programming

Viterbi: пример

1

π

x

0

0

6

2

6

ε

(1/6)×(1/2)

= 1/12

0

(1/2)×(1/2)

= 1/4

(1/6)×max{(1/12)×0.99,

(1/4)×0.2}

= 0.01375

(1/10)×max{(1/12)×0.01,

(1/4)×0.8}

= 0.02

B

F

L

0

0

(1/6)×max{0.01375×0.99,

0.02×0.2}

= 0.00226875

(1/2)×max{0.01375×0.01,

0.02×0.8}

= 0.08

The Viterbi Algorithm

sequence

states

(i,k)

k

k-1

. . .

k-2

k+1

. . .

. . .

Viterbi: Обратный проход

T( T( T( ... T( T(i, L-1), L-2) ..., 2), 1), 0) = 0

Viterbi gets it right more often than not

Вероятность испускания по всем путям

• Каждый путь ассоциирован с некой вероятностью

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

– Viterbi наиболее вероятный путь

•Сколько вероятности от полной он в себе содержит?

•решение

– рассчитать сумму

• P(x) = Σπ P(x,π)

– можно использовать динамическое программирование

• аппроксимация

–рассчитать вероятность наиболее вероятного пути (Viterbi) π*

– может хорошо приближать, но, в целом, неправильно

Легко перейти к нуклеотидам

Байесовский подход

48

Чем отличается P(x|𝜋) от P(𝜋|x)?

​

Как они связаны?

Предсказание генов

Белок-Кодирующая

Некодирующая

P(A) = 20.5%

P(C) = 29.6%

P(G) = 35.4%

P(T) = 14.5%

P(A) = 20.4%

P(C) = 28.3%

P(G) = 32.8%

P(T) = 18.4%

Участок ДНК:

x = GATGGGATTGGGGTTTTCCCCTCCCATGTGCTCAAGACTGGCGCTAAAAGTTTTGAG

Теорема Байеса

Третья позиция кодона – особенная

Кодирующая область vs. Некодирующая

Nucleotide frequency patterns �in non-coding DNA (left half of the picture) and protein-coding DNA (right half) �

visualization of alignment of 1000+ E. coli sequences with length 120 nt; �each sequence contains a gene start in the middle

Учет кодонов

Белок-Кодирующая

Некодирующая

Позиция в кодоне

1 2 3

P(A) 19.3% 28.8% 13.2%

P(C) 24.1% 33.4% 31.5%

P(G) 45.8% 19.3% 41.2%

P(T) 10.8% 18.4% 14.1%

​

​

P(A) = 20.4%

P(C) = 28.3%

P(G) = 32.8%

P(T) = 18.4%

Участок ДНК:

x = GCG

​

Можем ли мы сказать, белок-кодирующий он или нет?

Вероятность белок-кодирующего гена?

COD1 – белок-кодирующая последовательность в рамке 0

COD2 – белок-кодирующая последовательность в рамке +1

COD3 – белок-кодирующая последовательность в рамке +2

NON - некодирующая последовательность

​

x = G C G

P(x|COD1) = ?

P(x|COD2) = ?

P(x|COD3) = ?

P(x|NON) = ?

​

Постериорные вероятности:

P(COD1|x) = ?

P(COD2|x) = ?

P(COD3|x) = ?

P(NON|x) = ?

Как улучшить предсказание?

54

Что мы можем измерить ,чтобы использовать в модели?

• Большинство того, что мы знаем о последовательностях относится к белок-кодирующим характеристикам
• ORF (Open Reading Frame)/ОРС (открытая рамка считывания): последовательность определяемая по AUG и стоп кодон, что в свою очередь определяет последовательность аминокислот.
• Codon Usage/Использование кодонов: наиболее часто измеряется в CAI (Codon Adaptation Index/индекс адаптации кодонов)
• Другие явления
• Частоты и корреляции нуклеотидов:
• Функциональные сайты:
• сайты сплайсинга, промотеры, НТО, сайты полиаденилирования

Метод «Скользящего окна»

1 2 2 3 4 5 6 6 6 5 4 2 1 3 4 4 6 6 6 6 5 5 4 3 2 1 5 6 5 4 3 2 2 1 1 1 6 6 6 6 6 6 1 1 2 4 5 3 4 5 6 2 3 4 1 2 2 3 4 5 6 6 6 5 4 2 1 3 4 4 6 6 6 6 5 5 4 3 2 1 5 6 5 4 3 2 2 1 1 1 6 6 6 6 6 6 1 1 2 4 5 3 4 5 6 2 3 4 1 2 2 3 4 5 6 6 6 5 4 2 1 3 4 4 6 6 6 6 5 5 4 3 2 1 5 6 5 4 3 2 2 1 1 1 6 6 6 6 6 6 1 1 2 4 5 3 4 5 6 2 3 4 1 2 2 3 4 5 6 6 6 5 4 2 1 3 4 4 6 6 6 6 5 5 4 3 2 1 5 6 5 4 3 2 2 1 1 1 6 6 6 6 6 6 1 1 2 4 5 3 4 5 6 2 3 4 1 2 2 3 4 5 6 6 6 5 4 2 1 3 4 4 6 6 6 6 5 5 4 3 2 1 5 6 5 4 3 2 2 1 1 1 6 6 6 6 6 6 1 1 2 4 5 3 4 5 6 2 3 4 1 2 2 3 4 5 6 6 6 5 4 2 1 3 4 4 6 6 6 6 5 5 4 3 2 1 5 6 5 4 3 2 2 1 1 1 6 6 6 6 6 6 1 1 2 4 5 3 4 5 6 2 3 4 1 2 2 3 4 5 6 6 6 5 4 2 1 3 4 4 6 6 6 6 5 5 4 3 2 1 5 6 5 4 3 2 2 1 1 1 6 6 6 6 6 6 1 1 2 4 5 3 4 5 6 2 3 4 1 2 2 3 4 5 6 6 6 5 4 2 1 3 4 4 6 6 6 6 5 5 4 3 2 1 5 6 5 4 3 2 2 1 1 1 6 6 6 6 6 6 1 1 2 4 5 3 4 5 6 2 3 4 1 2 2 3 4 5 6 6 6 5 4 2 1 3 4 4 6 6 6 6 5 5 4 3 2 1 5 6 5 4 3 2 2 1 1 1 6 6 6 6 6 6 1 1 2 4 5 3 4 5 6 2 3 4 1 2 2 3 4 5 6 6 6 5 4 2 1 3 4 4 6 6 6 6 5 5 4 3 2 1 5 6 5 4 3 2 2 1 1 1 6 6 6 6 6 6 1 1 2 4 5 3 4 5 6 2 3 4 1 2 2 3 4 5 6 6 6 5 4 2 1 3 4 4 6 6 6 6 5 5 4 3 2 1 5 6 5 4 3 2 2 1 1 1 6 6 6 6 6 6 1 1 2 4 5 3 4 5 6 2 3 4 1 2 2 3 4 5 6 6 6 5 4 2 1 3 4 4 6 6 6 6 5 5 4 3 2 1 5 6 5 4 3 2 2 1 1 1 6 6 6 6 6 6 1 1 2 4 5 3 4 5 6 2 3 4 1 2 2 3 4 5 6 6 6 5 4 2 1 3 4 4 6 6 6 6 5 5 4 3 2 1 5 6 5 4 3 2 2 1 1 1 6 6 6 6 6 6 1 1 2 4 5 3 4 5 6 2 3 4 1 2 2 3 4 5 6 6 6 5 4 2 1 3 4 4 6 6 6 6 5 5 4 3 2 1 5 6 5 4 3 2 2 1 1 1 6 6 6 6 6 6 1 1 2 4 5 3 4 5 6 2 3 4 1 2 2 3 4 5 6 6 6 5 4 2 1 3

Учет кодонов

Белок-Кодирующая

Некодирующая

Позиция в кодоне

1 2 3

P(A) 19.3% 28.8% 13.2%

P(C) 24.1% 33.4% 31.5%

P(G) 45.8% 19.3% 41.2%

P(T) 10.8% 18.4% 14.1%

​

​

P(A) = 20.4%

P(C) = 28.3%

P(G) = 32.8%

P(T) = 18.4%

Участок ДНК:

x = GCG

​

Можем ли мы сказать, белок-кодирующий он или нет?

Учет предыдущего нуклеотида – модель 1го порядка

Белок-Кодирующая

Некодирующая

Позиция в кодоне

1 2 3

P(A|A)

P(A|C)

P(A|G)

P(A|T)

P(C|A)

P(C|C)

P(C|G)

P(C|T)

…

​

​

P(A|A)

P(A|C)

P(A|G)

P(A|T)

P(C|A)

P(C|C)

P(C|G)

P(C|T)

…

Выдача программы GeneMark

Выдача программы GeneMark для 6 рамок

Что мы можем измерить ,чтобы использовать в модели?

• Большинство того, что мы знаем о последовательностях относится к белок-кодирующим характеристикам
• ORF (Open Reading Frame)/ОРС (открытая рамка считывания): последовательность определяемая по AUG и стоп кодон, что в свою очередь определяет последовательность аминокислот.
• Codon Usage/Использование кодонов: наиболее часто измеряется в CAI (Codon Adaptation Index/индекс адаптации кодонов)
• Другие явления
• Частоты и корреляции нуклеотидов:
• Функциональные сайты:
• сайты сплайсинга, промотеры, НТО, сайты полиаденилирования

Статистика кодирующей последовательности

• Неравное использование кодонов в кодирующих областях – универсальная характеристика геномов.

​

• Неравное использование аминокислот в существующих белках
• Неравное использование синонимичных кодонов (коррелирует с избытком соответствующих tRNAs)

​

• Эти характеристики могут быть использованы для разделения между кодирующими и некодирующими областями генома.

​

• Статистика кодирования – функция, которая для данной ДНК последовательности вычисляет правдоподобие (условную вероятность) того, что последовательность является кодирующей для белка

62

An Example of Coding Statistics

63

An Intron

3’ splice site

5’ splice site

revcomp(CT)=AG

revcomp(AC)=GT

GT: signals start of intron

AG: signals end of intron

Как нужно поменять модель чтобы предсказывать гены эукариот?

65

66

E₀

E₁

E₂

E₂

E₁

E₀

N

P

E_term

P

E_init

polyA

5’ UTR

I₀

I₁

I₂

I₀

I₁

I₂

E_sngl

E_sngl

E_init

E_term

forward strand

backward strand

3’ UTR

5’ UTR

3’ UTR

polyA

E- exons

I- introns

single exon

5’ UTRs

3’ UTRs

P- promoter region polyA site N- intergenic region

​

Для эукариот всё сложно.

Interpolated Markov Models (IMM)

• Introduced in Glimmer 1.0�Salzberg, Delcher, Kasif & White, NAR 26, 1998.
• Probability of the target position depends on a variable number of previous positions (sometimes 2 bases, sometimes 3, 4, etc.)
• How many is determined by the specific context.
• E.g., for context ggtta the next position might depend on previous 3 bases tta .

But for context catta all 5 bases might be used.

​

Real IMMs

• Model has additional probabilities, λ, that determine which parts of the context to use.
• E.g., the probability of g occurring after context atca is:

Real IMMs

• Result is a linear combination of different Markov orders:����where�
• Can view this as interpolating the results of different-order models.
• The probability of a sequence is still the probability of the bases in the sequence.

IMMs vs Fixed-Order Models

• Performance
• IMM generally should do at least as well as a fixed-order model.
• Some risk of overtraining.
• IMM result can be stored and used like a fixed-order model.
• IMM will be somewhat slower to train and will use more memory.

​

​

Target

Variable-Length�Context

GLIMMER-HMM

N^th-order interpolated Markov models (IMM) (N=8)

Какие гены существуют помимо генов кодирующих белок?

72

PGAP

• https://www.ncbi.nlm.nih.gov/refseq/annotation_prok/process/
• https://github.com/ncbi/pgap

73

Практика

Для генома бледной трепонемы

(возбудитель какой болезни?)

NC_000919.1

Запустить:

• Genemark
• обученный на e coli
• Обученный на трипаносоме
• Самообучающийся
• Glimmer

​

Практика

Для генома бледной трепонемы NC_000919.1

Запустить:

• Genemark
• обученный на e coli
• Обученный на трипаносоме
• Самообучающийся
• Glimmer

​

• Прокариоты https://bmcgenomics.biomedcentral.com/articles/10.1186/s12864-020-6707-9
• Эукариоты https://academic.oup.com/bioinformaticsadvances/article/3/1/vbad105/7240498

76

Другие программы и методы. Обзорные статьи