Gramática probabilística livre de contexto - Probabilistic context-free grammar

A teoria gramatical para modelar cadeias de símbolos originou-se de trabalhos em linguística computacional com o objetivo de compreender a estrutura das línguas naturais . Gramáticas probabilísticas livres de contexto ( PCFGs ) têm sido aplicadas na modelagem probabilística de estruturas de RNA quase 40 anos depois de terem sido introduzidas na linguística computacional .

Os PCFGs estendem gramáticas livres de contexto de maneira semelhante a como os modelos ocultos de Markov estendem gramáticas regulares . Cada produção recebe uma probabilidade. A probabilidade de uma derivação (parse) é o produto das probabilidades das produções usadas nessa derivação. Essas probabilidades podem ser vistas como parâmetros do modelo e, para grandes problemas, é conveniente aprender esses parâmetros por meio do aprendizado de máquina . A validade de uma gramática probabilística é restringida pelo contexto de seu conjunto de dados de treinamento.

Os PCFGs têm aplicação em áreas tão diversas como o processamento de linguagem natural para o estudo da estrutura de moléculas de RNA e design de linguagens de programação . Projetar PCFGs eficientes deve pesar fatores de escalabilidade e generalidade. Problemas como ambigüidade gramatical devem ser resolvidos. O design da gramática afeta a precisão dos resultados. Os algoritmos de análise gramatical têm vários requisitos de tempo e memória.

Definições

Derivação: O processo de geração recursiva de strings de uma gramática.

Análise : Encontrar uma derivação válida usando um autômato.

Árvore de análise: o alinhamento da gramática a uma sequência.

Um exemplo de analisador para gramáticas PCFG é o autômato pushdown . O algoritmo analisa não-terminais gramaticais da esquerda para a direita em uma forma de pilha . Essa abordagem de força bruta não é muito eficiente. Em variantes de previsão de estrutura secundária de RNA do algoritmo Cocke – Younger – Kasami (CYK) fornecem alternativas mais eficientes para a análise gramatical do que autômatos pushdown. Outro exemplo de analisador PCFG é o Stanford Statistical Parser, que foi treinado com o Treebank .

Definição formal

Semelhante a um CFG , uma gramática livre de contexto probabilística $G$ pode ser definida por um quíntuplo:

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

Onde

$M$ é o conjunto de símbolos não terminais
$T$ é o conjunto de símbolos terminais
$R$ é o conjunto de regras de produção
$S$ é o símbolo inicial
$P$ é o conjunto de probabilidades nas regras de produção

Relação com modelos ocultos de Markov

Os modelos PCFGs estendem gramáticas livres de contexto da mesma forma que os modelos ocultos de Markov estendem gramáticas regulares .

O algoritmo Inside-Outside é um análogo do algoritmo Forward-Backward . Ele calcula a probabilidade total de todas as derivações que são consistentes com uma determinada sequência, com base em algum PCFG. Isso é equivalente à probabilidade do PCFG gerar a sequência e é intuitivamente uma medida de quão consistente é a sequência com a gramática dada. O algoritmo Inside-Outside é usado na parametrização do modelo para estimar frequências anteriores observadas a partir de sequências de treinamento no caso de RNAs.

Variantes de programação dinâmica do algoritmo CYK encontram a análise de Viterbi de uma sequência de RNA para um modelo PCFG. Esta análise é a derivação mais provável da sequência pelo PCFG fornecido.

Construção gramatical

Gramáticas livres de contexto são representadas como um conjunto de regras inspiradas em tentativas de modelar linguagens naturais. As regras são absolutas e têm uma representação de sintaxe típica conhecida como forma Backus – Naur . As regras de produção consistem em símbolos $S$ terminais e não terminais e um espaço em branco também pode ser usado como um ponto final. Nas regras de produção de CFG e PCFG, o lado esquerdo tem apenas um não terminal, enquanto o lado direito pode ser qualquer sequência de terminais ou não terminais. No PCFG, os nulos são excluídos. Um exemplo de gramática: ${\ displaystyle \ left \ {a, b \ right \}}$ ${\ displaystyle \ epsilon}$

{\ displaystyle S \ para aS, S \ para bS, S \ para \ epsilon}

Esta gramática pode ser encurtada usando o caractere '|' ('ou') caractere em:

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

