Алгоритм Баума – Велча - Baum–Welch algorithm

В электротехника, Информатика, статистические вычисления и биоинформатика, то Алгоритм Баума – Велча это частный случай EM алгоритм используется для поиска неизвестных параметров скрытая марковская модель (ХМ). Он использует вперед-назад алгоритм для вычисления статистики для шага ожидания.

История

Алгоритм Баума – Велча был назван в честь его изобретателей. Леонард Э. Баум и Ллойд Р. Велч. Алгоритм и скрытые марковские модели были впервые описаны в серии статей Баума и его коллег в Институт оборонного анализа в конце 1960-х - начале 1970-х гг.^[1] Одно из первых крупных применений HMM было в области обработка речи.^[2] В 1980-х годах ТММ становились полезным инструментом в анализе биологических систем и информации, и в частности генетическая информация.^[3] С тех пор они стали важным инструментом вероятностного моделирования геномных последовательностей.^[4]

Описание

А скрытая марковская модель описывает совместную вероятность набора "скрытый "и наблюдаемые дискретные случайные величины. Он основан на предположении, что я-я скрытая переменная с учетом (я - 1) -я скрытая переменная не зависит от предыдущих скрытых переменных, а текущие переменные наблюдения зависят только от текущего скрытого состояния.

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

Позволять ${\displaystyle X_{t}}$ дискретная скрытая случайная величина с ${\displaystyle N}$ возможные значения (т.е. мы предполагаем, что есть ${\displaystyle N}$ штатов всего). Мы предполагаем ${\displaystyle P(X_{t}\mid X_{t-1})}$ не зависит от времени ${\displaystyle t}$, что приводит к определению не зависящей от времени матрицы стохастических переходов

${\displaystyle A=\{a_{ij}\}=P(X_{t}=j\mid X_{t-1}=i).}$

Распределение начального состояния (т.е. когда ${\displaystyle t=1}$) дан кем-то

${\displaystyle \pi _{i}=P(X_{1}=i).}$

Переменные наблюдения ${\displaystyle Y_{t}}$ может взять один из ${\displaystyle K}$ возможные значения. Мы также предполагаем, что наблюдение в «скрытом» состоянии не зависит от времени. Вероятность определенного наблюдения ${\displaystyle y_{i}}$ вовремя ${\displaystyle t}$ для государства ${\displaystyle X_{t}=j}$ дан кем-то

${\displaystyle b_{j}(y_{i})=P(Y_{t}=y_{i}\mid X_{t}=j).}$

Принимая во внимание все возможные значения ${\displaystyle Y_{t}}$ и ${\displaystyle X_{t}}$, получаем ${\displaystyle N\times K}$ матрица ${\displaystyle B=\{b_{j}(y_{i})\}}$ куда ${\displaystyle b_{j}}$ принадлежит всем возможным состояниям и ${\displaystyle y_{i}}$ принадлежит всем наблюдениям.

Последовательность наблюдений определяется выражением ${\displaystyle Y=(Y_{1}=y_{1},Y_{2}=y_{2},\ldots ,Y_{T}=y_{T})}$.

Таким образом, мы можем описать скрытую цепь Маркова с помощью ${\displaystyle \theta =(A,B,\pi )}$. Алгоритм Баума – Велча находит локальный максимум для ${\displaystyle \theta ^{*}=\operatorname {arg\,max} _{\theta }P(Y\mid \theta )}$ (т.е. параметры HMM ${\displaystyle \theta }$ которые увеличивают вероятность наблюдения).^[5]

Алгоритм

Набор ${\displaystyle \theta =(A,B,\pi )}$ со случайными начальными условиями. Их также можно установить с использованием предварительной информации о параметрах, если она доступна; это может ускорить алгоритм, а также направить его к желаемому локальному максимуму.

Форвардная процедура

Позволять ${\displaystyle \alpha _{i}(t)=P(Y_{1}=y_{1},\ldots ,Y_{t}=y_{t},X_{t}=i\mid \theta )}$, вероятность увидеть наблюдения ${\displaystyle y_{1},y_{2},\ldots ,y_{t}}$ и находясь в состоянии ${\displaystyle i}$ вовремя ${\displaystyle t}$. Это находится рекурсивно:

