Вероятностная контекстно-свободная грамматика

Теория грамматики для моделирования символьных строк возникла в результате работы в области компьютерной лингвистики, направленной на понимание структуры естественных языков . ^[1]^[2]^[3] Вероятностный контекстно-свободная грамматика ( PCFGs ) были применены в вероятностного моделирования из структур РНК почти 40 лет после того, как они были введены в компьютерной лингвистике . ^[4]^[5]^[6]^[7]^[8]

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

PCFG находят применение в таких разнообразных областях, как обработка естественного языка для изучения структуры молекул РНК и проектирования языков программирования . При разработке эффективных PCFG необходимо учитывать факторы масштабируемости и универсальности. Необходимо устранить такие проблемы, как грамматическая двусмысленность. Грамматический дизайн влияет на точность результатов. Алгоритмы синтаксического анализа грамматики имеют различные требования к времени и памяти.

Определения [ править ]

Вывод: процесс рекурсивной генерации строк из грамматики.

Разбор : поиск действительного вывода с помощью автомата.

Дерево синтаксического анализа: соответствие грамматики последовательности.

Примером синтаксического анализатора грамматик PCFG является автомат pushdown . Алгоритм анализирует нетерминалы грамматики слева направо в виде стека . Этот метод грубой силы не очень эффективен. В вариантах предсказания вторичной структуры РНК алгоритма Кок-Янгера-Касами (CYK) предоставляют более эффективные альтернативы синтаксическому анализу грамматики, чем автоматические выталкивающие элементы. ^[9] Другим примером анализатора PCFG является Стэнфордский статистический анализатор, который был обучен с использованием Treebank . ^[10]

Формальное определение [ править ]

Подобно CFG , вероятностная контекстно-свободная грамматика $G$ может быть определена пятеркой:

{\ Displaystyle G = (M, T, R, S, P)}

где

$M$ - множество нетерминальных символов
$T$ - набор терминальных символов
$R$ - набор производственных правил
$S$ - начальный символ
$P$ - множество вероятностей по продукционным правилам

Связь со скрытыми марковскими моделями [ править ]

Модели PCFG расширяют контекстно-свободные грамматики так же, как скрытые марковские модели расширяют обычные грамматики .

Алгоритм Inside-Outside является аналогом вперед-назад алгоритма . Он вычисляет общую вероятность всех производных, согласующихся с заданной последовательностью, на основе некоторого PCFG. Это эквивалентно вероятности того, что PCFG сгенерирует последовательность, и интуитивно является мерой того, насколько последовательность согласуется с заданной грамматикой. Алгоритм Inside-Outside используется в параметризации модели для оценки предшествующих частот, наблюдаемых из обучающих последовательностей в случае РНК.

Варианты динамического программирования алгоритма CYK находят синтаксический анализ Витерби последовательности РНК для модели PCFG. Этот синтаксический анализ является наиболее вероятным производным последовательности данной PCFG.

Грамматическая конструкция [ править ]

Бесконтекстные грамматики представлены как набор правил, вдохновленных попытками моделирования естественных языков. ^[3] Правила являются абсолютными и имеют типичное синтаксическое представление, известное как форма Бэкуса – Наура . Правила производства состоят из оконечных и нетерминальных $S-$ символов, и в качестве конечной точки также может использоваться пробел . В производственных правилах CFG и PCFG левая сторона имеет только один нетерминал, тогда как правая сторона может быть любой строкой терминалов или нетерминалов. В PCFG нули исключены. ^[9] Пример грамматики: ${\ Displaystyle \ влево \ {а, б \ вправо \}}$ ${\ displaystyle \ epsilon}$

{\ Displaystyle S \ в AS, S \ в BS, S \ в \ epsilon}

Эту грамматику можно сократить с помощью символа '|' ('или') символ в:

{\ Displaystyle S \ к AS | BS | \ epsilon}

Терминалы в грамматике - это слова, и через правила грамматики нетерминальный символ преобразуется в строку из терминалов и / или нетерминалов. Вышеупомянутая грамматика читается как «начиная с нетерминального $S,$ излучение может генерировать либо $a,$ либо $b,$ либо ». Его вывод: ${\ displaystyle \ epsilon}$

{\ displaystyle S \ Rightarrow aS \ Rightarrow abS \ Rightarrow abbS \ Rightarrow abb}

Неоднозначная грамматика может привести к неоднозначному синтаксическому анализу, если применяется к омографам, поскольку одна и та же последовательность слов может иметь более одной интерпретации. Карательные предложения, такие как газетный заголовок «Голова Ирака ищет оружие», являются примером неоднозначного разбора.

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

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

Присвоение вероятности продукционным правилам создает PCFG. Эти вероятности получают информацию, наблюдая за распределениями на обучающем наборе, состав которого аналогичен моделируемому языку. В большинстве образцов широкого языка вероятностные грамматики, в которых вероятности оцениваются на основе данных, обычно превосходят грамматики, созданные вручную. CFG в отличие от PCFG неприменимы для предсказания структуры РНК, потому что, хотя они включают взаимосвязь последовательность-структура, им не хватает показателей оценки, которые раскрывают структурный потенциал последовательности ^[11]

Взвешенная контекстно-свободная грамматика [ править ]

Взвешенная контекстно-свободная грамматика ( WCFG ) является более общей категорией контекстно-свободной грамматики , где каждое производство имеет числовой вес , связанный с ним. Вес определенного дерева синтаксического анализа в WCFG - это произведение ^[12] (или сумма ^[13] ) всех весов правил в дереве. Вес каждого правила включается так часто, как правило используется в дереве. Частный случай является WCFGs PCFGs, где вес ( логарифмы из ^[14]^[15] ) вероятностей .

Расширенная версия алгоритма CYK может использоваться для поиска «легчайшего» (с наименьшим весом) производной строки с учетом некоторого количества WCFG.

Когда вес дерева является произведением весов правил, WCFG и PCFG могут выражать один и тот же набор распределений вероятностей . ^[12]

Приложения [ править ]

Предсказание структуры РНК [ править ]

Минимизация энергии ^[16]^[17] и PCFG предоставляют способы предсказания вторичной структуры РНК с сопоставимой производительностью. ^[4]^[5]^[9] Однако предсказание структуры с помощью PCFG оценивается вероятностно, а не расчетом минимальной свободной энергии. Параметры модели PCFG выводятся непосредственно из частот различных характеристик, наблюдаемых в базах данных структур РНК ^[11], а не путем экспериментального определения, как в случае с методами минимизации энергии. ^[18]^[19]

