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

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

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

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

Определения

Деривация: процесс рекурсивной генерации строк из грамматики.

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

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

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

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

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

G=(M,T,R,S,P)

где

$M$ — набор нетерминальных символов
$T$ — набор терминальных символов
$R$ — набор правил производства
$S$ — стартовый символ
$P$ - набор вероятностей правил производства.

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

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

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

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

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

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

S\to aS,S\to bS,S\to \epsilon

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

S\to aS|bS|\epsilon

Терминалы в грамматике — это слова, и с помощью правил грамматики нетерминальный символ преобразуется в строку, состоящую из терминалов и/или нетерминалов. Приведенная выше грамматика читается как «начиная с нетерминала $S,$ излучение может генерировать либо $a,$ либо $b$ , либо $\epsilon$ ". Его вывод:

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]

S\to aSa|bSb|aa|bb

Приведенная выше грамматика генерирует строку снаружи внутрь, то есть сначала выводится пара оснований на самых дальних крайних точках терминала. Итак, строка типа $aabaabaa$ получается путем первого создания дистальных $a$ с обеих сторон перед перемещением внутрь:

S\Rightarrow aSa\Rightarrow aaSaa\Rightarrow aabSbaa\Rightarrow aabaabaa

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

Каждой возможной строке $x,$ которую генерирует грамматика, присваивается вес вероятности. $P(x|\theta )$ учитывая модель PCFG $\theta$ . Отсюда следует, что сумма всех вероятностей всех возможных грамматических произведений равна $\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

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

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

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

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

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

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

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

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

При структурном выравнивании вероятности столбцов с непарными основаниями и столбцов с парными основаниями не зависят от других столбцов. Подсчитав основания в одиночных и парных позициях, можно получить частоты оснований в петлях и основах. Для пар оснований $X$ и $Y$ появление $XY$ также считается возникновением $YX$ . Идентичные пары оснований, такие как $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: ^[35]

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

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

Оцените вероятности выравнивания

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

P(D|T,M)

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

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

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

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

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

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

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

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

Прогнозирование вероятности структуры

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

\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-система

Ссылки