1. ${\displaystyle \alpha _{i}(1)=\pi _{i}b_{i}(y_{1}),}$
2. ${\displaystyle \alpha _{i}(t+1)=b_{i}(y_{t+1})\sum _{j=1}^{N}\alpha _{j}(t)a_{ji}.}$

Поскольку этот ряд экспоненциально сходится к нулю, алгоритм будет численно пропадать для более длинных последовательностей.^[6] Однако этого можно избежать в слегка модифицированном алгоритме, масштабируя ${\displaystyle \alpha }$ в форварде и ${\displaystyle \beta }$ в обратной процедуре ниже.

Обратная процедура

Позволять ${\displaystyle \beta _{i}(t)=P(Y_{t+1}=y_{t+1},\ldots ,Y_{T}=y_{T}\mid X_{t}=i,\theta )}$ это вероятность окончания частичной последовательности ${\displaystyle y_{t+1},\ldots ,y_{T}}$ данное начальное состояние ${\displaystyle i}$ вовремя ${\displaystyle t}$. Мы рассчитываем ${\displaystyle \beta _{i}(t)}$ в качестве,

1. ${\displaystyle \beta _{i}(T)=1,}$
2. ${\displaystyle \beta _{i}(t)=\sum _{j=1}^{N}\beta _{j}(t+1)a_{ij}b_{j}(y_{t+1}).}$

Обновлять

Теперь мы можем вычислить временные переменные согласно теореме Байеса:

${\displaystyle \gamma _{i}(t)=P(X_{t}=i\mid Y,\theta )={\frac {P(X_{t}=i,Y\mid \theta )}{P(Y\mid \theta )}}={\frac {\alpha _{i}(t)\beta _{i}(t)}{\sum _{j=1}^{N}\alpha _{j}(t)\beta _{j}(t)}},}$

что вероятность нахождения в состоянии ${\displaystyle i}$ вовремя ${\displaystyle t}$ учитывая наблюдаемую последовательность ${\displaystyle Y}$ и параметры ${\displaystyle \theta }$

${\displaystyle \xi _{ij}(t)=P(X_{t}=i,X_{t+1}=j\mid Y,\theta )={\frac {P(X_{t}=i,X_{t+1}=j,Y\mid \theta )}{P(Y\mid \theta )}}={\frac {\alpha _{i}(t)a_{ij}\beta _{j}(t+1)b_{j}(y_{t+1})}{\sum _{k=1}^{N}\sum _{w=1}^{N}\alpha _{k}(t)a_{kw}\beta _{w}(t+1)b_{w}(y_{t+1})}},}$

что вероятность нахождения в состоянии ${\displaystyle i}$ и ${\displaystyle j}$ во время ${\displaystyle t}$ и ${\displaystyle t+1}$ соответственно, учитывая наблюдаемую последовательность ${\displaystyle Y}$ и параметры ${\displaystyle \theta }$.

Знаменатели ${\displaystyle \gamma _{i}(t)}$ и ${\displaystyle \xi _{ij}(t)}$ одинаковые ; они представляют собой вероятность проведения наблюдения ${\displaystyle Y}$ учитывая параметры ${\displaystyle \theta }$.

Параметры скрытой марковской модели ${\displaystyle \theta }$ теперь можно обновить:

• ${\displaystyle \pi _{i}^{*}=\gamma _{i}(1),}$

что является ожидаемой частотой нахождения в состоянии ${\displaystyle i}$ вовремя ${\displaystyle 1}$.

• ${\displaystyle a_{ij}^{*}={\frac {\sum _{t=1}^{T-1}\xi _{ij}(t)}{\sum _{t=1}^{T-1}\gamma _{i}(t)}},}$

что является ожидаемым количеством переходов из состояния я заявить j по сравнению с ожидаемым общим количеством переходов из состояния я. Чтобы уточнить, количество переходов из состояния я не означает переходы в другое состояние j, но в любое состояние, включая себя. Это эквивалентно тому, сколько раз состояние я наблюдается в последовательности от т = От 1 до т = Т − 1.