Типы различных структур, которые могут быть смоделированы с помощью PCFG, включают дальнодействующие взаимодействия, парную структуру и другие вложенные структуры. Однако псевдоузлы не поддаются моделированию. ^[4]^[5]^[9]PCFG расширяют CFG, присваивая вероятности каждому производственному правилу. Дерево синтаксического анализа максимальной вероятности из грамматики подразумевает структуру максимальной вероятности. Поскольку РНК сохраняют свои структуры по сравнению с их первичной последовательностью; Прогнозирование структуры РНК может осуществляться путем объединения эволюционной информации из сравнительного анализа последовательностей с биофизическими знаниями о правдоподобности структуры, основанной на таких вероятностях. Также результаты поиска структурных гомологов с использованием правил PCFG оцениваются в соответствии с вероятностями производных PCFG. Следовательно, построение грамматики для моделирования поведения пар оснований и одноцепочечных областей начинается с изучения особенностей структурного выравнивания множественных последовательностей родственных РНК. ^[9]

{\ Displaystyle S \ к aSa | bSb | aa | bb}

Вышеупомянутая грамматика генерирует строку по типу «снаружи-внутрь», то есть сначала выводится базовая пара на самых дальних крайних точках терминала. Таким образом, строка типа as получается путем создания дистальных $a$ с обеих сторон перед перемещением внутрь: ${\ displaystyle aabaabaa}$

{\ displaystyle S \ Rightarrow aSa \ Rightarrow aaSaa \ Rightarrow aabSbaa \ Rightarrow aabaabaa}

Расширяемость модели PCFG позволяет ограничить предсказание структуры за счет включения ожиданий относительно различных характеристик РНК. Такое ожидание может отражать, например, склонность к принятию определенной структуры РНК. ^[11] Однако включение слишком большого количества информации может увеличить пространство PCFG и сложность памяти, и желательно, чтобы модель на основе PCFG была как можно более простой. ^[11]^[20]

Каждой возможной строке $x, которую$ генерирует грамматика, присваивается вероятностный вес с учетом модели PCFG . Отсюда следует, что сумма всех вероятностей для всех возможных грамматических производств равна . Баллы для каждого парного и непарного остатка объясняют вероятность образования вторичной структуры. Производственные правила также позволяют оценивать длину цикла, а также порядок наложения базовых пар, поэтому можно исследовать диапазон всех возможных поколений, включая субоптимальные структуры из грамматики, и принимать или отклонять структуры на основе пороговых значений баллов. ^[9]^[11] ${\ Displaystyle Р (х | \ тета)}$ ${\ displaystyle \ theta}$ ${\ Displaystyle \ сумма _ {\ текст {х}} п (х | \ тета) = 1}$

Реализации [ править ]

Реализации вторичной структуры РНК, основанные на подходах PCFG, могут быть использованы в:

Нахождение консенсусной структуры путем оптимизации совместных вероятностей структур по MSA. ^[20]^[21]
Моделирование ковариации пар оснований для обнаружения гомологии при поиске в базе данных. ^[4]
попарно одновременное сворачивание и совмещение. ^[22]^[23]

Существуют разные реализации этих подходов. Например, Pfold используется для предсказания вторичной структуры из группы связанных последовательностей РНК, ^[20] модели ковариации используются для поиска в базах данных гомологичных последовательностей, аннотации и классификации РНК, ^[4]^{[24] используются} RNApromo, CMFinder и TEISER. в поиске стабильных структурных мотивов в РНК. ^[25]^[26]^[27]

Соображения по дизайну [ править ]

Дизайн PCFG влияет на точность предсказания вторичной структуры. Любая полезная вероятностная модель прогнозирования структуры, основанная на PCFG, должна поддерживать простоту без значительного ущерба для точности прогнозирования. Слишком сложная модель отличной производительности для одной последовательности может не масштабироваться. ^[9] Модель на основе грамматики должна уметь:

Найдите оптимальное выравнивание между последовательностью и PCFG.
Оцените вероятность структур для последовательности и подпоследовательностей.
Параметризуйте модель путем обучения последовательностям / структурам.
Найдите оптимальное дерево разбора грамматики (алгоритм CYK).
Проверка на неоднозначную грамматику (алгоритм условного внутреннего).

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

Можно выделить два типа неоднозначности. Неоднозначность дерева синтаксического анализа и структурная неоднозначность. Структурная неоднозначность не влияет на термодинамические подходы, поскольку выбор оптимальной структуры всегда осуществляется на основе самых низких показателей свободной энергии. ^[11] Неоднозначность дерева синтаксического анализа касается существования нескольких деревьев синтаксического анализа для каждой последовательности. Такая неоднозначность может выявить все возможные структуры с парами оснований для последовательности путем генерации всех возможных деревьев синтаксического анализа и последующего нахождения оптимального. ^[28]^[29]^[30] В случае структурной неоднозначности несколько деревьев синтаксического анализа описывают одну и ту же вторичную структуру. Это скрывает решение алгоритма CYK о поиске оптимальной структуры, поскольку соответствие между деревом синтаксического анализа и структурой не является уникальным. ^[31]Неоднозначность грамматики можно проверить с помощью внутреннего условного алгоритма. ^[9]^[11]

Построение модели PCFG [ править ]

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

Начальный нетерминал создает петли. Остальная часть грамматики продолжается с параметром, который определяет, является ли цикл началом основы или одноцепочечной областью $s,$ и параметром, который создает парные основания. $\mathbf {\mathit {S}}$ $\mathbf {\mathit {L}}$ $\mathbf {\mathit {F}}$

Формализм этой простой PCFG выглядит так:

{\mathit {S\to LS|L}}

{\mathit {L\to s|dFd}}

{\mathit {F\to dFd|LS}}

Применение PCFG для прогнозирования структур - это многоэтапный процесс. Кроме того, сам PCFG может быть включен в вероятностные модели, которые учитывают историю эволюции РНК или поиск гомологичных последовательностей в базах данных. В контексте истории эволюции включение предшествующих распределений структур РНК структурного выравнивания в продукционные правила PCFG способствует хорошей точности прогнозов. ^[21]

Сводка общих шагов по использованию PCFG в различных сценариях:

Сгенерируйте производственные правила для последовательностей.
Проверить двусмысленность.
Рекурсивно генерировать деревья синтаксического анализа возможных структур с использованием грамматики.
Ранжируйте и оценивайте деревья синтаксического анализа для наиболее правдоподобной последовательности. ^[9]