^ Хомский, Ноам (1956). «Три модели описания языка». IRE Транзакции по теории информации . 2 (3): 113–124. дои : 10.1109/TIT.1956.1056813 . S2CID 19519474 .
^ Хомский, Ноам (июнь 1959 г.). «О некоторых формальных свойствах грамматик» . Информация и контроль . 2 (2): 137–167. дои : 10.1016/S0019-9958(59)90362-6 .
^ Jump up to: ^а ^б Ноам Хомский, изд. (1957). Синтаксические структуры . Издательство Mouton & Co., Ден Хааг, Нидерланды.
^ Jump up to: ^а ^б ^с ^д ^и ^ж Эдди С.Р. и Дурбин Р. (1994). «Анализ последовательности РНК с использованием ковариационных моделей» . Исследования нуклеиновых кислот . 22 (11): 2079–2088. дои : 10.1093/нар/22.11.2079 . ПМК 308124 . ПМИД 8029015 .
^ Jump up to: ^а ^б ^с ^д Сакакибара Ю.; Браун М.; Хьюи Р.; Миан И.С.; и др. (1994). «Стохастические контекстно-свободные грамматики для моделирования тРНК» . Исследования нуклеиновых кислот . 22 (23): 5112–5120. дои : 10.1093/нар/22.23.5112 . ПМК 523785 . ПМИД 7800507 .
^ Грат, Л. (1995). «Автоматическое определение вторичной структуры РНК с помощью стохастических контекстно-свободных грамматик» (PDF) . В: Роулингс К., Кларк Д., Альтман Р., Хантер Л., Ленгауэр Т. и Водак С. Материалы Третьей международной конференции по интеллектуальным системам для молекулярной биологии, AAAI Press : 136–144. Архивировано из оригинала (PDF) 4 декабря 2015 г. Проверено 3 августа 2017 г.
^ Лефевр, Ф (1995). «Оптимизированный алгоритм анализа, хорошо подходящий для сворачивания РНК». В Роулингсе, К.; Кларк, Д.; Альтман, Р.; Хантер, Л.; Ленгауэр, Т.; Водак, С. (ред.). Материалы Третьей Международной конференции по интеллектуальным системам молекулярной биологии (PDF) . АААИ Пресс. стр. 222–230.
^ Лефевр, Ф. (1996). «Объединение нескольких алгоритмов выравнивания и свертывания на основе грамматики». В Штатах диджей; Агарвал, П.; Гастерлан, Т.; Хантер, Л.; Смит РФ (ред.). Материалы Четвертой Международной конференции по интеллектуальным системам молекулярной биологии (PDF) . АААИ Пресс. стр. 143–153.
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н Р. Дурбин; С. Эдди; А. Крог; Г. Митчинсон (1998). Анализ биологических последовательностей: вероятностные модели белков и нуклеиновых кислот . Издательство Кембриджского университета. ISBN 978-0-521-62971-3 .
^ Кляйн, Дэниел; Мэннинг, Кристофер (2003). «Точный нелексикализованный синтаксический анализ» (PDF) . Материалы 41-го собрания Ассоциации компьютерной лингвистики : 423–430.
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г Доуэлл Р. и Эдди С. (2004). «Оценка нескольких облегченных стохастических бесконтекстных грамматик для предсказания вторичной структуры РНК» . БМК Биоинформатика . 5 (71): 71. дои : 10.1186/1471-2105-5-71 . ПМК 442121 . ПМИД 15180907 .
^ Jump up to: ^а ^б Смит, Ной А.; Джонсон, Марк (2007). «Взвешенные и вероятностные бесконтекстные грамматики одинаково выразительны» (PDF) . Компьютерная лингвистика . 33 (4): 477. doi : 10.1162/coli.2007.33.4.477 . S2CID 1405777 .
^ Кацирелос, Джордж; Народицкая, Нина; Уолш, Тоби (2008). «Взвешенное ограничение CFG» . Интеграция методов искусственного интеллекта и ИЛИ в программировании с ограничениями для задач комбинаторной оптимизации . Конспекты лекций по информатике. Том. 5015. стр. 323–327. CiteSeerX 10.1.1.150.1187 . дои : 10.1007/978-3-540-68155-7_31 . ISBN 978-3-540-68154-0 . S2CID 9375313 .
^ Джонсон, Марк (2005). «Линейные логарифмические модели или модели Гиббса» (PDF) .
^ Чи, Чжии (март 1999 г.). «Статистические свойства вероятностных контекстно-свободных грамматик» (PDF) . Компьютерная лингвистика . 25 (1): 131–160. Архивировано из оригинала (PDF) 21 августа 2010 г.
^ Маккаскилл Дж.С. (1990). «Равновесная статистическая сумма и вероятности связывания пар оснований для вторичной структуры РНК». Биополимеры . 29 (6–7): 1105–19. дои : 10.1002/bip.360290621 . hdl : 11858/00-001M-0000-0013-0DE3-9 . ПМИД 1695107 . S2CID 12629688 .
^ Хуан В.; Уилсон К. (1999). «Прогнозирование вторичной структуры РНК на основе свободной энергии и филогенетического анализа». Дж. Мол. Биол . 289 (4): 935–947. дои : 10.1006/jmbi.1999.2801 . ПМИД 10369773 .
^ Цукер М (2000). «Расчет вторичной структуры нуклеиновой кислоты». Курс. Мнение. Структура. Биол . 10 (3): 303–310. дои : 10.1016/S0959-440X(00)00088-9 . ПМИД 10851192 .
^ Мэтьюз Д.Х.; Сабина Дж.; Цукер М.; Тернер Д.Х. (1999). «Расширенная зависимость термодинамических параметров от последовательности улучшает предсказание вторичной структуры РНК» . Дж. Мол. Биол . 288 (5): 911–940. дои : 10.1006/jmbi.1999.2700 . ПМИД 10329189 . S2CID 19989405 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час Б. Кнудсен и Дж. Хейн. (2003). «Pfold: предсказание вторичной структуры РНК с использованием стохастических контекстно-свободных грамматик» . Исследования нуклеиновых кислот . 31 (13): 3423–3428. дои : 10.1093/нар/gkg614 . ПМК 169020 . ПМИД 12824339 .
^ Jump up to: ^а ^б ^с Кнудсен Б.; Хейн Дж. (1999). «Прогнозирование вторичной структуры РНК с использованием стохастических контекстно-свободных грамматик и истории эволюции» . Биоинформатика . 15 (6): 446–454. дои : 10.1093/биоинформатика/15.6.446 . ПМИД 10383470 .
^ Ривас Э.; Эдди С.Р. (2001). «Обнаружение генов некодирующей РНК с использованием сравнительного анализа последовательностей» . БМК Биоинформатика . 2 (1): 8. дои : 10.1186/1471-2105-2-8 . ПМК 64605 . ПМИД 11801179 .
^ Холмс И.; Рубин ГМ (2002). Сравнение попарных структур РНК со стохастическими контекстно-свободными грамматиками . стр. 163–174 . дои : 10.1142/9789812799623_0016 . ISBN 978-981-02-4777-5 . ПМИД 11928472 . {{cite book}}: |journal= игнорируется ( помогите )
^ Jump up to: ^а ^б П. П. Гарднер; Дж. Дауб; Дж. Тейт; Б.Л. Мур; И. Х. Осуч; С. Гриффитс-Джонс; РД Финн; Е.П. Навроцкий; Д.Л. Кольбе; С.Р. Эдди; А. Бейтман. (2011). «Рфам: Arc.Ask3.Ru, кланы и «десятичный» релиз» . Исследования нуклеиновых кислот . 39 (Приложение 1): Д141–Д145. дои : 10.1093/nar/gkq1129 . ПМК 3013711 . ПМИД 21062808 .
^ Яо З.; Вайнберг З.; Руццо В.Л. (2006). «CMfinder - алгоритм поиска мотивов РНК на основе ковариационной модели» . Биоинформатика . 22 (4): 445–452. doi : 10.1093/биоинформатика/btk008 . ПМИД 16357030 .
^ Рабани М.; Кертес М.; Сигал Э. (2008). «Вычислительное предсказание структурных мотивов РНК, участвующих в посттранскрипционных регуляторных процессах» . Учеб. Натл. акад. наук. США . 105 (39): 14885–14890. Бибкод : 2008PNAS..10514885R . дои : 10.1073/pnas.0803169105 . ПМК 2567462 . ПМИД 18815376 .
^ Гударзи Х.; Наджафабади Х.С.; Ойконому П.; Греко ТМ; Рыбная Л.; Салавати Р.; Кристя ИМ; Тавазои С. (2012). «Систематическое открытие структурных элементов, определяющих стабильность информационных РНК млекопитающих» . Природа . 485 (7397): 264–268. Бибкод : 2012Natur.485..264G . дои : 10.1038/nature11013 . ПМК 3350620 . ПМИД 22495308 .
^ Сипсер М. (1996). Введение в теорию вычислений . Брукс Коул Паб Ко.
^ Майкл А. Харрисон (1978). Введение в теорию формального языка . Аддисон-Уэсли.
^ Хопкрофт Дж. Э.; Ульман Дж.Д. (1979). Введение в теорию автоматов, языки и вычисления . Аддисон-Уэсли.
^ Гигерих Р. (2000). «Объяснение и контроль неоднозначности в динамическом программировании». Комбинаторное сопоставление с образцом . Конспекты лекций по информатике. Том. 1848. В материалах 11-го ежегодного симпозиума по сопоставлению комбинаторных образцов 1848 года. Под редакцией: Джанкарло Р., Санкофф Д. Монреаль, Канада: Springer-Verlag, Берлин. стр. 46–59. дои : 10.1007/3-540-45123-4_6 . ISBN 978-3-540-67633-1 . S2CID 17088251 .
^ Jump up to: ^а ^б ^с Лари К.; Молодой SJ (1990). «Оценка стохастических контекстно-свободных грамматик с использованием алгоритма внутри-вне». Компьютерная речь и язык . 4 : 35–56. дои : 10.1016/0885-2308(90)90022-X .
^ Jump up to: ^а ^б ^с Лари К.; Молодой SJ (1991). «Применение стохастических контекстно-свободных грамматик с использованием алгоритма внутри-вне». Компьютерная речь и язык . 5 (3): 237–257. дои : 10.1016/0885-2308(91)90009-F .
^ Навроцкий Е.П., Эдди С.Р. (2013). «Адский поиск гомологии РНК в 1,1:100 раз быстрее» . Биоинформатика . 29 (22): 2933–2935. doi : 10.1093/биоинформатика/btt509 . ПМЦ 3810854 . ПМИД 24008419 .
^ Таваре С. (1986). «Некоторые вероятностные и статистические проблемы анализа последовательностей ДНК». Лекции по математике в науках о жизни. Американское математическое общество . 17 : 57–86.
^ Муза С.В. (1995). «Эволюционный анализ последовательностей ДНК с учетом ограничений вторичной структуры» . Генетика . 139 (3): 1429–1439. дои : 10.1093/генетика/139.3.1429 . ПМК 1206468 . PMID 7768450 .
^ Шёнигер М.; фон Хэзелер А. (1994). «Стохастическая модель эволюции автокоррелированных последовательностей ДНК». Мол. Филогенет. Эвол . 3 (3): 240–7. Бибкод : 1994МОЛПЭ...3..240С . дои : 10.1006/mpev.1994.1026 . ПМИД 7529616 .
^ Бейкер, Дж. К. (1979). «Обучаемые грамматики для распознавания речи» . Журнал Акустического общества Америки . 65 (С1): С132. Бибкод : 1979ASAJ...65Q.132B . дои : 10.1121/1.2017061 .
^ Jump up to: ^а ^б Сирлс, Д. (2013). «Обзор: Учебник по макромолекулярной лингвистике». Биополимеры . 99 (3): 203–217. дои : 10.1002/bip.22101 . ПМИД 23034580 . S2CID 12676925 .
^ Крог, А; Браун, М; Миан, я; Шоландер, К; Хаусслер, Д. (1994). «Скрытые марковские модели в вычислительной биологии: приложения к моделированию белков». Дж Мол Биол . 235 (5): 1501–1531. дои : 10.1006/jmbi.1994.1104 . ПМИД 8107089 . S2CID 2160404 .
^ Сигрист, С; Черутти, Л; Хуло, Н; Гаттикер, А; Фальке, Л; Паньи, М; Байрох, А; Бучер, П. (2002). «ПРОСАЙТ: документированная база данных, использующая шаблоны и профили в качестве дескрипторов мотивов» . Краткий Биоинформ . 3 (3): 265–274. дои : 10.1093/нагрудник/3.3.265 . ПМИД 12230035 .

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

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

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

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

