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

Одной из актуальных областей, в частности, является поиск консервативных подпоследовательностей или участков нуклеотидов, имитирующих промотор или островки CpG. Из-за того, сколько информации содержится в геноме человека, трудно сделать выводы о том, какие области были сохранены в результате эволюции или какие области осуществляют важные процессы в организме, такие как метилирование ДНК.

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

Рамки для моделирования ДНК

Когда нуклеотидная последовательность передается группе исследователей для выяснения функции самой последовательности (например, является ли она промотором, связанным с областями, кодирующими белок, и т. Д.), Часто используются три метода: выравнивание , визуализация и моделирование.

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

Посредством HMM мы займемся второй стратегией для сокращения времени выполнения вычислений и более быстрой доставки результатов. Мы не только посмотрим, что изображено на этих последовательностях, но и распознаем состояние, в котором возникло наблюдение.

Правило Бая и вероятностное моделирование

Скрытые марковские модели строго полагаются на правило Байя и формулы вероятности для выполнения расчетов и вывода правильной последовательности. Поэтому уместно знать основы, прежде чем углубляться в эту тему.

Приведенная выше формула жизненно важна для понимания того, как меняется вероятность события с учетом новой информации. Обозначение P (A | B) описывает вероятность возникновения события A, исходя из предположения, что событие B уже произошло.

Точный вывод формулы не имеет отношения к использованию в этой статье; однако понимание этого правила и того, как оно работает, необходимо, поскольку оно играет большую роль в самих скрытых марковских моделях. Обратите внимание, что правило Байя может постоянно дополняться в зависимости от новой предоставленной информации.

Интуиция, лежащая в основе цепей Маркова и HMM

HMM можно описать через два состояния: t скрытое и наблюдаемое. Скрытое состояние - это то, что вызывает эти выбросы и приводит к вышеупомянутым наблюдениям, которые показаны выше.

Пример можно показать на примере того, как времена года влияют на погоду. В этом случае наблюдаемые состояния будут состоять в том, солнечно или идет дождь, а скрытыми состояниями будет сам сезон. Обратите внимание на то, что время года имеет заранее определенную вероятность того, будет ли дождь или нет. Такие сезоны, как осень, имеют большую вероятность дождя, чем такие события, как лето.

В приведенном выше примере определите выбросы / наблюдения как набор солнца, дождя, облаков и снега, а скрытые состояния - это времена года (лето, осень, зима и весна). Как показано ниже, они могут быть определены векторами pi и x соответственно. Также представлены вероятности перехода (то есть вероятности перехода одного скрытого состояния в другое скрытое состояние).

Эти вероятности перехода также часто генерируются на основе предопределенных пользователем входных данных. Он определяется как вероятность входа в это скрытое состояние с учетом вероятности того, что предыдущее состояние является скрытым состоянием k.

Эти цепи Маркова являются шагом внутри общей HMM, и их часто определяют как триплет (Q, p, A), где Q представляет собой набор состояний, A - матрица переходных вероятностей, p - вектор начальных вероятностей. Позже мы более подробно рассмотрим начальные вероятности.

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

Разница между цепями Маркова и HMM

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

В скрытых марковских моделях эти наблюдения или выбросы будут результатом определенного набора вероятностей. Состояния будут скрыты от наблюдателя, и будут наблюдаться наблюдения, генерируемые с определенной вероятностью в каждом состоянии (часто называемые вероятностями излучения).

Проще говоря, HMM используются, когда наблюдения / выбросы происходят из набора состояний из систем, которые мы не можем наблюдать. Это отличается от цепей Маркова, которые уже имеют предопределенные состояния.

Математические обозначения HMM

Скрытые марковские модели формально определяются как 5-кортеж (Q, A, p, V, E) по сравнению с трехкортежной марковской цепью, где V - набор символов наблюдения (обычно набор нуклеотидных оснований или аминокислот), а E - матрица вероятностей эмиссии, часто определяемая как:

Пример HMM

Предопределенная модель HMM обычно будет выглядеть так, как показано выше. Для каждого азотистого основания существует корреляционная зависимость вероятности, которая показывает, насколько вероятно, что скрытое состояние выделяет это определенное азотистое основание.

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

Обратите внимание, что есть три возможности: скрытое состояние не изменяется от собственного состояния, скрытое состояние не изменяется от состояния вируса и скрытое состояние изменения из собственного и вирусного состояний.

Эта последняя вероятность, однако, часто не рекомендуется, поскольку вероятности перехода между различными состояниями часто ниже, чем вероятности перехода, которые просто возвращаются в одно и то же состояние (например, вероятность перехода Self → Virus составляет 0,05, а вероятность перехода Self → Self равна 0,95).

Чтобы вычислить вышеупомянутую вероятность этих состояний и наблюдаемых выбросов, нам нужно взять произведение трех членов:

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

Его часто определяют как P (x, pi) = P (x | pi) P (pi), как указано в нашем правиле Байя, где x - это вектор эмиссии, а pi - скрытый вектор.