• ${\displaystyle b_{i}^{*}(v_{k})={\frac {\sum _{t=1}^{T}1_{y_{t}=v_{k}}\gamma _{i}(t)}{\sum _{t=1}^{T}\gamma _{i}(t)}},}$

куда

${\displaystyle 1_{y_{t}=v_{k}}={\begin{cases}1&{\text{if }}y_{t}=v_{k},\\0&{\text{otherwise}}\end{cases}}}$

- индикаторная функция, а ${\displaystyle b_{i}^{*}(v_{k})}$ ожидаемое количество раз, когда выходные наблюдения были равны ${\displaystyle v_{k}}$ в то время как в состоянии ${\displaystyle i}$ больше ожидаемого общего количества раз в состоянии ${\displaystyle i}$.

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

Примечание: Возможна перегрузка определенного набора данных. То есть, ${\displaystyle P(Y\mid \theta _{\text{final}})>P(Y\mid \theta _{\text{true}})}$. Алгоритм также делает нет гарантировать глобальный максимум.

Несколько последовательностей

Алгоритм, описанный до сих пор, предполагает одну наблюдаемую последовательность ${\displaystyle Y=y_{1},\ldots ,y_{N}}$. Однако во многих ситуациях наблюдается несколько последовательностей: ${\displaystyle Y_{1},\ldots ,Y_{R}}$. В этом случае информация из всех наблюдаемых последовательностей должна использоваться при обновлении параметров. ${\displaystyle A}$, ${\displaystyle \pi }$, и ${\displaystyle b}$. Предполагая, что вы вычислили ${\displaystyle \gamma _{ir}(t)}$ и ${\displaystyle \xi _{ijr}(t)}$ для каждой последовательности ${\displaystyle y_{1,r},\ldots ,y_{N_{r},r}}$, теперь можно обновить параметры:

• ${\displaystyle \pi _{i}^{*}={\frac {\sum _{r=1}^{R}\gamma _{ir}(1)}{R}}}$
• ${\displaystyle a_{ij}^{*}={\frac {\sum _{r=1}^{R}\sum _{t=1}^{T-1}\xi _{ijr}(t)}{\sum _{r=1}^{R}\sum _{t=1}^{T-1}\gamma _{ir}(t)}},}$
• ${\displaystyle b_{i}^{*}(v_{k})={\frac {\sum _{r=1}^{R}\sum _{t=1}^{T}1_{y_{tr}=v_{k}}\gamma _{ir}(t)}{\sum _{r=1}^{R}\sum _{t=1}^{T}\gamma _{ir}(t)}},}$

куда

${\displaystyle 1_{y_{tr}=v_{k}}={\begin{cases}1&{\text{if }}y_{t,r}=v_{k},\\0&{\text{otherwise}}\end{cases}}}$

индикаторная функция

Пример

Предположим, у нас есть курица, из которой мы собираем яйца каждый день в полдень. Теперь, отложила ли курица яйца для сбора, зависит от некоторых скрытых неизвестных факторов. Однако мы можем (для простоты) предположить, что есть только два состояния, которые определяют, откладывает ли курица яйца. Теперь мы не знаем состояние в начальной начальной точке, мы не знаем вероятностей перехода между двумя состояниями и мы не знаем вероятность того, что курица снесет яйцо при конкретном состоянии.^[7][8] Для начала угадываем матрицы перехода и излучения.

Переход Состояние 1 Состояние 2 Состояние 1 0.5 0.5 Состояние 2 0.3 0.7

Эмиссия Без яиц Яйца Состояние 1 0.3 0.7 Состояние 2 0.8 0.2

Исходный Состояние 1 0.2 Состояние 2 0.8

Затем мы берем набор наблюдений (E = яйца, N = нет яиц): N, N, N, N, N, E, E, N, N, N

Это дает нам набор наблюдаемых переходов между днями: NN, NN, NN, NN, NE, EE, EN, NN, NN.

Следующим шагом является оценка новой матрицы перехода. Например, вероятность того, что последовательность NN и состояние будут ${\displaystyle S_{1}}$ тогда ${\displaystyle S_{2}}$ дается следующим образом,${\displaystyle P(S_{1})*P(N|S_{1})*P(S_{1}\rightarrow S_{2})*P(N|S_{2}).}$