Алгоритмы [ править ]

Существует несколько алгоритмов, касающихся аспектов вероятностных моделей на основе PCFG в предсказании структуры РНК. Например, алгоритм внутри-снаружи и алгоритм CYK. Алгоритм внутреннего-внешнего - это рекурсивный алгоритм оценки динамического программирования, который может следовать парадигмам максимизации ожидания . Он вычисляет общую вероятность всех производных, согласующихся с заданной последовательностью, на основе некоторого PCFG. Внутренняя часть оценивает поддеревья из дерева синтаксического анализа и, следовательно, оценивает вероятности подпоследовательностей с учетом PCFG. Внешняя часть оценивает вероятность полного дерева синтаксического анализа для полной последовательности. ^[32]^[33]CYK изменяет оценку внутри и снаружи. Обратите внимание, что термин «алгоритм CYK» описывает вариант CYK внутреннего алгоритма, который находит оптимальное дерево синтаксического анализа для последовательности с использованием PCFG. Он расширяет реальный алгоритм CYK, используемый в не вероятностных CFG. ^[9]

Внутренний алгоритм вычисляет вероятности для всего поддерева синтаксического анализа с корнем для подпоследовательности . Внешний алгоритм вычисляет вероятности полного синтаксического дерева для последовательности $x$ от корня, исключая вычисление . Переменные $α$ и $β$ уточняют оценку вероятностных параметров PCFG. Можно переоценить алгоритм PCFG, найдя ожидаемое количество раз, когда состояние используется в выводе, путем суммирования всех произведений $α$ и $β,$ деленных на вероятность для последовательности $x с$ данной моделью. $\alpha (i,j,v)$ $i,j,v$ $W_{v}$ $x_{i},...,x_{j}$ $\beta (i,j,v)$ $x_{i},...,x_{j}$ $P(x|\theta )$ . Также возможно найти ожидаемое количество раз, когда производственное правило используется с помощью максимизации ожидания, которая использует значения $α$ и $β$ . ^[32]^[33] Алгоритм CYK вычисляет наиболее вероятное дерево синтаксического анализа и дает результаты . ^[9] $\gamma (i,j,v)$ ${\hat {\pi }}$ $\log P(x,{\hat {\pi }}|\theta )$

Память и временная сложность для общих алгоритмов PCFG при прогнозировании структуры РНК равны и соответственно. Ограничение PCFG может изменить это требование, как и в случае с методами поиска в базе данных. $O(L^{2}M)$ $O(L^{3}M^{3})$

PCFG в поиске гомологии [ править ]

Модели ковариации (CM) - это особый тип PCFG с приложениями для поиска в базах данных гомологов, аннотаций и классификации РНК. Посредством CM можно построить профили РНК на основе PCFG, где родственные РНК могут быть представлены согласованной вторичной структурой. ^[4]^[5] Пакет анализа РНК Infernal использует такие профили для вывода выравнивания РНК. ^[34] База данных Rfam также использует CM для классификации РНК по семействам на основе их структуры и информации о последовательностях. ^[24]

CM созданы на основе консенсусной структуры РНК. CM позволяет использовать отступы неограниченной длины в выравнивании. Терминалы составляют состояния в CM, и вероятности перехода между состояниями равны 1, если не учитываются отступы. ^[9] Грамматики в CM следующие:

$P\to aWb$: вероятности парных взаимодействий между 16 возможными парами
$L\to aW$: вероятности генерации 4 возможных одиночных баз слева
$R\to Wa$: вероятности генерации 4 возможных одиночных оснований справа
$B\to SS$: бифуркация с вероятностью 1
$S\to W$: начать с вероятностью 1
$E\to \epsilon$: заканчиваться с вероятностью 1

Модель имеет 6 возможных состояний, и каждая грамматика состояний включает различные типы вероятностей вторичной структуры нетерминалов. Состояния связаны переходами. В идеале текущие состояния узла подключаются ко всем состояниям вставки, а последующие состояния узла подключаются к состояниям без вставки. Чтобы разрешить вставку более чем одной базовой вставки, состояния соединяются сами с собой. ^[9]

Для оценки модели CM используются алгоритмы внутреннего и внешнего. CM используют несколько иную реализацию CYK. Оценки выбросов с логарифмическими коэффициентами для оптимального дерева синтаксического анализа - - вычисляются на основе состояний излучения . Поскольку эти оценки являются функцией длины последовательности, более точная мера для восстановления оптимальной оценки вероятности дерева синтаксического анализа достигается ограничением максимальной длины последовательности, которая должна быть выровнена, и вычислением логарифмических шансов относительно нуля. Время вычисления этого шага линейно зависит от размера базы данных, и алгоритм имеет сложность памяти . ^[9] $\log {\hat {e}}$ $P,~L,~R$ $\log {\text{P}}(x,{\hat {\pi }}|\theta )$ $O(M_{a}D+M_{b}D^{2})$

Пример: использование эволюционной информации для предсказания структуры [ править ]

Алгоритм KH-99 Кнудсена и Хайна закладывает основу подхода Пфолда к предсказанию вторичной структуры РНК. ^[20] В этом подходе параметризация требует информации об истории эволюции, полученной из дерева выравнивания, в дополнение к вероятностям столбцов и мутаций. Вероятности грамматики наблюдаются из обучающего набора данных.

Оцените вероятности столбца для парных и непарных оснований [ править ]

При структурном выравнивании вероятности непарных базовых столбцов и парных базовых столбцов не зависят от других столбцов. Путем подсчета оснований в одиночных базовых позициях и парных позициях можно получить частоты баз в петлях и стержнях. Для базовой пары $X$ и $Y$ вхождение также считается появлением . Идентичные пары оснований, например , считаются дважды. $XY$ $YX$ $XX$

Рассчитайте частоту мутаций для парных и непарных оснований [ править ]

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

в то время как  $X\neq Y$  первая пара последовательностей вторая пара последовательностей $C_{\text{XY}}+1$   $C_{\text{YX}}+1$

Рассчитайте частоту мутаций.  Пусть мутация основания X на основание Y  $r_{\text{XY}}=$  $={\frac {K~C_{\text{XY}}}{P_{x}P_{s}}}$  Пусть отрицательная скорость мутации X на другие основания  $r_{\text{XX}}=$  $=-\sum r_{\text{XY}}$  вероятность того, что основание не спарено. $P_{s}=$

