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

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

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

Определения

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

Синтаксический анализ : нахождение допустимого вывода с использованием автомата.

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

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

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

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

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

где

• M — множество нетерминальных символов
• T — множество терминальных символов
• R — набор правил производства
• S — начальный символ
• P — это набор вероятностей по правилам производства

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Взвешенная контекстно-свободная грамматика ( WCFG ) — это более общая категория контекстно-свободной грамматики , где каждая продукция имеет числовой вес, связанный с ней. Вес конкретного дерева разбора в WCFG — это произведение ^[7] (или сумма ^[8] ) всех весов правил в дереве. Каждый вес правила включается так часто, как правило используется в дереве. Особым случаем WCFG являются PCFG, где веса — это ( логарифмы [ ^{9] [10]} ) вероятностей .

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

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

Приложения

Предсказание структуры РНК

С 1990-х годов PCFG применяется для моделирования структур РНК . ^{[11] [12] [13] [14] [15]}

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

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

${\displaystyle S\to aSa|bSb|aa|bb}$

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

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

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

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

Реализации

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

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

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

Конструктивные соображения

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

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

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

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

Построение модели PCFG

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

Начальный нетерминал производит циклы. Остальная часть грамматики продолжается с параметром , который определяет, является ли цикл началом стебля или одноцепочечной области s , и параметром , который производит парные основания. ${\displaystyle \mathbf {\mathit {S}} }$ ${\displaystyle \mathbf {\mathit {L}} }$ ${\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 в различных сценариях:

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

Алгоритмы

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

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

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

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

Ковариационные модели (КМ) представляют собой особый тип PCFG с приложениями для поиска в базах данных гомологов, аннотации и классификации РНК. С помощью КМ можно построить профили РНК на основе PCFG, где связанные РНК могут быть представлены консенсусной вторичной структурой. ^{[11] [12]} Пакет анализа РНК Infernal использует такие профили для вывода выравниваний РНК. ^[34] База данных Rfam также использует КМ для классификации РНК в семейства на основе их структуры и информации о последовательности. ^[24]

CM разрабатываются на основе консенсусной структуры РНК. CM допускает индели неограниченной длины в выравнивании. Терминалы представляют собой состояния в CM, а вероятности перехода между состояниями равны 1, если индели не учитываются. ^[1] Грамматики в 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 возможных состояний, и каждая грамматика состояний включает различные типы вероятностей вторичной структуры нетерминалов. Состояния связаны переходами. В идеале текущие состояния узлов связаны со всеми состояниями вставки, а последующие состояния узлов связаны с состояниями невставки. Чтобы разрешить вставку более чем одной базы, состояния вставки связаны с собой. ^[1]

Для оценки модели CM используются алгоритмы «изнутри-снаружи». CM используют немного иную реализацию CYK. Оценки эмиссии логарифмических шансов для оптимального дерева разбора - - вычисляются из состояний эмиссии . Поскольку эти оценки являются функцией длины последовательности, более дискриминантная мера для восстановления оценки вероятности оптимального дерева разбора - - достигается путем ограничения максимальной длины последовательности, подлежащей выравниванию, и вычисления логарифмических шансов относительно нуля. Время вычисления этого шага линейно зависит от размера базы данных, а сложность памяти алгоритма составляет . ^[1] ${\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})}$

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

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

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

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

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

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

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

Рассчитайте частоту мутаций.  Пусть мутация основания X в основание Y.  ${\displaystyle r_{\text{XY}}=}$ ${\displaystyle ={\frac {K~C_{\text{XY}}}{P_{x}P_{s}}}}$ Пусть отрицательная частота мутации X в другие основания —  ${\displaystyle r_{\text{XX}}=}$ ${\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 во вторичной структуре для последовательности D длины l такой, что может быть оценен относительно дерева выравнивания T и мутационной модели M. Априорное распределение, заданное PCFG, равно . Филогенетическое дерево T может быть рассчитано из модели путем оценки максимального правдоподобия. Обратите внимание, что пробелы рассматриваются как неизвестные основания, и суммирование может быть выполнено посредством динамического программирования . ^[38] ${\displaystyle \sigma }$ ${\displaystyle D=(C_{1},~C_{2},...C_{l})}$ ${\displaystyle P(\sigma |M)}$

${\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\%)}$