Terminais em uma gramática são palavras e através das regras gramaticais um símbolo não terminal é transformado em uma string de terminais e / ou não terminais. A gramática acima é lida como "começando de um $S$ não terminal, a emissão pode gerar $a$ ou $b$ ou ". Sua derivação é: ${\ displaystyle \ epsilon}$

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

A gramática ambígua pode resultar em análise ambígua se aplicada em homógrafos, uma vez que a mesma sequência de palavras pode ter mais de uma interpretação. Frases de trocadilho como a manchete de jornal "Cabeça iraquiana procura armas" são um exemplo de análises ambíguas.

Uma estratégia para lidar com parses ambíguos (originados com gramáticos já em Pāṇini ) é adicionar ainda mais regras ou priorizá-las de forma que uma regra tenha precedência sobre as outras. Isso, no entanto, tem a desvantagem de proliferar as regras, muitas vezes a ponto de se tornarem difíceis de administrar. Outra dificuldade é a geração excessiva, onde estruturas não licenciadas também são geradas.

Gramáticas probabilísticas contornam esses problemas classificando várias produções em pesos de frequência, resultando em uma interpretação "mais provável" (o vencedor leva tudo). Como os padrões de uso são alterados em deslocamentos diacrônicos , essas regras probabilísticas podem ser reaprendidas, atualizando assim a gramática.

Atribuir probabilidade às regras de produção cria um PCFG. Essas probabilidades são informadas pela observação das distribuições em um conjunto de treinamento de composição semelhante à linguagem a ser modelada. Na maioria dos exemplos de linguagem ampla, as gramáticas probabilísticas em que as probabilidades são estimadas a partir de dados normalmente superam as gramáticas feitas à mão. CFGs quando contrastados com PCFGs não são aplicáveis à previsão da estrutura do RNA porque, embora incorporem a relação sequência-estrutura, eles não possuem as métricas de pontuação que revelam um potencial estrutural da sequência

Gramática livre de contexto ponderada

Uma gramática livre de contexto ponderada ( WCFG ) é uma categoria mais geral de gramática livre de contexto , onde cada produção tem um peso numérico associado a ela. O peso de uma árvore de análise específica em um WCFG é o produto (ou soma) de todos os pesos das regras na árvore. Cada peso de regra é incluído tão frequentemente quanto a regra é usada na árvore. Um caso especial de WCFGs são PCFGs, onde os pesos são ( logaritmos de) probabilidades .

Uma versão estendida do algoritmo CYK pode ser usada para encontrar a derivação "mais leve" (de menor peso) de uma string dada algum WCFG.

Quando o peso da árvore é o produto dos pesos das regras, WCFGs e PCFGs podem expressar o mesmo conjunto de distribuições de probabilidade .

Formulários

Predição de estrutura de RNA

A minimização de energia e o PCFG fornecem maneiras de prever a estrutura secundária do RNA com desempenho comparável. No entanto, a previsão da estrutura por PCFGs é avaliada probabilisticamente, em vez de pelo cálculo de energia livre mínima. Os parâmetros do modelo PCFG são derivados diretamente de frequências de diferentes características observadas em bancos de dados de estruturas de RNA, e não por determinação experimental, como é o caso dos métodos de minimização de energia.

Os tipos de várias estruturas que podem ser modeladas por um PCFG incluem interações de longo alcance, estrutura em pares e outras estruturas aninhadas. No entanto, os pseudo-nós não podem ser modelados. Os PCFGs estendem o CFG atribuindo probabilidades a cada regra de produção. Uma árvore de análise de probabilidade máxima da gramática implica uma estrutura de probabilidade máxima. Já que os RNAs preservam suas estruturas sobre sua sequência primária; A previsão da estrutura do RNA pode ser guiada pela combinação de informações evolutivas da análise de sequência comparativa com o conhecimento biofísico sobre a plausibilidade de uma estrutura com base em tais probabilidades. Também os resultados da pesquisa para homólogos estruturais usando regras de PCFG são pontuados de acordo com as probabilidades de derivações de PCFG. Portanto, a construção de gramática para modelar o comportamento de pares de bases e regiões de fita simples começa com a exploração de recursos de alinhamento de sequência múltipla estrutural de RNAs relacionados.

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