Для неспаренных оснований используется матрица частоты мутаций 4 X 4, которая удовлетворяет тому, что поток мутаций от X к Y является обратимым: ^[35]

PX^{r}XY=PY^{r}YX

Для базовых пар аналогичным образом создается матрица распределения скоростей 16 X 16. ^[36]^[37] PCFG используется для прогнозирования априорного распределения вероятностей структуры, тогда как апостериорные вероятности оцениваются с помощью алгоритма внутри и снаружи, а наиболее вероятная структура находится с помощью алгоритма CYK. ^[20]

Оцените вероятность совмещения [ править ]

После вычисления априорных вероятностей столбца вероятность совмещения оценивается путем суммирования по всем возможным вторичным структурам. Любой столбец $С$ во вторичной структуре для последовательности $D$ длины $L$ такой , что может быть забит по отношению к дереву выравнивания $Т$ и мутационной модели $M$ . Предварительное распределение, данное PCFG, составляет . Филогенетическое дерево $T$ может быть рассчитано из модели путем оценки максимального правдоподобия. Обратите внимание, что пробелы рассматриваются как неизвестные основания, и суммирование может быть выполнено с помощью динамического программирования . ^[38] $\sigma$ $D=(C_{1},~C_{2},...C_{l})$ $P(\sigma |M)$

P(D|T,M)

=\sum P(D,\sigma |T,M)

=\sum P(D|\sigma ,T,M)P(\sigma |T,M)

=\sum P(D|\sigma ,T,M)P(\sigma |M)

Назначьте производственные вероятности каждому правилу грамматики [ править ]

Каждой структуре в грамматике назначаются производственные вероятности, разработанные на основе структур обучающего набора данных. Эти априорные вероятности придают вес точности прогнозов. ^[21]^[32]^[33] Количество использований каждого правила зависит от наблюдений из обучающего набора данных для этой конкретной грамматической функции. Эти вероятности записаны в скобках в грамматическом формализме, и каждое правило будет иметь в сумме 100%. ^[20] Например:

S\to LS(80\%)|L(20\%)

L\to s(70\%)|dFd(30\%)

F\to dFd(60.4\%)|LS(39.6\%)

Предсказать вероятность конструкции [ править ]

Учитывая предшествующие частоты выравнивания данных, наиболее вероятная структура ансамбля, предсказанная грамматикой, затем может быть вычислена путем максимизации с помощью алгоритма CYK. Структура с наибольшим прогнозируемым количеством правильных прогнозов сообщается как консенсусная структура. ^[20] $P(\sigma |D,T,M)$

\sigma _{MAP}=\arg {\underset {\sigma }{\max }}P(D|\sigma ,T^{M}L,M)P(\sigma |M)

Улучшения Pfold в алгоритме KH-99 [ править ]

Желательно, чтобы подходы, основанные на PCFG, были достаточно масштабируемыми и общими. Компромиссная скорость для точности должна быть минимальной. Pfold устраняет ограничения алгоритма KH-99 в отношении масштабируемости, пропусков, скорости и точности. ^[20]

В Pfold пробелы считаются неизвестными. В этом смысле вероятность столбца с пробелом равна вероятности столбца без пробела.
В Pfold дерево $T$ вычисляется до предсказания структуры посредством объединения соседей, а не по максимальной вероятности посредством грамматики PCFG. Только длины ветвей корректируются до оценок максимального правдоподобия.
Предположение Pfold состоит в том, что все последовательности имеют одинаковую структуру. Порог идентичности последовательности и допущение 1% вероятности того, что какой-либо нуклеотид станет еще одним ограничителем ухудшения производительности из-за ошибок выравнивания.

Анализ белковой последовательности [ править ]

В то время как PCFG оказались мощными инструментами для прогнозирования вторичной структуры РНК, их использование в области анализа последовательности белков было ограничено. Действительно, размер аминокислотного алфавита и разнообразие взаимодействий, наблюдаемых в белках, значительно усложняют вывод грамматики. ^[39] Как следствие, большинство приложений теории формального языка к анализу белков были в основном ограничены созданием грамматик с меньшей выразительной способностью для моделирования простых функциональных паттернов, основанных на локальных взаимодействиях. ^[40]^[41] Поскольку белковые структуры обычно демонстрируют зависимости более высокого порядка, включая вложенные и перекрестные отношения, они явно превосходят возможности любого CFG. ^[39]Тем не менее, разработка PCFG позволяет выразить некоторые из этих зависимостей и дает возможность моделировать более широкий спектр белковых паттернов.

Одним из основных препятствий при построении грамматики белка является размер алфавита, который должен кодировать 20 различных аминокислот . Было предложено решить эту проблему, используя физико-химические свойства аминокислот, чтобы значительно уменьшить количество возможных комбинаций символов правой стороны в правилах получения: вместо 20 типов аминокислот используются 3 уровня количественного свойства , например, маленькие , средний или большой объем Ван-дер-Ваальса . ^[42] На основе такой схемы были произведены PCFG, которые генерируют как сайт связывания ^{[42], так} и дескрипторы сайта контакта спираль-спираль. ^[43]Важной особенностью этих грамматик является то, что анализ их правил и деревьев синтаксического анализа может предоставить биологически значимую информацию. ^[42]^[43]

См. Также [ править ]

Статистический анализ
Стохастическая грамматика
L-система

Ссылки [ править ]