Наблюдаемая последовательность	Вероятность последовательности и состояния равна ${\displaystyle S_{1}}$ тогда ${\displaystyle S_{2}}$	Наивысшая вероятность наблюдения этой последовательности
NN	0.024 = 0.2 * 0.3 * 0.5 * 0.8	0.3584	${\displaystyle S_{2}}$,${\displaystyle S_{2}}$
NN	0.024 = 0.2 * 0.3 * 0.5 * 0.8	0.3584	${\displaystyle S_{2}}$,${\displaystyle S_{2}}$
NN	0.024 = 0.2 * 0.3 * 0.5 * 0.8	0.3584	${\displaystyle S_{2}}$,${\displaystyle S_{2}}$
NN	0.024 = 0.2 * 0.3 * 0.5 * 0.8	0.3584	${\displaystyle S_{2}}$,${\displaystyle S_{2}}$
NE	0.006 = 0.2 * 0.3 * 0.5 * 0.2	0.1344	${\displaystyle S_{2}}$,${\displaystyle S_{1}}$
EE	0.014 = 0.2 * 0.7 * 0.5 * 0.2	0.0490	${\displaystyle S_{1}}$,${\displaystyle S_{1}}$
EN	0.056 = 0.2 * 0.7 * 0.5 * 0.8	0.0896	${\displaystyle S_{2}}$,${\displaystyle S_{2}}$
NN	0.024 = 0.2 * 0.3 * 0.5 * 0.8	0.3584	${\displaystyle S_{2}}$,${\displaystyle S_{2}}$
NN	0.024 = 0.2 * 0.3 * 0.5 * 0.8	0.3584	${\displaystyle S_{2}}$,${\displaystyle S_{2}}$
Общий	0.22	2.4234

Таким образом, новая оценка ${\displaystyle S_{1}}$ к ${\displaystyle S_{2}}$ переход сейчас ${\displaystyle {\frac {0.22}{2.4234}}=0.0908}$ (в следующих таблицах именуются «псевдовероятностями»). Затем мы вычисляем ${\displaystyle S_{2}}$ к ${\displaystyle S_{1}}$, ${\displaystyle S_{2}}$ к ${\displaystyle S_{2}}$ и ${\displaystyle S_{1}}$ к ${\displaystyle S_{1}}$ вероятности перехода и нормализуются, поэтому они прибавляются к 1. Это дает нам обновленную матрицу перехода:

Старая матрица перехода Состояние 1 Состояние 2 Состояние 1 0.5 0.5 Состояние 2 0.3 0.7

Новая матрица перехода (псевдовероятности) Состояние 1 Состояние 2 Состояние 1 0.0598 0.0908 Состояние 2 0.2179 0.9705

Новая матрица перехода (после нормализации) Состояние 1 Состояние 2 Состояние 1 0.3973 0.6027 Состояние 2 0.1833 0.8167

Затем мы хотим оценить новую матрицу выбросов,

Наблюдаемая последовательность	Наивысшая вероятность наблюдения этой последовательности если предполагается, что E происходит из ${\displaystyle S_{1}}$		Наивысшая вероятность наблюдения этой последовательности
NE	0.1344	${\displaystyle S_{2}}$,${\displaystyle S_{1}}$	0.1344	${\displaystyle S_{2}}$,${\displaystyle S_{1}}$
EE	0.0490	${\displaystyle S_{1}}$,${\displaystyle S_{1}}$	0.0490	${\displaystyle S_{1}}$,${\displaystyle S_{1}}$
EN	0.0560	${\displaystyle S_{1}}$,${\displaystyle S_{2}}$	0.0896	${\displaystyle S_{2}}$,${\displaystyle S_{2}}$
Общий	0.2394		0.2730

Новая оценка E, полученная от ${\displaystyle S_{1}}$ эмиссия сейчас ${\displaystyle {\frac {0.2394}{0.2730}}=0.8769}$.

Это позволяет нам рассчитать матрицу выбросов, как описано выше в алгоритме, путем сложения вероятностей для соответствующих наблюдаемых последовательностей. Затем мы повторяем, если N пришло из ${\displaystyle S_{1}}$ и если N и E пришли из ${\displaystyle S_{2}}$ и нормализовать.