A gramática acima gera uma string de fora para dentro, ou seja, o par de base nos extremos mais distantes do terminal é derivado primeiro. Então, um fio tal como é obtido pela primeira geração distal $um$ 's em ambos os lados, antes de passar para o interior: ${\ displaystyle aabaabaa}$

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

A extensibilidade do modelo PCFG permite a previsão da estrutura de restrição ao incorporar expectativas sobre diferentes características de um RNA. Tal expectativa pode refletir, por exemplo, a propensão de assumir uma determinada estrutura por um RNA. No entanto, a incorporação de muitas informações pode aumentar o espaço PCFG e a complexidade da memória e é desejável que um modelo baseado em PCFG seja o mais simples possível.

Cada string possível $x que$ uma gramática gera recebe um peso de probabilidade dado o modelo PCFG . Segue-se que a soma de todas as probabilidades para todas as produções gramaticais possíveis é . As pontuações para cada resíduo emparelhado e não emparelhado explicam a probabilidade de formações de estrutura secundária. As regras de produção também permitem comprimentos de loop de pontuação, bem como a ordem de empilhamento de pares de base, portanto, é possível explorar a gama de todas as gerações possíveis, incluindo estruturas subótimas da gramática e aceitar ou rejeitar estruturas com base nos limites de pontuação. ${\ displaystyle P (x | \ theta)}$ ${\ displaystyle \ theta}$ ${\ displaystyle \ sum _ {\ text {x}} P (x | \ theta) = 1}$

Implementações

Implementações de estrutura secundária de RNA com base em abordagens de PCFG podem ser utilizadas em:

Encontrar a estrutura de consenso ao otimizar as probabilidades da estrutura conjunta em relação ao MSA.
Modelagem de covariação de par de base para detecção de homologia em pesquisas de banco de dados.
dobragem e alinhamento simultâneos em pares.

Existem diferentes implementações dessas abordagens. Por exemplo, Pfold é usado na previsão de estrutura secundária de um grupo de sequências de RNA relacionadas, modelos de covariância são usados na busca de bases de dados para sequências homólogas e anotação e classificação de RNA, RNApromo, CMFinder e TEISER são usados para encontrar motivos estruturais estáveis em RNAs.

Considerações de design

O projeto do PCFG impacta a precisão da previsão da estrutura secundária. Qualquer modelo probabilístico de previsão de estrutura útil baseado em PCFG deve manter a simplicidade sem comprometer muito a precisão da previsão. Um modelo muito complexo de excelente desempenho em uma única sequência pode não escalar. Um modelo baseado em gramática deve ser capaz de:

Encontre o alinhamento ideal entre uma sequência e o PCFG.
Pontue a probabilidade das estruturas para a sequência e subsequências.
Parametrize o modelo treinando em sequências / estruturas.
Encontre a árvore de análise gramatical ideal (algoritmo CYK).
Verifique a gramática ambígua (algoritmo interno condicional).

O resultado de várias árvores de análise por gramática denota ambigüidade gramatical. Isso pode ser útil para revelar todas as estruturas de pares de bases possíveis para uma gramática. No entanto, uma estrutura ótima é aquela em que há uma e apenas uma correspondência entre a árvore de análise e a estrutura secundária.

Dois tipos de ambigüidades podem ser distinguidos. Analise a ambigüidade da árvore e a ambigüidade estrutural. A ambigüidade estrutural não afeta as abordagens termodinâmicas, pois a seleção da estrutura ideal é sempre com base nas pontuações de energia livre mais baixas. A ambigüidade da árvore de análise diz respeito à existência de várias árvores de análise por sequência. Essa ambigüidade pode revelar todas as estruturas de pares de base possíveis para a sequência, gerando todas as árvores de análise sintática possíveis e, em seguida, encontrando a ideal. No caso de ambigüidade estrutural, várias árvores de análise descrevem a mesma estrutura secundária. Isso obscurece a decisão do algoritmo CYK em encontrar uma estrutura ótima, pois a correspondência entre a árvore de análise e a estrutura não é única. A ambigüidade gramatical pode ser verificada pelo algoritmo condicional interno.

Construindo um modelo PCFG