^ Хомский, Ноам (1956). «Три модели для описания языка» . Сделки IRE по теории информации . 2 (3): 113–124. DOI : 10.1109 / TIT.1956.1056813 . S2CID 19519474 .
↑ Хомский, Ноам (июнь 1959). «О некоторых формальных свойствах грамматик» . Информация и контроль . 2 (2): 137–167. DOI : 10.1016 / S0019-9958 (59) 90362-6 .
^ a b Ноам Хомский, изд. (1957). Синтаксические структуры . Издательство Mouton & Co., Ден Хааг, Нидерланды.
^ Б с д е е Eddy SR & Дарбина R. (1994). «Анализ последовательности РНК с использованием ковариационных моделей» . Исследования нуклеиновых кислот . 22 (11): 2079–2088. DOI : 10.1093 / nar / 22.11.2079 . PMC 308124 . PMID 8029015 .
^ a b c d Сакакибара Й .; Браун М .; Hughey R .; Миан ИС; и другие. (1994). «Стохастические контекстно-свободные грамматики для моделирования тРНК» . Исследования нуклеиновых кислот . 22 (23): 5112–5120. DOI : 10.1093 / NAR / 22.23.5112 . PMC 523785 . PMID 7800507 .
^ Грат, Л. (1995). «Автоматическое определение вторичной структуры РНК с помощью стохастических контекстно-свободных грамматик» (PDF) . В Роулингс, К., Кларк, Д., Альтман, Р., Хантер, Л., Ленгауэр, Т. и Водак, С. Труды Третьей Международной конференции по интеллектуальным системам для молекулярной биологии, AAAI Press : 136–144.
Перейти ↑ Lefebvre, F (1995). «Оптимизированный алгоритм синтаксического анализа, хорошо подходящий для сворачивания РНК». В Rawlings, C .; Clark, D .; Альтман, Р .; Хантер, Л .; Ленгауэр, Т .; Водак, С. (ред.). Труды Третьей Международной конференции по интеллектуальным системам для молекулярной биологии (PDF) . AAAI Press. С. 222–230.
Перейти ↑ Lefebvre, F. (1996). «Основанное на грамматике объединение нескольких алгоритмов выравнивания и сворачивания». В Штатах - ди-джей; Agarwal, P .; Гаастерлан, Т .; Хантер, Л .; Смит РФ (ред.). Труды Четвертой Международной конференции по интеллектуальным системам для молекулярной биологии (PDF) . AAAI Press. С. 143–153.
^ Б с д е е г ч я J к л м н Р. Дарбина; С. Эдди; А. Крог; Г. Митчинсон, ред. (1998). Анализ биологической последовательности: вероятностные модели белков и нуклеиновых кислот . Издательство Кембриджского университета. ISBN 978-0-521-62971-3.
^ Кляйн, Дэниел; Мэннинг, Кристофер (2003). «Точный нелексикализованный синтаксический анализ» (PDF) . Труды 41-го собрания Ассоциации компьютерной лингвистики : 423–430.
^ Б с д е е г Dowell R. & Eddy S. (2004). «Оценка нескольких облегченных стохастических контекстно-свободных грамматик для предсказания вторичной структуры РНК» . BMC Bioinformatics . 5 (71): 71. DOI : 10,1186 / 1471-2105-5-71 . PMC 442121 . PMID 15180907 .
^ a b Смит, Ной А .; Джонсон, Марк (2007). «Взвешенные и вероятностные контекстно-свободные грамматики одинаково выразительны» (PDF) . Компьютерная лингвистика . 33 (4): 477. DOI : 10,1162 / coli.2007.33.4.477 . S2CID 1405777 .
^ Кацирелос, Джордж; Народицкая Нина; Уолш, Тоби (2008). «Взвешенное ограничение CFG» . Интеграция методов ИИ и ИЛИ в программировании с ограничениями для задач комбинаторной оптимизации . Конспект лекций по информатике. 5015 . п. 323. CiteSeerX 10.1.1.150.1187 . DOI : 10.1007 / 978-3-540-68155-7_31 . ISBN 978-3-540-68154-0. S2CID 9375313 .
^ Джонсон, Марк (2005). «логарифмические линейные модели или модели Гиббса» (PDF) .
^ Чи, Zhiyi (март 1999). «Статистические свойства вероятностных контекстно-свободных грамматик» (PDF) . Компьютерная лингвистика . 25 (1): 131–160. Архивировано из оригинального (PDF) 21 августа 2010 года.
^ McCaskill JS (1990). «Равновесная функция распределения и вероятности связывания пар оснований для вторичной структуры РНК». Биополимеры . 29 (6–7): 1105–19. DOI : 10.1002 / bip.360290621 . hdl : 11858 / 00-001M-0000-0013-0DE3-9 . PMID 1695107 . S2CID 12629688 .
^ Хуан V .; Уилсон К. (1999). «Прогнозирование вторичной структуры РНК на основе анализа свободной энергии и филогенетического анализа». J. Mol. Биол . 289 (4): 935–947. DOI : 10.1006 / jmbi.1999.2801 . PMID 10369773 .
^ Цукер M (2000). «Расчет вторичной структуры нуклеиновых кислот». Curr. Opin. Struct. Биол . 10 (3): 303–310. DOI : 10.1016 / S0959-440X (00) 00088-9 . PMID 10851192 .
^ Мэтьюз DH; Sabina J .; Zuker M .; Тернер Д.Х. (1999). «Расширенная зависимость термодинамических параметров от последовательности улучшает предсказание вторичной структуры РНК» . J. Mol. Биол . 288 (5): 911–940. DOI : 10.1006 / jmbi.1999.2700 . PMID 10329189 . S2CID 19989405 .
^ a b c d e f g h Б. Кнудсен и Дж. Хайн. (2003). «Pfold: предсказание вторичной структуры РНК с использованием стохастических контекстно-свободных грамматик» . Исследования нуклеиновых кислот . 31 (13): 3423–3428. DOI : 10.1093 / NAR / gkg614 . PMC 169020 . PMID 12824339 .
^ a b c Кнудсен Б .; Хайн Дж. (1999). «Предсказание вторичной структуры РНК с использованием стохастических контекстно-свободных грамматик и эволюционной истории» . Биоинформатика . 15 (6): 446–454. DOI : 10.1093 / биоинформатики / 15.6.446 . PMID 10383470 .
^ Ривас Э .; Эдди SR (2001). «Обнаружение генов некодирующей РНК с использованием сравнительного анализа последовательностей» . BMC Bioinformatics . 2 (1): 8. DOI : 10,1186 / 1471-2105-2-8 . PMC 64605 . PMID 11801179 .
^ Холмс I .; Рубин GM (2002). Сравнение попарной структуры РНК со стохастическими контекстно-свободными грамматиками . В. Pac. Symp. Биокомпьют . С. 163–174 . DOI : 10.1142 / 9789812799623_0016 . ISBN 978-981-02-4777-5. PMID 11928472 .
^ a b П. П. Гарднер; J. Daub; Дж. Тейт; Б.Л. Мур; IH Osuch; С. Гриффитс-Джонс; RD Finn; EP Nawrocki; Д.Л. Кольбе; SR Eddy; А. Бейтман. (2011). «Рфам: Википедия, кланы и« десятичный »выпуск» . Исследования нуклеиновых кислот . 39 (Дополнение 1): D141 – D145. DOI : 10.1093 / NAR / gkq1129 . PMC 3013711 . PMID 21062808 .
^ Яо З .; Вайнберг З .; Руццо WL (2006). "CMfinder - алгоритм поиска мотивов РНК, основанный на ковариационной модели" . Биоинформатика . 22 (4): 445–452. DOI : 10.1093 / биоинформатики / btk008 . PMID 16357030 .
^ Rabani M .; Kertesz M .; Сигал Э. (2008). «Вычислительное предсказание структурных мотивов РНК, участвующих в посттранскрипционных регуляторных процессах» . Proc. Natl. Акад. Sci. США . 105 (39): 14885–14890. Bibcode : 2008PNAS..10514885R . DOI : 10.1073 / pnas.0803169105 . PMC 2567462 . PMID 18815376 .
^ Goodarzi H .; Наджафабади Х.С. Oikonomou P .; Greco TM; Fish L .; Salavati R .; Cristea IM; Тавазой С. (2012). «Систематическое открытие структурных элементов, регулирующих стабильность матричных РНК млекопитающих» . Природа . 485 (7397): 264–268. Bibcode : 2012Natur.485..264G . DOI : 10.1038 / nature11013 . PMC 3350620 . PMID 22495308 .
^ Сипсер М. (1996). Введение в теорию вычислений . Brooks Cole Pub Co.
^ Майкл А. Харрисон (1978). Введение в теорию формального языка . Эддисон-Уэсли.
^ Хопкрофт JE; Ульман Дж. Д. (1979). Введение в теорию автоматов, языки и вычисления . Эддисон-Уэсли.
^ Гигерих Р. (2000). «Объяснение и контроль неоднозначности в динамическом программировании» (PDF) . В Трудах 11-го ежегодного симпозиума по комбинаторному сопоставлению с образцом 1848 г. Под редакцией: Джанкарло Р., Санкофф Д. Монреаль, Канада: Springer-Verlag, Берлин . Конспект лекций по информатике. 1848 : 46–59. DOI : 10.1007 / 3-540-45123-4_6 . ISBN 978-3-540-67633-1. S2CID 17088251 .
^ a b c Лари К .; Молодой SJ (1990). «Оценка стохастических контекстно-свободных грамматик с использованием внутреннего-внешнего алгоритма». Компьютерная речь и язык . 4 : 35–56. DOI : 10.1016 / 0885-2308 (90) 90022-X .
^ a b c Лари К .; Молодой SJ (1991). «Приложения стохастических контекстно-свободных грамматик с использованием алгоритма изнутри-снаружи». Компьютерная речь и язык . 5 (3): 237–257. DOI : 10.1016 / 0885-2308 (91) 90009-F .
^ Навроцки Е.П., Eddy SR (2013). «Infernal 1.1: поиск гомологии РНК в 100 раз быстрее» . Биоинформатика . 29 (22): 2933–2935. DOI : 10.1093 / биоинформатики / btt509 . PMC 3810854 . PMID 24008419 .
^ Таваре С. (1986). «Некоторые вероятностно-статистические проблемы анализа последовательностей ДНК». Лекции по математике в естественных науках. Американское математическое общество . 17 : 57–86.
↑ Muse SV (1995). «Эволюционный анализ последовательностей ДНК с учетом ограничений вторичной структуры» . Генетика . 139 (3): 1429–1439. PMC 1206468 . PMID 7768450 .
^ Schöniger M .; фон Хезелер А. (1994). «Стохастическая модель эволюции автокоррелированных последовательностей ДНК». Мол. Филогенет. Evol . 3 (3): 240–7. DOI : 10.1006 / mpev.1994.1026 . PMID 7529616 .
Перейти ↑ Baker, JK (1979). «Обучаемые грамматики для распознавания речи» . Журнал акустического общества Америки . 65 (S1): S132. Bibcode : 1979ASAJ ... 65Q.132B . DOI : 10.1121 / 1.2017061 .
^ a b Searls, D (2013). «Обзор: Учебник по макромолекулярной лингвистике». Биополимеры . 99 (3): 203–217. DOI : 10.1002 / bip.22101 . PMID 23034580 . S2CID 12676925 .
^ Крог, А; Браун, М; Миан, я; Sjolander, K; Хаусслер, Д. (1994). «Скрытые марковские модели в вычислительной биологии: приложения к моделированию белков» . J Mol Biol . 235 (5): 1501–1531. DOI : 10.1006 / jmbi.1994.1104 . PMID 8107089 . S2CID 2160404 .
^ Сигрист, C; Cerutti, L; Хуло, Н; Гаттикер, А; Falquet, L; Паньи, М; Байрох, А; Бухер, П. (2002). «PROSITE: документированная база данных с использованием шаблонов и профилей в качестве дескрипторов мотивов» . Краткий биоинформ . 3 (3): 265–274. DOI : 10.1093 / нагрудник / 3.3.265 . PMID 12230035 .
^ a b c Дырка, Вт; Небель, JC (2009). «Структура на основе стохастической контекстно-свободной грамматики для анализа белковых последовательностей» . BMC Bioinformatics . 10 : 323. DOI : 10,1186 / 1471-2105-10-323 . PMC 2765975 . PMID 19814800 .
^ а б Дырка, Вт; Небель JC, Котульская M (2013). «Вероятностная грамматическая модель белкового языка и ее применение для классификации сайтов контакта спираль-спираль» . Алгоритмы молекулярной биологии . 8 (1): 31. DOI : 10,1186 / 1748-7188-8-31 . PMC 3892132 . PMID 24350601 .