Старая матрица выбросов Без яиц Яйца Состояние 1 0.3 0.7 Состояние 2 0.8 0.2

Новая матрица выбросов (оценки) Без яиц Яйца Состояние 1 0.0404 0.8769 Состояние 2 1.0000 0.7385

Новая матрица выбросов (после нормализации) Без яиц Яйца Состояние 1 0.0441 0.9559 Состояние 2 0.5752 0.4248

Чтобы оценить начальные вероятности, мы предполагаем, что все последовательности начинаются со скрытого состояния ${\displaystyle S_{1}}$ и вычислите наибольшую вероятность, а затем повторите для ${\displaystyle S_{2}}$. Затем мы снова нормализуем, чтобы получить обновленный начальный вектор.

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

Приложения

Распознавание речи

Скрытые марковские модели были впервые применены к распознаванию речи Джеймс К. Бейкер в 1975 г.^[9] Распознавание непрерывной речи происходит с помощью следующих шагов, смоделированных с помощью HMM. Анализ характеристик сначала проводится на временных и / или спектральных характеристиках речевого сигнала. Это создает вектор наблюдения. Затем функция сравнивается со всеми последовательностями блоков распознавания речи. Эти единицы могут быть фонемы, слоги или целые слова. Система декодирования лексики применяется для ограничения исследуемых путей, поэтому исследуются только слова в лексиконе системы (словарном словаре). Подобно декодированию словаря, системный путь дополнительно ограничен правилами грамматики и синтаксиса. Наконец, применяется семантический анализ, и система выводит распознанное высказывание. Ограничение многих приложений HMM на распознавание речи состоит в том, что текущее состояние зависит только от состояния на предыдущем временном шаге, что нереально для речи, поскольку зависимости часто имеют продолжительность в несколько временных шагов.^[10] Алгоритм Баума-Велча также имеет обширные приложения для решения HMM, используемых в области синтеза речи.^[11]

Криптоанализ

Алгоритм Баума – Велча часто используется для оценки параметров HMM при расшифровке скрытой или зашумленной информации и, следовательно, часто используется в криптоанализ. В области безопасности данных наблюдатель хотел бы извлечь информацию из потока данных, не зная всех параметров передачи. Это может включать обратный инжиниринг канальный кодировщик.^[12] HMM и, как следствие, алгоритм Баума-Велча также использовались для идентификации произносимых фраз в зашифрованных вызовах VoIP.^[13] Кроме того, криптоанализ HMM является важным инструментом для автоматизированного исследования данных о времени кэширования. Это позволяет автоматически обнаруживать критическое состояние алгоритма, например ключевые значения.^[14]

Приложения в биоинформатике

Поиск генов

Прокариотический

В Мерцание (Gene Locator и Interpolated Markov ModelER) программное обеспечение было ранним поиск генов программа, используемая для идентификации кодирующих областей в прокариотический ДНК.^[15][16] GLIMMER использует интерполированные марковские модели (IMM) для определения кодирующие области и отличить их от некодирующая ДНК. В последней версии (GLIMMER3) увеличилось специфичность и точность по сравнению с его предшественниками в отношении предсказания сайтов инициации трансляции, демонстрируя в среднем 99% точность определения местоположения 3 'по сравнению с подтвержденными генами у прокариот.^[17]

Эукариотический

В GENSCAN веб-сервер - это локатор генов, способный анализировать эукариотический последовательности до миллиона пар оснований (1 Мбит) длинный.^[18] GENSCAN использует общую неоднородную трехпериодическую марковскую модель пятого порядка кодирующих областей ДНК. Кроме того, эта модель учитывает различия в плотности и структуре генов (например, в длине интронов), которые возникают в разных изохоры. В то время как большинство интегрированных программ для поиска генов (на момент выпуска GENSCAN) предполагали, что входные последовательности содержат ровно один ген, GENSCAN решает общий случай, когда присутствуют частичные, полные или множественные гены (или даже отсутствие гена вообще).^[19] Было показано, что GENSCAN точно предсказывает местоположение экзона с точностью 90% и специфичностью 80% по сравнению с аннотированной базой данных.^[20]