Uma gramática livre de contexto probabilística consiste em variáveis terminais e não terminais. Cada característica a ser modelada possui uma regra de produção que é atribuída a uma probabilidade estimada a partir de um conjunto de treinamento de estruturas de RNA. As regras de produção são aplicadas recursivamente até que restem apenas resíduos terminais.

Um não terminal inicial produz loops. O resto da gramática prossegue com o parâmetro que decidir se um laço é um início de uma haste ou uma região em cadeia simples $s$ e parâmetro que produz bases emparelhadas. ${\ displaystyle \ mathbf {\ mathit {S}}}$ ${\ displaystyle \ mathbf {\ mathit {L}}}$ ${\ displaystyle \ mathbf {\ mathit {F}}}$

O formalismo deste PCFG simples se parece com:

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

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

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

A aplicação de PCFGs na previsão de estruturas é um processo de várias etapas. Além disso, o próprio PCFG pode ser incorporado em modelos probabilísticos que consideram a história evolutiva do RNA ou procuram sequências homólogas em bancos de dados. Em um contexto de história evolutiva, a inclusão de distribuições anteriores de estruturas de RNA de um alinhamento estrutural nas regras de produção do PCFG facilita uma boa precisão de predição.

Um resumo das etapas gerais para a utilização de PCFGs em vários cenários:

Gere regras de produção para as sequências.
Verifique a ambigüidade.
Gere recursivamente árvores de análise das estruturas possíveis usando a gramática.
Classifique e pontue as árvores de análise para a sequência mais plausível.

Algoritmos

Existem vários algoritmos que lidam com aspectos de modelos probabilísticos baseados em PCFG na predição de estrutura de RNA. Por exemplo, o algoritmo interno-externo e o algoritmo CYK. O algoritmo de dentro para fora é um algoritmo de pontuação de programação dinâmica recursiva que pode seguir paradigmas de maximização de expectativa . Ele calcula a probabilidade total de todas as derivações que são consistentes com uma determinada sequência, com base em algum PCFG. A parte interna pontua as subárvores de uma árvore de análise e, portanto, as probabilidades de subseqüências dadas um PCFG. A parte externa pontua a probabilidade da árvore de análise completa para uma sequência completa. CYK modifica a pontuação de dentro para fora. Observe que o termo 'algoritmo CYK' descreve a variante CYK do algoritmo interno que encontra uma árvore de análise ideal para uma sequência usando um PCFG. Ele estende o algoritmo CYK real usado em CFGs não probabilísticos.

O algoritmo interno calcula as probabilidades de toda uma subárvore de análise com raiz para a subsequência . O algoritmo externo calcula as probabilidades de uma árvore de análise completa para a sequência $x$ da raiz, excluindo o cálculo de . As variáveis $α$ e $β$ refinam a estimativa dos parâmetros de probabilidade de um PCFG. É possível reestimar o algoritmo PCFG encontrando o número esperado de vezes que um estado é usado em uma derivação por meio da soma de todos os produtos de $α$ e $β$ divididos pela probabilidade de uma sequência $x$ dado o modelo . Também é possível encontrar o número esperado de vezes que uma regra de produção é usada por uma maximização de expectativa que utiliza os valores de $α$ e $β$ . O algoritmo CYK calcula para encontrar a árvore de análise e os rendimentos mais prováveis . ${\ 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)}$

A complexidade de memória e tempo para algoritmos gerais de PCFG em previsões de estrutura de RNA são e, respectivamente. Restringir um PCFG pode alterar esse requisito, como é o caso dos métodos de pesquisa de banco de dados. ${\ displaystyle O (L ^ {2} M)}$ ${\ displaystyle O (L ^ {3} M ^ {3})}$

PCFG na pesquisa de homologia

Os modelos de covariância (CMs) são um tipo especial de PCFGs com aplicações em pesquisas de banco de dados para homólogos, anotação e classificação de RNA. Por meio de CMs, é possível construir perfis de RNA baseados em PCFG, onde RNAs relacionados podem ser representados por uma estrutura secundária de consenso. O pacote de análise de RNA Infernal usa esses perfis na inferência de alinhamentos de RNA. O banco de dados Rfam também usa CMs na classificação de RNAs em famílias com base em sua estrutura e informações de sequência.