Внешние ссылки [ править ]

База данных Rfam
Адский
Стэнфордский парсер: статистический анализатор
pyStatParser

[Chomsky_1956-1] Хомский, Ноам (1956). «Три модели для описания языка» . Сделки IRE по теории информации . 2 (3): 113–124. DOI : 10.1109 / TIT.1956.1056813 . S2CID 19519474 .

[Chomsky_1959-2] Хомский, Ноам (июнь 1959). «О некоторых формальных свойствах грамматик» . Информация и контроль . 2 (2): 137–167. DOI : 10.1016 / S0019-9958 (59) 90362-6 .

[Chomsky_1957-3] Ноам Хомский, изд. (1957). Синтаксические структуры . Издательство Mouton & Co., Ден Хааг, Нидерланды.

[Eddy_1994-4] Б с д е е Eddy SR & Дарбина R. (1994). «Анализ последовательности РНК с использованием ковариационных моделей» . Исследования нуклеиновых кислот . 22 (11): 2079–2088. DOI : 10.1093 / nar / 22.11.2079 . PMC 308124 . PMID 8029015 .

[Sakakibara_1994-5] Сакакибара Й .; Браун М .; Hughey R .; Миан ИС; и другие. (1994). «Стохастические контекстно-свободные грамматики для моделирования тРНК» . Исследования нуклеиновых кислот . 22 (23): 5112–5120. DOI : 10.1093 / NAR / 22.23.5112 . PMC 523785 . PMID 7800507 .