Короче говоря, вероятность наличия вероятности излучения при определенном состоянии (то есть P (x, pi)) представляет собой произведение вероятности начального состояния и вероятностей излучения и перехода в зависимости от вектора излучения.

Пример расчета вероятности

Если взять пример pi = {S, S, S, S, S} и x = {A, T, C, G, A}, где S указывает, что используется самосостояние, то мы можем вычислить совместную вероятность наличия как pi, так и x:

P (x, pi) = (0.5) x (0.25)⁵ x (0.95)⁴ = 3.977 x 10^(-4)

Обратите внимание, что это было просто умножением вышеупомянутой начальной вероятности, вероятностей перехода и вероятностей выбросов.

Эти вероятностные вычисления обычно невелики из-за того, как много маленьких чисел умножаются друг на друга. Мы часто просто смотрим на то, что с наибольшей вероятностью, и считаем, что это наиболее вероятное состояние.

Интерпретация вероятностей HMM

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

Таким образом, HMM перебирает все 32 комбинации, чтобы найти наиболее вероятное состояние (т. Е. Состояние с наибольшей совместной вероятностью). Обратите внимание, что эти 32 комбинации также включают вероятности перехода между разными состояниями.

Следовательно, необходимо использовать обобщенное предположение о 2 ^ n наборах скрытых состояний в зависимости от последовательности излучения длиной n. Как было замечено ранее, это может стать сложным в вычислительном отношении даже с последовательностями, состоящими всего из 100 пар оснований. Следовательно, необходимы более жесткие методы анализа.

GC-богатые регионы с HMM

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

HMM являются революционными, поскольку они могут предсказывать потенциальные интроны, экзоны, факторы транскрипции и т. Д. Только на одном фрагменте ДНК. В частности, для наших целей мы будем рассматривать богатые GC регионы для моделирования этих последовательностей.

GC-богатые регионы и CpG-острова

Эти области часто называют GC-богатыми, если они заполнены цитозином и гуанином (двумя комплементарными азотистыми основаниями).

Их часто определяют как области с менее 200 пар оснований, процентным содержанием GC более 50% и соотношением наблюдаемого и ожидаемого CpG более 60%. Обратите внимание, что эти числа могут быть реализована в нашей модели HMM для проверки конкретных островков CpG.

Используя наше понимание ТММ, мы можем сказать, что в этих богатых ГЦ регионах вероятность эмиссии цитозина и гуанина будет выше, чем у аденина и тимина. Часто эти промоторные области имеют вероятности 30% и 42% для G и C и просто 15% и 13% для A и T.

Основываясь на вероятностях эмиссии, мы теперь хотим найти оптимальное состояние (которое состоит из областей промотора или CpG и областей без промотора или фона), которое максимизирует общую совместную вероятность скрытых состояний и состояний излучения.

Это можно сделать с помощью динамического программирования, которое будет обсуждаться позже в этой статье.

Опять же, говоря о проблеме, обсуждавшейся ранее, максимальную совместную вероятность становится все труднее вычислить по мере увеличения длины последовательности, поэтому необходимо использовать динамическое программирование, чтобы сократить время выполнения вычислений HMM.

Расшифровка наиболее вероятного пути - алгоритм Витерби

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

Динамическое программирование направлено на разбиение проблемы на более мелкие подкатегории, например рекурсивный цикл. Обычно они используются для задач оптимизации, поскольку оптимальное решение проблемы зависит также от оптимального решения для самих подзадач.

Алгоритмы, подобные алгоритму Нидлмана-Вунша, используют динамическое программирование для поиска похожих нуклеотидных последовательностей (с учетом вставок, делеций и мутаций); для получения дополнительной информации ознакомьтесь с этой статьей.

Наша основная цель для этой проблемы - попытаться найти наиболее вероятные состояния на основе наблюдений или вероятностей выбросов. Обратите внимание, что в этой задаче указаны вероятности выбросов (E), вероятности перехода (a) и последовательность выбросов (x). Мы пытаемся найти последовательность скрытых состояний (пи), которая максимизирует совместную вероятность с учетом этих выбросов, или находим

Обратите внимание, что для решения этой проблемы можно использовать динамическое программирование, поскольку лучший путь может быть получен вне лучшего пути из предыдущих состояний; нам просто нужно сформировать рекуррентное отношение, чтобы найти оптимальный путь. Пусть v (i) будет известной вероятностью наиболее вероятного пути, который заканчивается в позиции i для определенного состояния. Это повторение определяется как:

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

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

Вот четыре основных шага алгоритма Витерби (математически):

Первый шаг, инициализация, присваивает начальному столбцу вероятность, равную единице (поскольку на нем не умножались вероятности эмиссии или перехода), в то время как все остальные столбцы k имеют вероятности нуль.

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

На третьем этапе, завершение, выполняется поиск наилучшего пути путем отслеживания с возвратом до тех пор, пока не будет найден наиболее оптимальный путь последовательности путей; это тот, у которого наибольшая максимальная вероятность прохождения до первого столбца.

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

С помощью K состояний и N состояний излучения мы можем сказать, что существует пространственная сложность O (KN) и временная сложность O (K²N), что намного лучше, чем экспоненциальное время выполнения алгоритма грубой силы.