Os CMs são projetados a partir de uma estrutura de RNA de consenso. Um CM permite indels de comprimento ilimitado no alinhamento. Os terminais constituem estados no CM e as probabilidades de transição entre os estados é 1 se nenhum indels for considerado. As gramáticas em um CM são as seguintes:

${\ displaystyle P \ to aWb}$: probabilidades de interações entre pares entre 16 pares possíveis
${\ displaystyle L \ to aW}$: probabilidades de gerar 4 bases únicas possíveis à esquerda
${\ displaystyle R \ to Wa}$: probabilidades de gerar 4 bases únicas possíveis à direita
${\ displaystyle B \ para SS}$: bifurcação com probabilidade de 1
${\ displaystyle S \ to W}$: comece com uma probabilidade de 1
${\ displaystyle E \ to \ epsilon}$: terminar com uma probabilidade de 1

O modelo tem 6 estados possíveis e cada gramática de estado inclui diferentes tipos de probabilidades de estrutura secundária dos não terminais. Os estados são conectados por transições. O ideal é que os estados de nó atuais se conectem a todos os estados de inserção e os estados de nós subsequentes se conectem a estados de não inserção. Para permitir a inserção de mais de uma base, os estados de inserção conectam-se a eles próprios.

Para pontuar um modelo CM, os algoritmos de dentro para fora são usados. Os CMs usam uma implementação ligeiramente diferente do CYK. As pontuações de emissão de log-odds para a árvore de análise ideal - - são calculadas a partir dos estados de emissão . Uma vez que essas pontuações são uma função do comprimento da sequência, uma medida mais discriminativa para recuperar uma pontuação ótima de probabilidade da árvore de análise - é alcançada limitando o comprimento máximo da sequência a ser alinhada e calculando as probabilidades logarítmicas em relação a um nulo. O tempo de cálculo desta etapa é linear ao tamanho do banco de dados e o algoritmo tem uma complexidade de memória de . ${\ 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})}$

Exemplo: Uso de informações evolutivas para orientar a previsão da estrutura

O algoritmo KH-99 de Knudsen e Hein estabelece a base da abordagem Pfold para prever a estrutura secundária do RNA. Nesta abordagem, a parametrização requer informações de histórico evolutivo derivadas de uma árvore de alinhamento, além de probabilidades de colunas e mutações. As probabilidades gramaticais são observadas a partir de um conjunto de dados de treinamento.

Estimar probabilidades de coluna para bases emparelhadas e não emparelhadas

Em um alinhamento estrutural, as probabilidades das colunas de bases desemparelhadas e das colunas de bases pareadas são independentes de outras colunas. Contando as bases em posições de base única e posições emparelhadas, obtém-se as frequências de bases em loops e hastes. Para o par de base $X$ e $Y,$ uma ocorrência de também é contada como uma ocorrência de . Pares de base idênticos, como são contados duas vezes. ${\ displaystyle XY}$ ${\ displaystyle YX}$ ${\ displaystyle XX}$

Calcular taxas de mutação para bases emparelhadas e não emparelhadas

Ao emparelhar as sequências de todas as maneiras possíveis, as taxas gerais de mutação são estimadas. A fim de recuperar mutações plausíveis, um limite de identidade de sequência deve ser usado para que a comparação seja entre sequências semelhantes. Esta abordagem usa um limite de identidade de 85% entre as sequências de emparelhamento. As primeiras diferenças de posições de base única - exceto para colunas com espaçamento - entre pares de sequências são contadas de modo que se a mesma posição em duas sequências tivesse bases $X, Y$ diferentes $,$ a contagem da diferença é incrementada para cada sequência.

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.

Para bases desemparelhadas, uma matriz de taxa de mutação 4 X 4 é usada que satisfaça que o fluxo de mutação de X para Y seja reversível:

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

Para pares de base, uma matriz de distribuição de taxa de 16 x 16 é gerada de forma semelhante. O PCFG é usado para prever a distribuição de probabilidade anterior da estrutura, enquanto as probabilidades posteriores são estimadas pelo algoritmo interno-externo e a estrutura mais provável é encontrada pelo algoritmo CYK.

Estimar probabilidades de alinhamento

