Shannon Entropy

9.1 Introduzione

Chomsky inizialmente formalizzato grammatiche context-free (CFG) come un tentativo di modellare i linguaggi. Da allora, sono stati utilizzati ampiamente in una varietà di applicazioni informatiche. I CFG hanno una natura ricorsiva e sono composti da insiemi di regole che possono guidare stringhe di alfabeti, chiamate anche parole. L’insieme di parole generate da una grammatica è indicato come la lingua di quella grammatica. Si dice che una grammatica non sia ambigua se esiste una corrispondenza uno-a-uno tra le parole e le loro derivazioni descrittive. I CFG stocastici (SCFGS) assegnano probabilità a ciascuna regola, che a sua volta assegna un valore di probabilità a ciascuna parola moltiplicando le probabilità delle regole utilizzate per derivare quella parola . Grenander, Kuich, Hutchins, Soule e altri hanno studiato importanti proprietà di CFGS e SCFGs, come la convergenza della lunghezza media delle derivazioni , la capacità o l’entropia di Shannon (entropia di Shannon) come definita in, usando tecniche di funzioni generatrici. Lo schema della struttura secondaria dell’RNA ha anche una natura libera dal contesto, permettendogli di essere descritto da tali grammatiche. La struttura secondaria dell’RNA è stata descritta formalmente da Smith e Waterman . Le caratteristiche combinatorie delle strutture secondarie dell’RNA sono state poi esplorate da Stein e Waterman e successivamente studiate da Viennot e Vauchaussade de Chaumont, Hofacker et al. , Nebel, Liao e Wang, Doslic et al. e altri che usano funzioni generatrici e funzioni generatrici di probabilità.

Gli SCFG hanno avuto un grande impatto sugli studi sulla struttura secondaria dell’RNA . La modellazione della struttura secondaria dell’RNA ci aiuta a fare previsioni sulla struttura dell’RNA e sulla sua successiva funzione biologica, poiché le funzioni di molti RNA come varie classi di RNA non codificanti (ncRNA) sono correlate alle loro strutture. In genere, la previsione della struttura secondaria dell’RNA viene effettuata riducendo al minimo l’energia di piegatura della sequenza sotto un modello di piegatura basato sulla termodinamica come l’insieme di Boltzmann . Gli SCFG, d’altra parte, sono modelli di covarianza che possono imitare la piegatura dell’RNA con maggiore flessibilità. Nel caso di un modello di piegatura basato su SCFG, i valori di probabilità sono assegnati a tutti i possibili scenari di piegatura di una sequenza di RNA. Quindi, la struttura con valore di massima verosimiglianza (ML) è prevista come struttura secondaria della sequenza di RNA. La previsione ML dei modelli basati su SCFG può essere eseguita dall’algoritmo Cocke-Younger-Kasami (CYK). Simile alla minimizzazione dell’energia, l’algoritmo CYK è implementato attraverso la programmazione dinamica. L’obiettivo della progettazione del modello è ottenere stime ML che siano il più simili possibile alle strutture secondarie di RNA conosciute, rendendo così l’assegnazione delle probabilità alle regole un compito critico e impegnativo. Rivas offre una visione più approfondita di vari aspetti della modellazione della struttura secondaria dell’RNA.

Gli approcci di training del modello EM (Current Expectation maximization) consistono generalmente nei seguenti due passaggi: In primo luogo, l’algoritmo CYK viene utilizzato per la previsione della struttura di ogni sequenza di RNA del set di allenamento (fase di massimizzazione). In secondo luogo, le probabilità di regola dell’SCFG vengono rivalutate in base ai conteggi o alle frequenze delle loro occorrenze nelle previsioni (fase di stima). Queste stime possono essere calcolate utilizzando l’approccio precedente di Laplace spiegato in Durbin et al. o la distribuzione di approcci simili basati sulla frequenza. La procedura EM iterativa può continuare fino a quando le probabilità di regola risultanti producono la precisione desiderata. Le tecniche di addestramento del modello possono variare, sia nella definizione del criterio ML (joint vs. conditional) o nelle tecniche di stima della probabilità di regola . Un modello di piegatura a RNA basato su SCFG può essere costituito da un SCFG leggero con solo poche regole grammaticali o può essere una grammatica pesante composta da molte regole come le super-grammatiche descritte in Rivas et al. .

In questo lavoro, l’entropia di Shannon dell’SCFG, indicata qui come entropia dello spazio grammaticale (GS), viene calcolata analiticamente e introdotta come caratteristica grammaticale critica nella modellazione della struttura secondaria dell’RNA. Le formulazioni presentate sono coerenti con la forma generale di entropia delle grammatiche nota come entropia derivazionale e possono essere trovate in Grenander e Soule . Nella sezione 9.2, viene presentata una formulazione per il calcolo dell’entropia di Shannon dello spazio probabilistico infinitamente grande di grammatiche strutturalmente non ambigue di modellazione1 che è coerente con le formulazioni di entropia derivazionale presentate in Grenander . I valori di entropia GS di diversi modelli consolidati di RNA folding vengono quindi calcolati in diversi set di parametri nella Sezione 9.3. Nella Sezione 9.4, viene proposto un criterio per l’addestramento del modello di struttura secondaria dell’RNA basato su SCFG basato sull’entropia GS. Infine, la sezione 9.5 è composta da discussioni e conclusioni.