[Grat_1995-6] Грат, Л. (1995). «Автоматическое определение вторичной структуры РНК с помощью стохастических контекстно-свободных грамматик» (PDF) . В Роулингс, К., Кларк, Д., Альтман, Р., Хантер, Л., Ленгауэр, Т. и Водак, С. Труды Третьей Международной конференции по интеллектуальным системам для молекулярной биологии, AAAI Press : 136–144.

[Lefebvre_1995-7] Перейти ↑ Lefebvre, F (1995). «Оптимизированный алгоритм синтаксического анализа, хорошо подходящий для сворачивания РНК». В Rawlings, C .; Clark, D .; Альтман, Р .; Хантер, Л .; Ленгауэр, Т .; Водак, С. (ред.). Труды Третьей Международной конференции по интеллектуальным системам для молекулярной биологии (PDF) . AAAI Press. С. 222–230.

[Lefebvre_1996-8] Перейти ↑ Lefebvre, F. (1996). «Основанное на грамматике объединение нескольких алгоритмов выравнивания и сворачивания». В Штатах - ди-джей; Agarwal, P .; Гаастерлан, Т .; Хантер, Л .; Смит РФ (ред.). Труды Четвертой Международной конференции по интеллектуальным системам для молекулярной биологии (PDF) . AAAI Press. С. 143–153.

[Durbin_1998-9] Б с д е е г ч я J к л м н Р. Дарбина; С. Эдди; А. Крог; Г. Митчинсон, ред. (1998). Анализ биологической последовательности: вероятностные модели белков и нуклеиновых кислот . Издательство Кембриджского университета. ISBN 978-0-521-62971-3.

[10] Кляйн, Дэниел; Мэннинг, Кристофер (2003). «Точный нелексикализованный синтаксический анализ» (PDF) . Труды 41-го собрания Ассоциации компьютерной лингвистики : 423–430.

[Dowell_2004-11] Б с д е е г Dowell R. & Eddy S. (2004). «Оценка нескольких облегченных стохастических контекстно-свободных грамматик для предсказания вторичной структуры РНК» . BMC Bioinformatics . 5 (71): 71. DOI : 10,1186 / 1471-2105-5-71 . PMC 442121 . PMID 15180907 .

[PCFG_WCFG_same-12] Смит, Ной А .; Джонсон, Марк (2007). «Взвешенные и вероятностные контекстно-свободные грамматики одинаково выразительны» (PDF) . Компьютерная лингвистика . 33 (4): 477. DOI : 10,1162 / coli.2007.33.4.477 . S2CID 1405777 .

[sumWeightedCFG-13] Кацирелос, Джордж; Народицкая Нина; Уолш, Тоби (2008). «Взвешенное ограничение CFG» . Интеграция методов ИИ и ИЛИ в программировании с ограничениями для задач комбинаторной оптимизации . Конспект лекций по информатике. 5015 . п. 323. CiteSeerX 10.1.1.150.1187 . DOI : 10.1007 / 978-3-540-68155-7_31 . ISBN 978-3-540-68154-0. S2CID 9375313 .

[logLinear-14] Джонсон, Марк (2005). «логарифмические линейные модели или модели Гиббса» (PDF) .

[15] Чи, Zhiyi (март 1999). «Статистические свойства вероятностных контекстно-свободных грамматик» (PDF) . Компьютерная лингвистика . 25 (1): 131–160. Архивировано из оригинального (PDF) 21 августа 2010 года.

[McCaskill_1990-16] McCaskill JS (1990). «Равновесная функция распределения и вероятности связывания пар оснований для вторичной структуры РНК». Биополимеры . 29 (6–7): 1105–19. DOI : 10.1002 / bip.360290621 . hdl : 11858 / 00-001M-0000-0013-0DE3-9 . PMID 1695107 . S2CID 12629688 .

[Juan_1999-17] Хуан V .; Уилсон К. (1999). «Прогнозирование вторичной структуры РНК на основе анализа свободной энергии и филогенетического анализа». J. Mol. Биол . 289 (4): 935–947. DOI : 10.1006 / jmbi.1999.2801 . PMID 10369773 .

[Zuker_2000-18] Цукер M (2000). «Расчет вторичной структуры нуклеиновых кислот». Curr. Opin. Struct. Биол . 10 (3): 303–310. DOI : 10.1016 / S0959-440X (00) 00088-9 . PMID 10851192 .

[Mathews_1999-19] Мэтьюз DH; Sabina J .; Zuker M .; Тернер Д.Х. (1999). «Расширенная зависимость термодинамических параметров от последовательности улучшает предсказание вторичной структуры РНК» . J. Mol. Биол . 288 (5): 911–940. DOI : 10.1006 / jmbi.1999.2700 . PMID 10329189 . S2CID 19989405 .

[Knudsen_2003-20] Б. Кнудсен и Дж. Хайн. (2003). «Pfold: предсказание вторичной структуры РНК с использованием стохастических контекстно-свободных грамматик» . Исследования нуклеиновых кислот . 31 (13): 3423–3428. DOI : 10.1093 / NAR / gkg614 . PMC 169020 . PMID 12824339 .

[Knudsen_1999-21] Кнудсен Б .; Хайн Дж. (1999). «Предсказание вторичной структуры РНК с использованием стохастических контекстно-свободных грамматик и эволюционной истории» . Биоинформатика . 15 (6): 446–454. DOI : 10.1093 / биоинформатики / 15.6.446 . PMID 10383470 .

[Rivas_2001-22] Ривас Э .; Эдди SR (2001). «Обнаружение генов некодирующей РНК с использованием сравнительного анализа последовательностей» . BMC Bioinformatics . 2 (1): 8. DOI : 10,1186 / 1471-2105-2-8 . PMC 64605 . PMID 11801179 .

[Holmes_2002-23] Холмс I .; Рубин GM (2002). Сравнение попарной структуры РНК со стохастическими контекстно-свободными грамматиками . В. Pac. Symp. Биокомпьют . С. 163–174 . DOI : 10.1142 / 9789812799623_0016 . ISBN 978-981-02-4777-5. PMID 11928472 .