[Eddy_1994-4] Jump up to: ^а ^б ^с ^д ^и ^ж Эдди С.Р. и Дурбин Р. (1994). «Анализ последовательности РНК с использованием ковариационных моделей» . Исследования нуклеиновых кислот . 22 (11): 2079–2088. дои : 10.1093/нар/22.11.2079 . ПМК 308124 . ПМИД 8029015 .

[Sakakibara_1994-5] Jump up to: ^а ^б ^с ^д Сакакибара Ю.; Браун М.; Хьюи Р.; Миан И.С.; и др. (1994). «Стохастические контекстно-свободные грамматики для моделирования тРНК» . Исследования нуклеиновых кислот . 22 (23): 5112–5120. дои : 10.1093/нар/22.23.5112 . ПМК 523785 . ПМИД 7800507 .

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

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

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

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

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

[Dowell_2004-11] Jump up to: ^а ^б ^с ^д ^и ^ж ^г Доуэлл Р. и Эдди С. (2004). «Оценка нескольких облегченных стохастических бесконтекстных грамматик для предсказания вторичной структуры РНК» . БМК Биоинформатика . 5 (71): 71. дои : 10.1186/1471-2105-5-71 . ПМК 442121 . ПМИД 15180907 .

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

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

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

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

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

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

[Zuker_2000-18] Цукер М (2000). «Расчет вторичной структуры нуклеиновой кислоты». Курс. Мнение. Структура. Биол . 10 (3): 303–310. дои : 10.1016/S0959-440X(00)00088-9 . ПМИД 10851192 .

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

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

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