Depois de calcular as probabilidades anteriores da coluna, a probabilidade de alinhamento é estimada somando todas as estruturas secundárias possíveis. Qualquer coluna $C$ em uma estrutura secundária para uma sequência $D$ do comprimento $L$ de tal modo que pode ser marcado com respeito à árvore alinhamento $T$ e o modelo mutacional $M$ . A distribuição prévia dada pelo PCFG é . A árvore filogenética, $T$ , pode ser calculada a partir do modelo por estimativa de máxima verossimilhança. Observe que as lacunas são tratadas como bases desconhecidas e a soma pode ser feita por meio de programação dinâmica . ${\ 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)}

Atribuir probabilidades de produção a cada regra da gramática

Cada estrutura na gramática é atribuída a probabilidades de produção concebidas a partir das estruturas do conjunto de dados de treinamento. Essas probabilidades anteriores dão peso à precisão das previsões. O número de vezes que cada regra é usada depende das observações do conjunto de dados de treinamento para aquele recurso gramatical específico. Essas probabilidades estão escritas entre parênteses no formalismo gramatical e cada regra terá um total de 100%. Por exemplo:

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

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

{\ displaystyle F \ to dFd (60,4 \%) | LS (39,6 \%)}

Preveja a probabilidade da estrutura

Dadas as frequências de alinhamento anteriores dos dados, a estrutura mais provável do conjunto previsto pela gramática pode então ser calculada maximizando por meio do algoritmo CYK. A estrutura com o maior número previsto de previsões corretas é relatada como a estrutura de consenso. ${\ displaystyle P (\ sigma | D, T, M)}$

{\ displaystyle \ sigma _ {MAP} = \ arg {\ underset {\ sigma} {\ max}} P (D | \ sigma, T ^ {M} L, M) P (\ sigma | M)}

Melhorias Pfold no algoritmo KH-99

As abordagens baseadas em PCFG devem ser escalonáveis e gerais o suficiente. O comprometimento da velocidade para a precisão deve ser o mínimo possível. Pfold aborda as limitações do algoritmo KH-99 no que diz respeito à escalabilidade, lacunas, velocidade e precisão.

Em Pfold, as lacunas são tratadas como desconhecidas. Nesse sentido, a probabilidade de uma coluna com lacuna é igual à de uma coluna sem lacuna.
Em Pfold, a árvore $T$ é calculada antes da previsão da estrutura por meio da junção de vizinhos e não por máxima verossimilhança por meio da gramática PCFG. Apenas os comprimentos dos ramos são ajustados para estimativas de máxima verossimilhança.
Uma suposição de Pfold é que todas as sequências têm a mesma estrutura. O limite de identidade de sequência e permitindo uma probabilidade de 1% de que qualquer nucleotídeo se torne outro limita a deterioração do desempenho devido a erros de alinhamento.

Análise de sequência de proteína

Enquanto os PCFGs provaram ser ferramentas poderosas para prever a estrutura secundária do RNA, o uso no campo da análise da sequência de proteínas foi limitado. Na verdade, o tamanho do alfabeto de aminoácidos e a variedade de interações vistas nas proteínas tornam a inferência gramatical muito mais desafiadora. Como consequência, a maioria das aplicações da teoria da linguagem formal para análise de proteínas tem se restringido principalmente à produção de gramáticas de baixo poder expressivo para modelar padrões funcionais simples baseados em interações locais. Como as estruturas de proteínas comumente exibem dependências de ordem superior, incluindo relações aninhadas e cruzadas, elas claramente excedem as capacidades de qualquer CFG. Ainda assim, o desenvolvimento de PCFGs permite expressar algumas dessas dependências e fornecer a capacidade de modelar uma gama mais ampla de padrões de proteínas.

Um dos principais obstáculos para inferir uma gramática de proteína é o tamanho do alfabeto que deveria codificar os 20 aminoácidos diferentes . Foi proposto abordar isso usando propriedades físico-químicas de aminoácidos para reduzir significativamente o número de combinações possíveis de símbolos do lado direito nas regras de produção: 3 níveis de uma propriedade quantitativa são utilizados em vez dos 20 tipos de aminoácidos , por exemplo, pequeno , volume de van der Waals médio ou grande . Com base em tal esquema, PCFGs foram produzidos para gerar descritores de local de ligação e de local de contato hélice-hélice. Uma característica significativa dessas gramáticas é que a análise de suas regras e árvores de análise pode fornecer informações biologicamente significativas.

Languages

In other projects