Обнаружение вариации номера копии

Варианты номера копии (CNV) - это распространенная форма вариаций структуры генома у людей. Использовалась двумерная HMM с дискретными значениями (dbHMM), приписывающая хромосомные области семи различным состояниям: незатронутые области, делеции, дупликации и четыре переходных состояния. Решение этой модели с использованием Баума-Велча продемонстрировало способность предсказывать местоположение точки останова CNV примерно до 300 п.н. эксперименты на микромассивах.^[21] Эта величина разрешения обеспечивает более точную корреляцию между различными CNV и среди населения чем это было возможно ранее, что позволяет изучить частоту популяции CNV. Он также продемонстрировал шаблон прямого наследования для конкретного CNV.

Реализации

• Accord.NET в C #
• ммм Библиотека C с Python привязки, поддерживающие как дискретные, так и непрерывные выбросы.
• HMMBase пакет для Юля.
• Функция HMMFit в RHmm пакет для р.
• хммм поезд в MATLAB

Смотрите также

• Алгоритм Витерби
• Скрытая марковская модель
• EM алгоритм
• Максимальная вероятность
• Распознавание речи
• Биоинформатика
• Криптоанализ

Рекомендации

1. Рабинер, Лоуренс. «Из первых рук: скрытая марковская модель». Сеть глобальной истории IEEE. Получено 2 октября 2013.
2. Елинек, Фредерик; Bahl, Lalit R .; Мерсер, Роберт Л. (май 1975 г.). «Разработка лингвистического статистического декодера для распознавания слитной речи». IEEE Transactions по теории информации. 21 (3): 250–6. Дои:10.1109 / tit.1975.1055384.
3. Бишоп, Мартин Дж .; Томпсон, Элизабет А. (20 июля 1986 г.). «Максимальное правдоподобие выравнивания последовательностей ДНК». Журнал молекулярной биологии. 190 (2): 159–65. Дои:10.1016/0022-2836(86)90289-5. PMID  3641921.
4. Дурбин, Ричард (23 апреля 1998 г.). Анализ биологической последовательности: вероятностные модели белков и нуклеиновых кислот. Издательство Кембриджского университета. ISBN  978-0-521-62041-3.
5. Билмес, Джефф А. (1998). Краткое руководство по EM-алгоритму и его применению к оценке параметров для гауссовой смеси и скрытых марковских моделей. Беркли, Калифорния: Международный институт компьютерных наук. С. 7–13.
6. Рабинер, Лоуренс (февраль 1989 г.). "Учебное пособие по скрытым марковским моделям и избранным приложениям в распознавании речи" (PDF). Труды IEEE. Получено 29 ноябрь 2019.
7. «Приложения Баума-Велча и HMM» (PDF). Школа общественного здравоохранения Bloomberg Джонса Хопкинса. Получено 11 октября 2019.
8. Фраццоли, Эмилио. «Введение в скрытые марковские модели: алгоритм Баума-Велча» (PDF). Аэронавтика и астронавтика, Массачусетский технологический институт. Получено 2 октября 2013.
9. Бейкер, Джеймс К. (1975). «Система ДРАКОН - Обзор». Транзакции IEEE по акустике, речи и обработке сигналов. 23: 24–29. Дои:10.1109 / ТАССП.1975.1162650.
10. Рабинер, Лоуренс (февраль 1989 г.). "Учебное пособие по скрытым марковским моделям и избранным приложениям в распознавании речи". Труды IEEE. 77 (2): 257–286. CiteSeerX  10.1.1.381.3454. Дои:10.1109/5.18626.
11. Токуда, Кейчи; Ёсимура, Такаяоши; Масуко, Такаши; Кобаяси, Такао; Китамура, Тадаши (2000). «Алгоритмы генерации параметров речи для синтеза речи на основе HMM». Международная конференция IEEE по акустике, речи и обработке сигналов. 3.
12. Дингель, Янис; Хагенауэр, Иоахим (24 июня 2007 г.). "Оценка параметров сверточного кодировщика по зашумленным наблюдениям". Международный симпозиум IEEE по теории информации.
13. Райт, Чарльз; Баллард, Лукас; Коулл, Скотт; Монроуз, Фабиан; Массон, Джеральд (2008). «Найди меня, если сможешь: обнаружение разговорных фраз в зашифрованных разговорах по протоколу VoIP». Международный симпозиум IEEE по безопасности и конфиденциальности.
14. Брамли, Боб; Хакала, Ристо (2009). Атаки по шаблону времени кеширования. Достижения в криптографии. Конспект лекций по информатике. 5912. С. 667–684. Дои:10.1007/978-3-642-10366-7_39. ISBN  978-3-642-10365-0.
15. Зальцберг, Стивен; Делчер, Артур Л .; Касиф, Саймон; Белый, Оуэн (1998). «Идентификация микробных генов с использованием интерполированных марковских моделей». Исследования нуклеиновых кислот. 26 (2): 544–548. Дои:10.1093 / nar / 26.2.544. ЧВК  147303. PMID  9421513.
16. "Glimmer: система обнаружения микробных генов". Университет Джона Хопкинса - Центр вычислительной биологии.
17. Делчер, Артур; Братке, Кирстен А .; Пауэрс, Эдвин С .; Зальцберг, Стивен Л. (2007). «Идентификация бактериальных генов и ДНК эндосимбионтов с помощью Glimmer». Биоинформатика. 23 (6): 673–679. Дои:10.1093 / биоинформатика / btm009. ЧВК  2387122. PMID  17237039.
18. Бердж, Кристофер. "Веб-сервер GENSCAN в Массачусетском технологическом институте". Архивировано из оригинал 6 сентября 2013 г.. Получено 2 октября 2013.
19. Бердж, Крис; Карлин, Сэмюэл (1997). «Прогнозирование полных генных структур в геномной ДНК человека». Журнал молекулярной биологии. 268 (1): 78–94. CiteSeerX  10.1.1.115.3107. Дои:10.1006 / jmbi.1997.0951. PMID  9149143.
20. Бердж, Кристофер; Карлин, Сэмюэл (1998). «Поиск генов в геномной ДНК». Текущее мнение в структурной биологии. 8 (3): 346–354. Дои:10.1016 / s0959-440x (98) 80069-9. PMID  9666331.
21. Корбель Ян; Урбан, Александр; Груберт, Фабьен; Ду, Цзян; Ройс, Томас; Старр, Питер; Чжун, Гуонэн; Эмануэль, Беверли; Вайсман, Шерман; Снайдер, Майкл; Герштейн, Марг (12 июня 2007 г.). «Систематическое предсказание и проверка точек останова, связанных с вариациями числа копий в геноме человека». Труды Национальной академии наук Соединенных Штатов Америки. 104 (24): 10110–5. Bibcode:2007ПНАС..10410110К. Дои:10.1073 / pnas.0703834104. ЧВК  1891248. PMID  17551006.