[Gardner_2010-24] П. П. Гарднер; J. Daub; Дж. Тейт; Б.Л. Мур; IH Osuch; С. Гриффитс-Джонс; RD Finn; EP Nawrocki; Д.Л. Кольбе; SR Eddy; А. Бейтман. (2011). «Рфам: Википедия, кланы и« десятичный »выпуск» . Исследования нуклеиновых кислот . 39 (Дополнение 1): D141 – D145. DOI : 10.1093 / NAR / gkq1129 . PMC 3013711 . PMID 21062808 .

[Yao_2006-25] Яо З .; Вайнберг З .; Руццо WL (2006). "CMfinder - алгоритм поиска мотивов РНК, основанный на ковариационной модели" . Биоинформатика . 22 (4): 445–452. DOI : 10.1093 / биоинформатики / btk008 . PMID 16357030 .

[Rabani_2008-26] Rabani M .; Kertesz M .; Сигал Э. (2008). «Вычислительное предсказание структурных мотивов РНК, участвующих в посттранскрипционных регуляторных процессах» . Proc. Natl. Акад. Sci. США . 105 (39): 14885–14890. Bibcode : 2008PNAS..10514885R . DOI : 10.1073 / pnas.0803169105 . PMC 2567462 . PMID 18815376 .

[Goodarzi_2012-27] Goodarzi H .; Наджафабади Х.С. Oikonomou P .; Greco TM; Fish L .; Salavati R .; Cristea IM; Тавазой С. (2012). «Систематическое открытие структурных элементов, регулирующих стабильность матричных РНК млекопитающих» . Природа . 485 (7397): 264–268. Bibcode : 2012Natur.485..264G . DOI : 10.1038 / nature11013 . PMC 3350620 . PMID 22495308 .

[Sipser_1996-28] Сипсер М. (1996). Введение в теорию вычислений . Brooks Cole Pub Co.

[Harrison_1978-29] Майкл А. Харрисон (1978). Введение в теорию формального языка . Эддисон-Уэсли.

[Hopcroft_1979-30] Хопкрофт JE; Ульман Дж. Д. (1979). Введение в теорию автоматов, языки и вычисления . Эддисон-Уэсли.

[Giegerich_2000-31] Гигерих Р. (2000). «Объяснение и контроль неоднозначности в динамическом программировании» (PDF) . В Трудах 11-го ежегодного симпозиума по комбинаторному сопоставлению с образцом 1848 г. Под редакцией: Джанкарло Р., Санкофф Д. Монреаль, Канада: Springer-Verlag, Берлин . Конспект лекций по информатике. 1848 : 46–59. DOI : 10.1007 / 3-540-45123-4_6 . ISBN 978-3-540-67633-1. S2CID 17088251 .

[Lari_and_Young_1990-32] Лари К .; Молодой SJ (1990). «Оценка стохастических контекстно-свободных грамматик с использованием внутреннего-внешнего алгоритма». Компьютерная речь и язык . 4 : 35–56. DOI : 10.1016 / 0885-2308 (90) 90022-X .

[Lari_and_Young_1991-33] Лари К .; Молодой SJ (1991). «Приложения стохастических контекстно-свободных грамматик с использованием алгоритма изнутри-снаружи». Компьютерная речь и язык . 5 (3): 237–257. DOI : 10.1016 / 0885-2308 (91) 90009-F .

[Nawrocki_2013-34] Навроцки Е.П., Eddy SR (2013). «Infernal 1.1: поиск гомологии РНК в 100 раз быстрее» . Биоинформатика . 29 (22): 2933–2935. DOI : 10.1093 / биоинформатики / btt509 . PMC 3810854 . PMID 24008419 .

[Tavaré_1986-35] Таваре С. (1986). «Некоторые вероятностно-статистические проблемы анализа последовательностей ДНК». Лекции по математике в естественных науках. Американское математическое общество . 17 : 57–86.

[Muse_1995-36] Muse SV (1995). «Эволюционный анализ последовательностей ДНК с учетом ограничений вторичной структуры» . Генетика . 139 (3): 1429–1439. PMC 1206468 . PMID 7768450 .

[Schöniger_1994-37] Schöniger M .; фон Хезелер А. (1994). «Стохастическая модель эволюции автокоррелированных последовательностей ДНК». Мол. Филогенет. Evol . 3 (3): 240–7. DOI : 10.1006 / mpev.1994.1026 . PMID 7529616 .

[Baker_1979-38] Перейти ↑ Baker, JK (1979). «Обучаемые грамматики для распознавания речи» . Журнал акустического общества Америки . 65 (S1): S132. Bibcode : 1979ASAJ ... 65Q.132B . DOI : 10.1121 / 1.2017061 .

[Searls_D_2013-39] Searls, D (2013). «Обзор: Учебник по макромолекулярной лингвистике». Биополимеры . 99 (3): 203–217. DOI : 10.1002 / bip.22101 . PMID 23034580 . S2CID 12676925 .

[40] Крог, А; Браун, М; Миан, я; Sjolander, K; Хаусслер, Д. (1994). «Скрытые марковские модели в вычислительной биологии: приложения к моделированию белков» . J Mol Biol . 235 (5): 1501–1531. DOI : 10.1006 / jmbi.1994.1104 . PMID 8107089 . S2CID 2160404 .

[41] Сигрист, C; Cerutti, L; Хуло, Н; Гаттикер, А; Falquet, L; Паньи, М; Байрох, А; Бухер, П. (2002). «PROSITE: документированная база данных с использованием шаблонов и профилей в качестве дескрипторов мотивов» . Краткий биоинформ . 3 (3): 265–274. DOI : 10.1093 / нагрудник / 3.3.265 . PMID 12230035 .

[Dyrka_W_2009-42] Дырка, Вт; Небель, JC (2009). «Структура на основе стохастической контекстно-свободной грамматики для анализа белковых последовательностей» . BMC Bioinformatics . 10 : 323. DOI : 10,1186 / 1471-2105-10-323 . PMC 2765975 . PMID 19814800 .

[Dyrka_W_2013-43] а б Дырка, Вт; Небель JC, Котульская M (2013). «Вероятностная грамматическая модель белкового языка и ее применение для классификации сайтов контакта спираль-спираль» . Алгоритмы молекулярной биологии . 8 (1): 31. DOI : 10,1186 / 1748-7188-8-31 . PMC 3892132 . PMID 24350601 .

[1]