Shannon Entropy

9.1 Innledning

Chomsky opprinnelig formalisert kontekstfrie grammatikker (CFGs) som et forsøk på å modellere språk. Siden da har de blitt brukt bredt i en rekke datavitenskapsprogrammer. CFGs har en rekursiv natur og består av sett med regler som kan drive strenger av alfabeter, også referert til som ord. Settet av ord generert av en grammatikk er referert til som språket i den grammatikken. En grammatikk sies å være entydig hvis det er en en-til-en korrespondanse mellom ordene og deres beskrivende avledninger. Stokastiske CFGs (SCFGs) tildeler sannsynligheter til hver regel, som igjen tildeler en sannsynlighetsverdi til hvert ord ved å multiplisere sannsynlighetene for reglene som brukes til å utlede det ordet . Grenander, Kuich, Hutchins, Soule og andre har undersøkt viktige egenskaper Ved CFGs og SCFGs, slik som konvergens av gjennomsnittlig lengde av avledninger, kapasitet, Eller Shannon entropi (Shannon entropi) som definert i , ved hjelp av generering-funksjoner teknikker. Den sekundære strukturen skjematisk AV RNA har også en kontekstfri natur, slik at den kan beskrives av slike grammatikker. Rna sekundær struktur ble først formelt beskrevet Av Smith Og Waterman . Kombinatoriske trekk ved rna sekundære strukturer ble deretter utforsket Av Stein Og Waterman og deretter studert Av Viennot Og Vauchaussade De Chaumont, Hofacker et al. , Nebel, Liao Og Wang, Doslic et al. og andre bruker genererende funksjoner og sannsynlighetsgenererende funksjoner.

SCFGs har hatt stor innvirkning på rna sekundære strukturstudier . Rna sekundær strukturmodellering hjelper oss med å gjøre spådommer om RNA-strukturen og dens etterfølgende biologiske funksjon, da funksjonene til mange Rna-Er som ulike klasser av ikke-protein-kodende rna (ncRNA) er relatert til deres strukturer. Typisk er rna sekundær struktur prediksjon gjort ved minimering av folde energi av sekvensen under en termodynamisk-basert foldemodell Som Boltzmann ensemble . SCFGs, derimot, er kovariansmodeller som kan etterligne RNA-folding med mer fleksibilitet. I TILFELLE AV EN SCFG-basert foldemodell tilordnes sannsynlighetsverdier til alle mulige foldingsscenarier av EN RNA-sekvens. Da er strukturen som har maksimal sannsynlighet (ML) verdi spådd som den sekundære strukturen TIL RNA-sekvensen. ML prediksjon AV SCFG-baserte modeller kan gjøres Av Cocke-Younger-Kasami (CYK) algoritme. I likhet med energiminimering implementeres CYK-algoritmen gjennom dynamisk programmering. Målet med modelldesign er Å oppnå ML-estimeringer som er så lik de kjente rna-sekundære strukturer som mulig, og dermed gjøre tildeling av sannsynligheter til regler en kritisk og utfordrende oppgave. Rivas gir en mer grundig innsikt i ulike aspekter AV rna sekundær struktur modellering.Nåværende forventning maksimering (EM) modell trening tilnærminger vanligvis består av følgende to trinn: FØRST, CYK algoritmen brukes for struktur prediksjon av HVER RNA sekvens av treningssettet (maksimering trinn). For det andre blir regelens sannsynligheter for SCFG reestimert basert på tellingene eller frekvensene av deres forekomster i prognosene (estimeringstrinnet). Disse estimatene kan beregnes enten ved Hjelp Av Laplace tidligere tilnærming forklart I Durbin et al. eller distribuere lignende frekvensbaserte tilnærminger. Den iterative EM-prosedyren kan fortsette til de resulterende regel sannsynlighetene gir ønsket nøyaktighet. Modelltreningsteknikker kan variere, enten i definisjonen AV ML-kriteriet (felles vs betinget) eller i regel-sannsynlighets estimeringsteknikker . EN SCFG-basert rna-foldemodell kan enten bestå av en lett SCFG med bare noen få grammatikkregler, eller det kan være en tungvekt grammatikk som består av mange regler som super-grammatikker beskrevet i Rivas et al. .I dette arbeidet er Shannon-entropien TIL SCFG, betegnet her som grammatikkrom (GS) entropi, analytisk beregnet og introdusert som en kritisk grammatikkfunksjon i rna sekundær strukturmodellering. Presentert formuleringer er i samsvar med den generelle formen for grammatikkentropi kjent som derivativ entropi, og kan finnes I Grenander og Soule . I Avsnitt 9.2, en formulering er presentert for beregning Av Shannon entropi av uendelig store probabilistiske plass strukturelt entydige RNA-modellering grammatikker1 som er i samsvar med derivative entropi formuleringer presentert I Grenander . Gs-entropiverdiene for flere veletablerte rna-foldemodeller beregnes deretter under forskjellige parametersett i Seksjon 9.3. I Avsnitt 9.4 foreslås et kriterium for scfg-basert rna sekundær strukturmodell trening basert PÅ GS entropi. Punkt 9.5 består av drøftelser og konklusjoner.