Декодирование по всем путям

Дальнейшие исследования были проведены в области декодирования по всем путям, где мы находим путь состояний pi *, который содержит наиболее вероятное состояние в каждый момент времени. Это означает состояние, которое имеет самую низкую мультипликативную вероятность (включая предыдущие вероятности, а также вероятности перехода и выбросов).

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

Примечание. Апостериорное декодирование может дать неверную последовательность состояний, потому что оно не учитывает вероятность переходов между состояниями, а в большей степени делает это для каждой позиции независимо.

Апостериорное декодирование и алгоритм Витерби имеют свои сильные и слабые стороны; однако алгоритм Витерби чаще всего используется для вывода функций на основе нуклеотидных последовательностей.

Апостериорное декодирование не имеет отношения к целям нашей статьи, поэтому мы не будем его обсуждать; однако более подробную информацию можно найти здесь.

Оценка по нескольким путям

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

Аналогичный подход можно использовать и для оценки по нескольким путям. Мы часто используем этот показатель, если нас особенно интересует знание вероятности конкретной последовательности с учетом скрытой марковской модели.

Вместо того, чтобы сосредотачиваться на скрытых состояниях, он вместо этого фокусируется на наблюдаемых состояниях, просто суммируя все 2 ^ n скрытых наборов друг с другом. Вероятность всех путей pi скрытых состояний данной последовательности наблюдений определяется формулой:

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

Это соответствует процессу инициализации и итерации, аналогичному алгоритму Витерби; однако вместо того, чтобы брать максимум предыдущей вероятности и вероятности перехода, вместо этого используется суммирование.

Этот итерационный процесс учитывает все имеющиеся вероятности путем умножения вероятностей перехода и выбросов во всех столкновениях. Наконец, он завершается суммированием вероятностей всех элементов для получения окончательной совместной вероятности. Он задается тем же пробелом:

Алгоритмические сравнения

Эти алгоритмы играют важную роль в оценке и декодировании с помощью этих скрытых марковских моделей. Дополнительные контролируемые и неконтролируемые модели могут быть приняты во внимание, чтобы сделать этот процесс более продуктивным; однако это не будет обсуждаться для целей данной статьи.

Дополнительные сведения о тактике контролируемого и неконтролируемого обучения для определения функций нуклеотидных последовательностей см. В алгоритме Баума-Велча и обучении Витерби. Более подробную информацию можно найти здесь".

Геномные приложения

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

Острова CpG и HMM

Островки CpG, или области, которые имеют пары нуклеотидов C и G на цепи, являются основным направлением этой статьи. Когда он присутствует в геноме, он часто становится метилированным, когда дезаминирование цитозина приводит к тимину (вызывая мутацию C в T).

Из-за этого метилирования эти CpG-островки истощаются с течением времени, и они часто встречаются редко из-за высокой частоты мутаций цитозинов. Однако, когда они находятся рядом с активным промотором, эта функция метилирования может быть подавляются, и CpG-островки обычно выживают.

Следовательно, обнаружение этих CpG-островков может выявить определенные промоторные области внутри генома человека. Традиционные применения использования рамок считывания для обнаружения высоких уровней Cs и G устарели, поскольку слишком маленькое окно может не захватить островок CpG, в то время как слишком большое окно может привести к тому, что островок CpG будет пропущен. Следовательно, HMM являются ключом к моделированию этого.

Одна проблема, которая часто сохраняется с этими марковскими моделями, - это проблема переобучения при увеличении этих параметров, что может переобучать данные и приводить к снижению точности. Следовательно, необходимо сокращение параметров, либо сделав все вероятности переходов одинаковыми, либо просто сделав переходы в состояниях, на которых мы сосредоточены.

Резюме

HMM становятся новым методом в области биоинформатики для определения функций нуклеотидных последовательностей с помощью правила Бая и расчетов вероятностей. HMM часто имеют скрытое состояние и наблюдаемое состояние, где конкретное скрытое состояние имеет вероятность испустить определенное наблюдаемое состояние, часто обозначаемое как вероятность излучения.

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

И наоборот, путем декодирования функций на основе нуклеотидных последовательностей: можно использовать два подхода. Алгоритм Витерби может использоваться для поиска наиболее вероятного скрытого пути между нуклеотидной последовательностью, в то время как апостериорное декодирование может использоваться для поиска пути, содержащего наиболее вероятное состояние (не путь) в любой момент времени.

Чтобы сделать этот подход более продуктивным и менее предопределенным, можно использовать дополнительные методы машинного обучения с помощью обучения Витерби и Баума-Велча.

Дополнительные ресурсы

Привет! Мне 16 лет, и я интересуюсь машинным обучением и биотехнологиями. Если вы хотите видеть больше моего контента и того, что я публикую, подумайте о подписке на мою рассылку новостей! Ознакомьтесь с моим мартовским информационным бюллетенем здесь! Также загляните на мои страницы LinkedIn и Github. Если вас интересует личное мышление или что-то в целом, зарегистрируйтесь в чате, используя мой Calendly.