Предсказать вероятность структуры

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

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

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

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

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

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

Ссылки

1. Р. Дурбин; С. Эдди; А. Крог; Г. Митчинсон (1998). Анализ биологической последовательности: вероятностные модели белков и нуклеиновых кислот. Cambridge University Press. ISBN 978-0-521-62971-3.
2. Кляйн, Дэниел; Мэннинг, Кристофер (2003). «Точный нелексический анализ» (PDF) . Труды 41-го заседания Ассоциации компьютерной лингвистики : 423–430.
3. Хомский, Ноам (1956). «Три модели описания языка». Труды IRE по теории информации . 2 (3): 113–124. doi :10.1109/TIT.1956.1056813. S2CID  19519474.
4. Хомский, Ноам (июнь 1959). «О некоторых формальных свойствах грамматик». Информация и управление . 2 (2): 137–167. doi : 10.1016/S0019-9958(59)90362-6 .
5. Ноам Хомский, ред. (1957). Синтаксические структуры . Mouton & Co. Publishers, Гаага, Нидерланды.
6. Dowell R. & Eddy S. (2004). "Оценка нескольких облегченных стохастических контекстно-свободных грамматик для предсказания вторичной структуры РНК". BMC Bioinformatics . 5 (71): 71. doi : 10.1186/1471-2105-5-71 . PMC 442121 . PMID  15180907. 
7. Смит, Ноа А.; Джонсон, Марк (2007). «Взвешенные и вероятностные контекстно-свободные грамматики одинаково выразительны» (PDF) . Компьютерная лингвистика . 33 (4): 477. doi :10.1162/coli.2007.33.4.477. S2CID  1405777.
8. Katsirelos, George; Narodytska, Nina; Walsh, Toby (2008). "The Weighted CFG Constraint". Интеграция методов ИИ и OR в программировании ограничений для задач комбинаторной оптимизации . Lecture Notes in Computer Science. Vol. 5015. pp. 323–327. CiteSeerX 10.1.1.150.1187 . doi :10.1007/978-3-540-68155-7_31. ISBN  978-3-540-68154-0. S2CID  9375313.
9. Джонсон, Марк (2005). «логарифмически линейные или модели Гиббса» (PDF) .
10. Чи, Чжии (март 1999). "Статистические свойства вероятностных контекстно-свободных грамматик" (PDF) . Компьютерная лингвистика . 25 (1): 131–160. Архивировано из оригинала (PDF) 2010-08-21.
11. Эдди SR и Дурбин Р. (1994). "Анализ последовательности РНК с использованием ковариационных моделей". Nucleic Acids Research . 22 (11): 2079–2088. doi :10.1093/nar/22.11.2079. PMC 308124. PMID 8029015  . 
12. Сакакибара Y.; Браун M.; Хьюи R.; Миан IS; и др. (1994). «Стохастические контекстно-свободные грамматики для моделирования тРНК». Nucleic Acids Research . 22 (23): 5112–5120. doi :10.1093/nar/22.23.5112. PMC 523785. PMID  7800507 . 
13. Грат, Л. (1995). «Автоматическое определение вторичной структуры РНК с помощью стохастических контекстно-свободных грамматик» (PDF) . В Rawlings, C., Clark, D., Altman, R., Hunter, L., Lengauer, T и Wodak, S. Труды Третьей международной конференции по интеллектуальным системам для молекулярной биологии, AAAI Press : 136–144. Архивировано из оригинала (PDF) 2015-12-04 . Получено 2017-08-03 .
14. Лефевр, Ф. (1995). «Оптимизированный алгоритм синтаксического анализа, хорошо подходящий для сворачивания РНК». В Роулингс, К.; Кларк, Д.; Альтман, Р.; Хантер, Л.; Ленгауэр, Т.; Водак, С. (ред.). Труды Третьей международной конференции по интеллектуальным системам для молекулярной биологии (PDF) . AAAI Press. стр. 222–230.
15. Лефевр, Ф. (1996). «Объединение нескольких алгоритмов выравнивания и сворачивания на основе грамматики». В States, DJ; Агарвал, П.; Гаастерлан, Т.; Хантер, Л.; Смит РФ (ред.). Труды Четвертой международной конференции по интеллектуальным системам для молекулярной биологии (PDF) . AAAI Press. стр. 143–153.
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.
17. Хуан В.; Уилсон К. (1999). «Предсказание вторичной структуры РНК на основе свободной энергии и филогенетического анализа». J. Mol. Biol . 289 (4): 935–947. doi :10.1006/jmbi.1999.2801. PMID  10369773.
18. Zuker M (2000). «Расчет вторичной структуры нуклеиновых кислот». Curr. Opin. Struct. Biol . 10 (3): 303–310. doi :10.1016/S0959-440X(00)00088-9. PMID  10851192.
19. Mathews DH; Sabina J.; Zuker M.; Turner DH (1999). «Расширенная зависимость термодинамических параметров от последовательности улучшает предсказание вторичной структуры РНК». J. Mol. Biol . 288 (5): 911–940. doi : 10.1006/jmbi.1999.2700 . PMID  10329189. S2CID  19989405.
20. B. Knudsen & J. Hein. (2003). "Pfold: предсказание вторичной структуры РНК с использованием стохастических контекстно-свободных грамматик". Nucleic Acids Research . 31 (13): 3423–3428. doi :10.1093/nar/gkg614. PMC 169020. PMID  12824339 . 
21. Knudsen B.; Hein J. (1999). «Предсказание вторичной структуры РНК с использованием стохастических контекстно-свободных грамматик и эволюционной истории». Биоинформатика . 15 (6): 446–454. doi : 10.1093/bioinformatics/15.6.446 . PMID  10383470.
22. Ривас Э.; Эдди СР (2001). «Обнаружение генов некодирующей РНК с использованием сравнительного анализа последовательностей». BMC Bioinformatics . 2 (1): 8. doi : 10.1186/1471-2105-2-8 . PMC 64605. PMID  11801179. 
23. Холмс И.; Рубин ГМ (2002). Сравнение парных структур РНК со стохастическими контекстно-свободными грамматиками . стр. 163–174. doi :10.1142/9789812799623_0016. ISBN 978-981-02-4777-5. PMID  11928472. {{cite book}}: |journal=проигнорировано ( помощь )
24. PP Gardner; J. Daub; J. Tate; BL Moore; IH Osuch; S. Griffiths-Jones; RD Finn; EP Nawrocki; DL Kolbe; SR Eddy; A. Bateman. (2011). "Rfam: Wikipedia, clans and the "decimal" release". Nucleic Acids Research . 39 (Suppl 1): D141–D145. doi :10.1093/nar/gkq1129. PMC 3013711. PMID  21062808 . 
25. Яо З.; Вайнберг З.; Руццо В. Л. (2006). «CMfinder — алгоритм поиска мотивов РНК на основе ковариационной модели». Биоинформатика . 22 (4): 445–452. doi : 10.1093/bioinformatics/btk008 . PMID  16357030.
26. Рабани М.; Кертес М.; Сегал Э. (2008). «Вычислительное предсказание структурных мотивов РНК, участвующих в посттранскрипционных регуляторных процессах». Proc. Natl. Acad. Sci. USA . 105 (39): 14885–14890. Bibcode : 2008PNAS..10514885R. doi : 10.1073/pnas.0803169105 . PMC 2567462. PMID  18815376 . 
27. Goodarzi H.; Najafabadi HS; Oikonomou P.; Greco TM; Fish L.; Salavati R.; Cristea IM; Tavazoie S. (2012). «Систематическое открытие структурных элементов, регулирующих стабильность информационных РНК млекопитающих». Nature . 485 (7397): 264–268. Bibcode :2012Natur.485..264G. doi :10.1038/nature11013. PMC 3350620 . PMID  22495308. 
28. Сипсер М. (1996). Введение в теорию вычислений . Brooks Cole Pub Co.
29. Майкл А. Харрисон (1978). Введение в формальную теорию языка . Эддисон-Уэсли.
30. Хопкрофт Дж. Э.; Ульман Дж. Д. (1979). Введение в теорию автоматов, языков и вычислений . Эддисон-Уэсли.
31. Giegerich R. (2000). "Explaining and Controlling Ambiguity in Dynamic Programming". Комбинаторное сопоставление с образцом . Lecture Notes in Computer Science. Vol. 1848. In Proceedings of the 11th Annual Symposium on Combinatory Pattern Matching 1848 Под редакцией: Giancarlo R., Sankoff D. Montréal, Canada: Springer-Verlag, Berlin. pp. 46–59. doi :10.1007/3-540-45123-4_6. ISBN 978-3-540-67633-1. S2CID  17088251.
32. Lari K.; Young SJ (1990). «Оценка стохастических контекстно-свободных грамматик с использованием алгоритма «изнутри-вне»». Computer Speech and Language . 4 : 35–56. doi :10.1016/0885-2308(90)90022-X.
33. Lari K.; Young SJ (1991). «Применение стохастических контекстно-свободных грамматик с использованием алгоритма «изнутри-снаружи»». Computer Speech and Language . 5 (3): 237–257. doi :10.1016/0885-2308(91)90009-F.
34. Nawrocki EP, Eddy SR (2013). «Infernal 1.1:100-fold faster RNA homology searches». Биоинформатика . 29 (22): 2933–2935. doi : 10.1093/bioinformatics/btt509. PMC 3810854. PMID  24008419. 
35. Таваре С. (1986). «Некоторые вероятностные и статистические проблемы анализа последовательностей ДНК». Лекции по математике в науках о жизни. Американское математическое общество . 17 : 57–86.
36. Muse SV (1995). «Эволюционный анализ последовательностей ДНК с учетом ограничений вторичной структуры». Genetics . 139 (3): 1429–1439. doi :10.1093/genetics/139.3.1429. PMC 1206468 . PMID  7768450. 
37. Schöniger M.; von Haeseler A. (1994). «Стохастическая модель эволюции автокоррелированных последовательностей ДНК». Mol. Phylogenet. Evol . 3 (3): 240–7. Bibcode :1994MolPE...3..240S. doi :10.1006/mpev.1994.1026. PMID  7529616.
38. Бейкер, Дж. К. (1979). «Обучаемые грамматики для распознавания речи». Журнал Акустического общества Америки . 65 (S1): S132. Bibcode : 1979ASAJ...65Q.132B. doi : 10.1121/1.2017061 .
39. Searls, D (2013). «Обзор: Учебник по макромолекулярной лингвистике». Биополимеры . 99 (3): 203–217. doi :10.1002/bip.22101. PMID  23034580. S2CID  12676925.
40. Krogh, A; Brown, M; Mian, I; Sjolander, K; Haussler, D (1994). «Скрытые марковские модели в вычислительной биологии: приложения к моделированию белков». J Mol Biol . 235 (5): 1501–1531. doi :10.1006/jmbi.1994.1104. PMID  8107089. S2CID  2160404.
41. Сигрист, C; Черутти, Л; Хуло, Н; Гаттикер, А; Фальке, Л; Паньи, М; Байрох, А; Бучер, П. (2002). «PROSITE: документированная база данных, использующая шаблоны и профили в качестве дескрипторов мотивов». Краткий Биоинформ . 3 (3): 265–274. дои : 10.1093/нагрудник/3.3.265 . ПМИД  12230035.

Внешние ссылки

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