Shannon Entropy

9.1 Inleiding

Chomsky formaliseerde aanvankelijk contextvrije grammatica ’s (Cfg’ s) als een poging om talen te modelleren. Sindsdien zijn ze op grote schaal gebruikt in een verscheidenheid van computer science toepassingen. Cfg ‘ s hebben een recursieve aard en zijn samengesteld uit sets van regels die strings van alfabetten kunnen aandrijven, ook wel aangeduid als woorden. De verzameling woorden gegenereerd door een grammatica wordt aangeduid als de taal van die grammatica. Een grammatica wordt gezegd eenduidig te zijn als er een een-op-een overeenkomst tussen de woorden en hun beschrijvende afleidingen. Stochastische CFGs (SCFGs) wijzen waarschijnlijkheden toe aan elke regel, die op zijn beurt een waarschijnlijkheidswaarde aan elk woord toewijst door de waarschijnlijkheden van de regels te vermenigvuldigen die worden gebruikt om dat woord af te leiden . Grenander, Kuich, Hutchins, Soule en anderen hebben belangrijke eigenschappen van cfg ’s en Scfg’ s onderzocht, zoals convergentie van de gemiddelde lengte van afleidingen, capaciteit, of de Shannon ‘ s entropie (Shannon entropie) zoals gedefinieerd in , met behulp van technieken voor het genereren van functies. Het secundaire structuurschema van RNA heeft ook een contextvrije aard, waardoor het door dergelijke grammatica kan worden beschreven. De secundaire structuur van RNA werd eerst formeel beschreven door Smith en Waterman . Combinatorische kenmerken van RNA secundaire structuren werden vervolgens onderzocht door Stein en Waterman en vervolgens bestudeerd door Viennot en Vauchaussade de Chaumont, Hofacker et al. , Nebel, Liao en Wang, Doslic et al. en anderen die genererende functies en waarschijnlijkheidsgenererende functies gebruiken.

Scfg ‘ s hebben een grote impact gehad op de secundaire structuurstudies van RNA . De secundaire structuurmodellering van RNA helpt ons voorspellingen over de structuur van RNA en zijn latere biologische functie te maken, aangezien de functies van vele RNAs zoals diverse klassen van Nonproteïne-codeert RNAs (ncRNA) met hun structuren verwant zijn. Typisch, RNA secundaire structuur voorspelling wordt gedaan door het minimaliseren van de vouwenergie van de sequentie onder een thermodynamisch gebaseerd vouwmodel zoals het Boltzmann ensemble . SCFGs, anderzijds, zijn covariantiemodellen die RNA het vouwen met meer flexibiliteit kunnen imiteren. In het geval van een scfg-gebaseerd vouwmodel, worden waarschijnlijkheidswaarden toegewezen aan alle mogelijke vouwscenario ‘ s van een RNA-sequentie. Vervolgens wordt de structuur met maximale waarschijnlijkheid (ML) waarde voorspeld als de secundaire structuur van de RNA-sequentie. ML voorspelling van SCFG – gebaseerde modellen kan worden gedaan door de Cocke-Younger-Kasami (CYK) algoritme. Net als bij energieminimalisatie wordt het CYK-algoritme geïmplementeerd door middel van dynamisch programmeren. Het doel van modelontwerp is om ml schattingen te verkrijgen die zo gelijkaardig aan de bekende secundaire structuren van RNA mogelijk zijn, waardoor toewijzing van waarschijnlijkheden aan regels een kritische en uitdagende taak wordt. Rivas biedt een dieper inzicht in verschillende aspecten van RNA secundaire structuurmodellering.

Current expectation maximization (EM) model trainingsbenaderingen bestaan over het algemeen uit de volgende twee stappen: ten eerste wordt het CYK-algoritme gebruikt voor structuurvoorspelling van elke RNA-sequentie van de trainingsset (maximalisatiestap). Ten tweede, de regel waarschijnlijkheden van het SCFG worden opnieuw geschat op basis van de tellingen of frequenties van hun voorvallen in de voorspellingen (schattingsstap). Deze schattingen kunnen worden berekend aan de hand van de eerdere Laplace-benadering die is uitgelegd in Durbin et al. of gebruik maken van vergelijkbare frequentiegebaseerde benaderingen. De iteratieve EM procedure kan doorgaan totdat de resulterende regel waarschijnlijkheden de gewenste nauwkeurigheid opleveren. Modeltrainingstechnieken kunnen variëren, hetzij in de definitie van het ML-criterium (joint vs .conditional) of in de regel-kansschatting technieken. Een SCFG-gebaseerd RNA vouwmodel kan bestaan uit een lichtgewicht SCFG met slechts een paar grammatica regels of het kan een zwaargewicht grammatica die bestaat uit vele regels zoals super-grammars beschreven in Rivas et al. .

in dit werk wordt de Shannon entropie van de SCFG, hier aangeduid als grammatica ruimte (GS) entropie, analytisch berekend en geà ntroduceerd als een kritische grammatica functie in RNA secundaire structuur modellering. Gepresenteerde formuleringen zijn consistent met de algemene vorm van grammatica entropie bekend als de afgeleide entropie, en kan worden gevonden in Grenander en Soule . In Sectie 9.2, een formulering wordt gepresenteerd voor het berekenen van de Shannon entropie van de oneindig grote probabilistische ruimte van structureel eenduidige RNA-modellering grammars1 die consistent is met de derivationele entropie formuleringen gepresenteerd in Grenander . De GS-entropiewaarden van verschillende gevestigde RNA-vouwmodellen worden vervolgens berekend onder verschillende parameterverzamelingen in Paragraaf 9.3. In Paragraaf 9.4, wordt een criterium voor scfg-gebaseerde secundaire structuurmodel opleiding van RNA voorgesteld gebaseerd op de GS entropie. Punt 9.5 tot slot bevat een discussie en conclusies.