Shannon Entropy

9.1 introduktion

Chomsky formaliserede oprindeligt kontekstfrie grammatikker (cfg ‘ er) som et forsøg på at modellere sprog. Siden da er de blevet brugt bredt i en række computervidenskabelige applikationer. Cfg ‘ er har en rekursiv karakter og er sammensat af sæt regler, der kan drive strenge af alfabeter, også kaldet ord. Det sæt ord, der genereres af en grammatik, kaldes sproget i denne grammatik. En grammatik siges at være entydig, hvis der er en en-til-en korrespondance mellem ordene og deres beskrivende afledninger. Stokastiske cfg ‘er (Scfg’ er) tildeler sandsynligheder til hver regel, som igen tildeler en sandsynlighedsværdi til hvert ord ved at multiplicere sandsynlighederne for de regler, der bruges til at udlede dette ord . Grenander, Kuich , Hutchins, Soule og andre har undersøgt vigtige egenskaber ved cfg ‘er og Scfg’ er, såsom konvergens af gennemsnitlig længde af afledninger, kapacitet eller Shannons entropi (Shannon entropi) som defineret i ved hjælp af genereringsfunktionsteknikker. Den sekundære struktur skematisk af RNA har også en kontekstfri natur, der gør det muligt at beskrive det ved sådanne grammatikker. RNA sekundær struktur blev først formelt beskrevet af Smith og Vandmand . Kombinatoriske træk ved RNA sekundære strukturer blev derefter undersøgt af Stein og Vandmand og derefter undersøgt af Viennot og Vauchaussade de Chaumont , Hofacker et al. , Nebel, Liao, Doslic et al. og andre ved hjælp af genererende funktioner og sandsynlighedsgenererende funktioner.

Scfg ‘ er har haft stor indflydelse på RNA sekundære strukturstudier . RNA-sekundær strukturmodellering hjælper os med at forudsige RNA-strukturen og dens efterfølgende biologiske funktion, da funktionerne i mange RNA ‘er såsom forskellige klasser af ikke-proteinkodende RNA’ er (ncRNA) er relateret til deres strukturer. Typisk er RNA sekundær struktur forudsigelse udført ved minimering af foldningsenergien i sekvensen under en termodynamisk-baseret foldemodel som f .eks. Scfg ‘ er er derimod kovariansmodeller, der kan efterligne RNA-foldning med mere fleksibilitet. I tilfælde af en SCFG-baseret foldemodel tildeles sandsynlighedsværdier til alle mulige foldningsscenarier for en RNA-sekvens. Derefter forudsiges strukturen med maksimal sandsynlighed (ML) værdi som den sekundære struktur af RNA-sekvensen. ML forudsigelse af SCFG-baserede modeller kan udføres af Cocke-Younger-Kasami (CYK) algoritmen. I lighed med energiminimering implementeres CYK-algoritmen gennem dynamisk programmering. Målet med modeldesign er at opnå ML-estimater, der ligner de kendte RNA-sekundære strukturer som muligt, hvilket gør tildeling af sandsynligheder til regler til en kritisk og udfordrende opgave. Rivas tilbyder en mere dybdegående indsigt i forskellige aspekter af RNA sekundær struktur modellering.

nuværende forventningsmaksimering (EM) model træningsmetoder består generelt af følgende to trin: for det første bruges CYK-algoritmen til strukturforudsigelse af hver RNA-sekvens i træningssættet (maksimeringstrin). For det andet estimeres regelsandsynlighederne for SCFG på baggrund af tællingerne eller frekvenserne af deres forekomster i forudsigelserne (estimeringstrin). Disse estimater kan beregnes enten ved hjælp af Laplace forudgående tilgang forklaret i Durbin et al. eller implementering af lignende frekvensbaserede tilgange. Den iterative EM-procedure kan fortsætte, indtil de resulterende regelsandsynligheder giver den ønskede nøjagtighed. Modeluddannelsesteknikker kan variere i enten definitionen af ML-kriteriet (fælles vs. betinget) eller i regel-sandsynlighedsestimeringsteknikker . En SCFG-baseret RNA-foldemodel kan enten bestå af en let scfg med kun få grammatikregler, eller det kan være en tungvægtsgrammatik bestående af mange regler såsom supergrammater beskrevet i Rivas et al. .

i dette arbejde Shannon entropi af SCFG, betegnet her som grammatikrum (GS) entropi, beregnes analytisk og introduceres som en kritisk grammatikfunktion i RNA sekundær struktur modellering. Præsenterede formuleringer er i overensstemmelse med den generelle form for grammatikker entropi kendt som derivational entropi, og kan findes i Grenander og Soule . I Afsnit 9.2 præsenteres en formulering til beregning af Shannon-entropien i det uendeligt store probabilistiske rum af strukturelt entydige RNA-modelleringsgrammatikker1, der er i overensstemmelse med de afledte entropiformuleringer præsenteret i Grenander . GS-entropi-værdierne for flere veletablerede RNA-foldemodeller beregnes derefter under forskellige parametersæt i afsnit 9.3. I afsnit 9.4 foreslås et kriterium for SCFG-baseret RNA-sekundær strukturmodeltræning baseret på GS entropi. Endelig indeholder afsnit 9.5 diskussion og konklusioner.