[Rivas_2001-22] Ривас Э.; Эдди С.Р. (2001). «Обнаружение генов некодирующей РНК с использованием сравнительного анализа последовательностей» . БМК Биоинформатика . 2 (1): 8. дои : 10.1186/1471-2105-2-8 . ПМК 64605 . ПМИД 11801179 .

[Holmes_2002-23] Холмс И.; Рубин ГМ (2002). Сравнение попарных структур РНК со стохастическими контекстно-свободными грамматиками . стр. 163–174 . дои : 10.1142/9789812799623_0016 . ISBN 978-981-02-4777-5 . ПМИД 11928472 . {{cite book}}: |journal= игнорируется ( помогите )

[Gardner_2010-24] Jump up to: ^а ^б П. П. Гарднер; Дж. Дауб; Дж. Тейт; Б.Л. Мур; И. Х. Осуч; С. Гриффитс-Джонс; РД Финн; Е.П. Навроцкий; Д.Л. Кольбе; С.Р. Эдди; А. Бейтман. (2011). «Рфам: Arc.Ask3.Ru, кланы и «десятичный» релиз» . Исследования нуклеиновых кислот . 39 (Приложение 1): Д141–Д145. дои : 10.1093/nar/gkq1129 . ПМК 3013711 . ПМИД 21062808 .

