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

Теория грамматики для моделирования символьных строк возникла в результате работы в области компьютерной лингвистики, направленной на понимание структуры естественных языков . Вероятностный контекст свободных грамматик ( PCFGs ) были применены в вероятностного моделирования из структур РНК почти 40 лет после того, как они были введены в компьютерной лингвистике .

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

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

Определения

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

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

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

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

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

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

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

куда

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

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

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

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

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

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

Бесконтекстные грамматики представлены как набор правил, вдохновленных попытками моделирования естественных языков. Правила являются абсолютными и имеют типичное синтаксическое представление, известное как форма Бэкуса – Наура . Правила производства состоят из оконечных и нетерминальных $S-$ символов, и в качестве конечной точки также может использоваться пробел . В производственных правилах CFG и PCFG левая сторона имеет только один нетерминал, тогда как правая сторона может быть любой строкой терминалов или нетерминалов. В PCFG нули исключены. Пример грамматики: ${\ 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 неприменимы для предсказания структуры РНК, потому что, хотя они включают взаимосвязь последовательность-структура, им не хватает показателей оценки, которые раскрывают структурный потенциал последовательности.

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

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

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

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

Приложения

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

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

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

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

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

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

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

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

Реализации

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

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

Существуют разные реализации этих подходов. Например, Pfold используется для предсказания вторичной структуры из группы связанных последовательностей РНК, ковариационные модели используются для поиска в базах данных гомологичных последовательностей, аннотации и классификации РНК, RNApromo, CMFinder и TEISER используются для поиска стабильных структурных мотивов в РНК.

Соображения по дизайну

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

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

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

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

Построение модели 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 способствует хорошей точности прогнозов.

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

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

while  $X\neq Y$ 
                $C_{\text{XY}}+1$  first sequence  pair
                $C_{\text{YX}}+1$  second sequence pair

Calculate mutation rates.
               Let   $r_{\text{XY}}=$  mutation of base X to base Y  $={\frac {K~C_{\text{XY}}}{P_{x}P_{s}}}$ 
               Let   $r_{\text{XX}}=$  the negative of the rate of X mutation to other bases  $=-\sum r_{\text{XY}}$ 
                $P_{s}=$  the probability that the base is not paired.

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

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

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

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

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

{\ Displaystyle P (D | T, M)}

{\ Displaystyle = \ сумма P (D, \ sigma | T, M)}

{\ Displaystyle = \ сумма P (D | \ sigma, T, M) P (\ sigma | T, M)}

{\ Displaystyle = \ сумма P (D | \ sigma, T, M) P (\ sigma | M)}

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

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

{\ Displaystyle S \ к LS (80 \%) | L (20 \%)}

{\ Displaystyle L \ к s (70 \%) | dFd (30 \%)}

{\ Displaystyle F \ в dFd (60,4 \%) | LS (39,6 \%)}

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

Учитывая предшествующие частоты выравнивания данных, наиболее вероятная структура ансамбля, предсказанная грамматикой, затем может быть вычислена путем максимизации с помощью алгоритма CYK. Структура с наибольшим прогнозируемым количеством правильных прогнозов сообщается как консенсусная структура. ${\ 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 в отношении масштабируемости, пропусков, скорости и точности.

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

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

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

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

Languages

In other projects