внешняя ссылка

• Всесторонний обзор методов и программного обеспечения HMM в биоинформатике - Профиль скрытых марковских моделей
• Ранние публикации HMM Баума:
  • Техника максимизации, встречающаяся в статистическом анализе вероятностных функций марковских цепей
  • Неравенство с приложениями к статистическому оцениванию вероятностных функций марковских процессов и к модели для экологии
  • Статистический вывод для вероятностных функций конечных марковских цепей
• Лекция Шеннона Уэлча, в которой рассказывается, как можно эффективно реализовать алгоритм:
  • Скрытые марковские модели и алгоритм Баума – Велча., Информационный бюллетень общества теории информации IEEE, декабрь 2003 г.
• Альтернатива алгоритму Баума-Велча, алгоритм подсчета путей Витерби:
  • Дэвис, Ричард И. А .; Ловелл, Брайан Ч .; «Сравнение и оценка алгоритмов обучения ансамбля HMM с использованием обучающих и тестовых критериев числа условий», Анализ структур и приложения, т. 6, вып. 4. С. 327–336, 2003.
• Интерактивная таблица для обучения алгоритму вперед-назад (таблица и статья с пошаговым руководством)
• Формальный вывод алгоритма Баума – Велча.
• Реализация алгоритма Баума – Велча.