[Yao_2006-25] Яо З.; Вайнберг З.; Руццо В.Л. (2006). «CMfinder - алгоритм поиска мотивов РНК на основе ковариационной модели» . Биоинформатика . 22 (4): 445–452. doi : 10.1093/биоинформатика/btk008 . ПМИД 16357030 .

[Rabani_2008-26] Рабани М.; Кертес М.; Сигал Э. (2008). «Вычислительное предсказание структурных мотивов РНК, участвующих в посттранскрипционных регуляторных процессах» . Учеб. Натл. акад. наук. США . 105 (39): 14885–14890. Бибкод : 2008PNAS..10514885R . дои : 10.1073/pnas.0803169105 . ПМК 2567462 . ПМИД 18815376 .

[Goodarzi_2012-27] Гударзи Х.; Наджафабади Х.С.; Ойконому П.; Греко ТМ; Рыбная Л.; Салавати Р.; Кристя ИМ; Тавазои С. (2012). «Систематическое открытие структурных элементов, определяющих стабильность информационных РНК млекопитающих» . Природа . 485 (7397): 264–268. Бибкод : 2012Natur.485..264G . дои : 10.1038/nature11013 . ПМК 3350620 . ПМИД 22495308 .

[Sipser_1996-28] Сипсер М. (1996). Введение в теорию вычислений . Брукс Коул Паб Ко.

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

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

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

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

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

[Nawrocki_2013-34] Навроцкий Е.П., Эдди С.Р. (2013). «Адский поиск гомологии РНК в 1,1:100 раз быстрее» . Биоинформатика . 29 (22): 2933–2935. doi : 10.1093/биоинформатика/btt509 . ПМЦ 3810854 . ПМИД 24008419 .

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

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

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

[Baker_1979-38] Бейкер, Дж. К. (1979). «Обучаемые грамматики для распознавания речи» . Журнал Акустического общества Америки . 65 (С1): С132. Бибкод : 1979ASAJ...65Q.132B . дои : 10.1121/1.2017061 .

[Searls_D_2013-39] Jump up to: ^а ^б Сирлс, Д. (2013). «Обзор: Учебник по макромолекулярной лингвистике». Биополимеры . 99 (3): 203–217. дои : 10.1002/bip.22101 . ПМИД 23034580 . S2CID 12676925 .

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

[41] Сигрист, С; Черутти, Л; Хуло, Н; Гаттикер, А; Фальке, Л; Паньи, М; Байрох, А; Бучер, П. (2002). «ПРОСАЙТ: документированная база данных, использующая шаблоны и профили в качестве дескрипторов мотивов» . Краткий Биоинформ . 3 (3): 265–274. дои : 10.1093/нагрудник/3.3.265 . ПМИД 12230035 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]