Shannon Entropy

9.1 Introduction

Chomsky initially formalized context-free grammars (CFGs) as an attempt to model languages. Desde então, eles têm sido amplamente utilizados em uma variedade de aplicações de ciência da computação. CFGs têm uma natureza recursiva e são compostos de conjuntos de regras que podem conduzir cadeias de alfabetos, também referidos como palavras. O conjunto de palavras geradas por uma gramática é referido como a linguagem dessa gramática. Uma gramática é dita não ambígua se houver uma correspondência um-para-um entre as palavras e suas derivações descritivas. CFGs estocásticos (SCFGs) atribuem probabilidades a cada regra, que por sua vez atribui um valor de probabilidade a cada palavra, multiplicando as probabilidades das regras usadas para derivar essa palavra . Grenander , Kuich , Hutchins , Soule e outros têm investigado propriedades importantes de CFGs e SCFGs, tais como a convergência de duração média de derivações, a capacidade ou a entropia de Shannon (Shannon entropy), tal como definido , usando a geração de funções técnicas. O esquema de estrutura secundária do RNA também tem uma natureza livre de contexto, permitindo que seja descrito por tais gramáticas. A estrutura secundária RNA foi primeiramente descrita formalmente por Smith e Waterman . Características combinatórias de estruturas secundárias RNA foram então exploradas por Stein e Waterman e posteriormente estudadas por Viennot e Vauchaussade de Chaumont , Hofacker et al. , Nebel, Liao e Wang, Doslic et al. e outros que utilizem funções geradoras e funções geradoras de probabilidade.os SCFGs tiveram um grande impacto nos estudos de estrutura secundária de ARN . A modelagem de estrutura secundária de RNA nos ajuda a fazer previsões sobre a estrutura de RNA e sua função biológica subsequente, já que as funções de muitas RNAs, como várias classes de RNAs não codificantes (ncRNA) estão relacionadas com suas estruturas. Tipicamente, a predição da estrutura secundária RNA é feita pela minimização da energia de dobragem da sequência sob um modelo de dobragem baseado em termodinâmica, como o conjunto Boltzmann . SCFGs, por outro lado, são modelos de covariância que podem imitar a dobragem de RNA com mais flexibilidade. No caso de um modelo dobrável baseado no SCFG, os valores de probabilidade são atribuídos a todos os cenários possíveis de dobragem de uma sequência de ARN. Em seguida, a estrutura com o valor máximo de probabilidade (ML) é prevista como a estrutura secundária da sequência de RNA. ML prediction of SCFG-based models can be done by the Cocke-Younger-Kasami (CYK) algorithm. Similar à minimização de energia, o algoritmo de CYK é implementado através de programação dinâmica. O objetivo do projeto do modelo é obter estimativas ML que são tão semelhantes às estruturas secundárias de RNA conhecidas quanto possível, tornando assim a atribuição de probabilidades às regras uma tarefa crítica e desafiadora. Rivas oferece uma visão mais aprofundada sobre vários aspectos da modelagem de estrutura secundária de RNA.

maximização de expectativa atual (EM) abordagens de treinamento modelo geralmente consistem nos seguintes dois passos: Primeiro, o algoritmo de CYK é usado para a previsão de estrutura de cada sequência de RNA do conjunto de treinamento (etapa de maximização). Em segundo lugar, as probabilidades de regra do SCFG são reavaliadas com base nas contagens ou frequências das suas ocorrências nas previsões (etapa de estimativa). Estas estimativas podem ser calculadas utilizando a abordagem anterior de Laplace explicada em Durbin et al. ou a lançar abordagens semelhantes baseadas em frequências. O procedimento em iterativo pode continuar até que as probabilidades resultantes da regra produzam a precisão desejada. As técnicas de formação de modelos podem variar, quer na definição do critério ML (Conjunto vs. condicional), quer nas técnicas de estimativa da probabilidade de regra . Um modelo baseado em SCFG pode consistir de um SCFG leve com apenas algumas regras gramaticais ou pode ser uma gramática pesada consistindo de muitas regras, tais como super-gramáticas descritas em Rivas et al. .

neste trabalho, a entropia de Shannon do SCFG, denotada aqui como entropia do espaço gramatical (GS), é analiticamente calculada e introduzida como uma característica gramatical crítica na modelagem da estrutura secundária do RNA. Formulações apresentadas são consistentes com a forma geral de entropia gramatical conhecida como entropia derivacional, e pode ser encontrada em Grenander e Soule . Na Secção 9.2, a formulação é apresentada para o cálculo da entropia de Shannon para o infinitamente grande probabilística espaço estruturalmente inequívoca RNA-modelagem grammars1 que é consistente com o derivational entropia formulações apresentadas no Grenander . Os valores de entropia GS de vários modelos bem estabelecidos de dobragem de ARN são então calculados sob diferentes conjuntos de Parâmetros na secção 9.3. Na Secção 9.4, propõe-se um critério para a formação de modelos de estrutura secundária de ARN com base no SCFG, com base na entropia do GS. Por último, a secção 9.5 consiste em discussões e conclusões.