Для начала введем некоторое определение: марковская цепь — это цепь событий,

в котором следующие события не зависят от прошлых, кроме как через настоящее.

Это значит, что если у вас есть одно событие, то следующее событие зависит

от того, что произошло в первый момент времени, третье событие зависит от того,

что произошло во второй момент времени, но не зависит от первого момента.

Таким образом, будущее зависит от прошлого только через настоящее.

Например, если у вас есть некоторая точка в пространстве,

и вам известно ее местоположение и скорость, то вы можете определить,

где она будет в следующий момент времени в пространстве,

если ее скорость не меняется.

При этом вам не обязательно знать, что происходило раньше.

Такой...

Такая цепь событий называется марковской цепью, и часто применяется

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

достаточно простых моделей, в которых будущее зависит только от какого-то

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

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

В биоинформатике часто используется такое понятие как

скрытая марковская модель или hidden markov model.

Вы будете встречать такую аббревиатуру в названии некоторых программ, например,

HMMER, Glimmer и GeneMark.hmm Что такое скрытая марковская модель?

Это некоторый граф из состояний, который

нам на самом деле не всегда известен, поэтому она и скрытая марковская модель.

Но часто нам известна структура графа.

На ней известны параметры переходов между вершинами этого графа.

Итак, у нас,

например, известно, что есть состояние ген и не-ген.

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

то есть это граф из двух вершин и двух ребер.

На самом деле ребер там не два,

а четыре, потому что из состояния можно перейти в самого себя,

то есть остаться в том же самом состоянии в какой-то момент времени.

И на ребрах у нас написаны вероятности.

Например, 0.1, что мы перейдем из состояния ген в состояние не-ген,

и 0.9, что мы останемся в наших исходных состояниях.

Ну, и 0.1 обратно из не-гена в ген.

Такая скрытая марковская модель также может выпускать,

— называется emission, — некоторые символы, которые мы наблюдаем.

То есть мы часто не наблюдаем состояние этой модели в каждое конкретное время,

но мы можем наблюдать выход, — то, что печатает, можно сказать, эта модель.

В частности, в состоянии ген эта модель может выпускать тройки символов,

которые отвечают кодонам, и распределены с той же вероятностью,

с которой эти кодоны встречаются внутри генов.

Например, ATG, скажем, это просто некоторые случайные вероятности.

ATG 1%, AAA 3% и так далее, а в состоянии

не-ген мы печатаем такие тройки нуклеотидов с другими вероятностями,

например, ATG печатается с вероятностью 0.1%,

a AAA печатается с вероятностью 10%, допустим.

Это некоторые случайные вероятности,

которые не соответствуют действительно в организмах, но они разные, так как и...

Они действительно разные в организмах И, перемещаясь внутри этой модели,

например, мы начинаем в состоянии не-ген, бросаем кубик,

определяем, какой — в зависимости от того, что упало на кубике от 0 до

1 в процентах — мы определяем, какой кодон нам нужно вывести, например, ААА.

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

либо остаемся в состоянии не-ген, либо перемещаемся в состояние ген.

Допустим, мы остались тут.

После этого бросили еще раз кубик, который говорит нам,

какой кодон вывести, например, ATG.

И снова попытались сделать переход.

Мы либо остались, либо перешли в ген.

Например, мы перешли в ген.

После этого снова бросаем кубик.

Получается, допустим, снова ААА и так далее.

Мы обычно наблюдаем тольтко последовательность,

которую выпускает такая скрытая марковская модель.

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

написаны некоторой моделью, которая содержала два состояния ген или не-ген.

Когда мы внутри гена, то мы с большей вероятностью выдаем те кодоны,

которые соответствуют распределению кодона внутри гена.

Когда мы находимся вне гена,

мы их выдаем с вероятностью похожей на вероятность кодонов вне гена.

При этом, если мы находимся в какой-то момент времени в гене,

то в следующий момент времени, скорее всего, мы тоже останемся внутри гена,

потому что ген имеет некоторую длину продолжительную.

Если мы находимся вне гена, то,

скорее всего, вокруг также гена нету, но есть вероятность, что ген начнется.

Ну, в данном случае у нас это 10%.

И есть вероятность, что ген закончится.

В данном случае это тоже 10%.

Это пример достаточно простой марковской модели.

На самом деле марковские модели чуть более сложные, и состояний в них часто больше,

но в целом в них есть некоторые состояния, переходы между

состояниями с вероятностями, которые написаны на эти переходах,

а также выпускаемые символы из некоторого алфавита.

В данном случае у нас алфавит кодонов, и выпускаемые символы имеют вероятность.

То есть в каждом состоянии у нас есть некоторая вероятность выпустить

некоторые символы.

Марковские модели, и в частности скрытые марковские модели,

являются частным случаем алгоритмов машинного обучения.

Таким образом, если у вас есть геном и некоторые уже известные в нем гены,

вы можете скрытую марковскую модель обучить, то есть определить параметры,

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

переходов и вероятности выпуска символов в каждом состоянии по известным данным,

и применять эту марковскую модель для нахождения новых генов.

И, обучившись на известных генах или на известных геномах и известных аннотациях,

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

что, да, наверное, это тоже ген, потому что он суммарно похож на все другие гены,

которые мы видели раньше по целому набору статистических признаков.

При этом при обучении и при построении такой модели есть много вариаций.

Есть разные алгоритмы обучения,

в том числе когда у нас есть геномы с хорошей разметкой на гены.

Также существуют алгоритмы unsupervised learning, то есть обучение без учителя,

когда нам просто даны геномы, но неизвестно, что в них является генами или

нет, но просто из неоднородности этих геномов можно уже найти некоторые участки,

которые явно отличаются от всего генома.

То есть, если у вас даже дана одна строка, один геном, в котором вы знаете,

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

они отличаются от мусорной ДНК, и от их от других участков, то марковские модели,

обучившись на такой последовательности, могут находить эти неоднородности.

При этом построение марковской модели, вот именно спецификация состояний,

которые в ней находятся, это достаточно сложный творческий процесс, так же как

и построение алгоритмов, поэтому разные программы внутри себя содержат разные

марковские модели по структуре, но по идее и алгоритмам они очень схожи, то

есть они все обучаются примерно одинаково и применяются примерно одинаково,

но набор состояний, переходов иногда варьируется от программы к программе.

Примеры программ, которые используются для поиска генов de novo и используют

скрытые марковские модели, это HMMER, Glimmer,

также GeneMark.hmm использует скрытые марковские модели.

Для многих из этих программ уже существуют предподсчитаные модели для

некоторых организмов.

Скажем, если у вас прокариотический организм с определенным GC-составом,

то вы можете взять уже GeneMark и конкретную модель для прокариотов, скажем,

с GC 40% и примерить ее для поиска генов de novo в вашем организме,

потому что эта модель, скрытая марковская модель,

уже обучена на многих прокариотах с GC равным

40% и работает похоже и достаточно хорошо на аналогичных организмах.

Таким образом, вам часто не нужно обучать такую скрытую марковскую модель самим.

Важно подобрать и использовать уже существующую хорошую модель

и просто применить ее для вашего организма, для ваш...

для геномов, для контигов, которые вы собрали ранее,

и в результате вы получите аннотацию, то есть разметку этих контигов на участки,

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

Теперь рассмотрим применение этих программ на практике.

Скрытые марковские модели (Hidden Markov Models)

Введение в биоинформатику (Introduction to Bioinformatics)

与讲师见面