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

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

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

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

Определения

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

Парсинг: Поиск правильного вывода с помощью автомата.

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

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

Формальное определение

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

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

куда

• M набор нетерминальных символов
• Т это набор терминальных символов
• р это набор правил производства
• S это начальный символ
• п это множество вероятностей по продукционным правилам

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

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

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

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

Грамматическая конструкция

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

${\displaystyle S\to aS,S\to bS,S\to \epsilon }$

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

${\displaystyle S\to aS|bS|\epsilon }$

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

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

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

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

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

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

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

А взвешенная контекстно-свободная грамматика (WCFG) - более общая категория контекстно-свободная грамматика, где каждому продукту присвоен числовой вес. Вес конкретного дерево синтаксического анализа в WCFG это продукт^[12] (или сумма^[13] ) всех весов правил в дереве. Вес каждого правила включается так часто, как правило используется в дереве. Особым случаем WCFG являются PCFG, где веса (логарифмы из ^[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\to aSa|bSb|aa|bb}$

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

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

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

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

Реализации

Реализации вторичной структуры РНК на основе подходов 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

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

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

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

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

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

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

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

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

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

Алгоритмы

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

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

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

PCFG в поиске гомологии

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

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

${\displaystyle P\to aWb}$

вероятности парных взаимодействий между 16 возможными парами

${\displaystyle L\to aW}$

вероятности генерации 4 возможных одиночных баз слева

${\displaystyle R\to Wa}$

вероятности генерации 4 возможных одиночных оснований справа

${\displaystyle B\to SS}$

бифуркация с вероятностью 1

${\displaystyle S\to W}$

начать с вероятностью 1

${\displaystyle E\to \epsilon }$

закончиться с вероятностью 1

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle PX^{r}XY=PY^{r}YX}$

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

Оценить вероятность совмещения

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

${\displaystyle P(D|T,M)}$

${\displaystyle =\sum P(D,\sigma |T,M)}$

${\displaystyle =\sum P(D|\sigma ,T,M)P(\sigma |T,M)}$

${\displaystyle =\sum P(D|\sigma ,T,M)P(\sigma |M)}$

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

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

${\displaystyle S\to LS(80\%)|L(20\%)}$

${\displaystyle L\to s(70\%)|dFd(30\%)}$

${\displaystyle F\to dFd(60.4\%)|LS(39.6\%)}$

Прогнозировать вероятность строения

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

${\displaystyle \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 дерево Т вычисляется до предсказания структуры посредством объединения соседей, а не по максимальной вероятности посредством грамматики PCFG. Для оценок максимального правдоподобия корректируются только длины ветвей.
• Предположение Pfold состоит в том, что все последовательности имеют одинаковую структуру. Порог идентичности последовательности и допущение 1% вероятности того, что какой-либо нуклеотид станет еще одним ограничителем ухудшения производительности из-за ошибок выравнивания.

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

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

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

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

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

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

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

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

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