Shannon entropi

9.1 introduktion

Chomsky formaliserade ursprungligen kontextfria grammatik (cfg) som ett försök att modellera språk. Sedan dess har de använts i stor utsträckning i en mängd olika datavetenskapliga applikationer. Cfg: er har en rekursiv karaktär och består av uppsättningar regler som kan driva strängar av alfabet, även kallade ord. Den uppsättning ord som genereras av en grammatik kallas språket i den grammatiken. En grammatik sägs vara entydig om det finns en en-till-en-korrespondens mellan orden och deras beskrivande härledningar. Stokastiska CFGs (SCFGs) tilldelar sannolikheter till varje regel, som i sin tur tilldelar ett sannolikhetsvärde till varje ord genom att multiplicera sannolikheten för de regler som används för att härleda det ordet . Grenander, Kuich, Hutchins, Soule och andra har undersökt viktiga egenskaper hos cfg och Scfg, såsom konvergens av genomsnittlig längd av derivat, kapacitet eller Shannons entropi (Shannon entropi) enligt definitionen i, med hjälp av genereringsfunktioner tekniker. RNA: s sekundära strukturschema har också en kontextfri natur, så att den kan beskrivas av sådana grammatik. RNA sekundär struktur beskrevs först formellt av Smith och Waterman . Kombinatoriska egenskaper hos RNA sekundära strukturer undersöktes sedan av Stein och Waterman och studerades därefter av Viennot och Vauchaussade de Chaumont , Hofacker et al. , Nebel , Liao och Wang, Doslic et al. och andra som använder genererande funktioner och sannolikhetsgenererande funktioner.

SCFGs har haft stor inverkan på RNA-sekundära strukturstudier . RNA sekundär strukturmodellering hjälper oss att göra förutsägelser om RNA-strukturen och dess efterföljande biologiska funktion, eftersom funktionerna hos många rna såsom olika klasser av icke-proteinkodande rna (ncRNA) är relaterade till deras strukturer. Vanligtvis görs förutsägelse av RNA-sekundär struktur genom minimering av sekvensens vikningsenergi under en termodynamisk baserad vikningsmodell såsom Boltzmann-ensemblet . Scfg, å andra sidan, är kovariansmodeller som kan imitera RNA-vikning med mer flexibilitet. I fallet med en SCFG-baserad vikningsmodell tilldelas sannolikhetsvärden till alla möjliga vikningsscenarier av en RNA-sekvens. Därefter förutses strukturen med maximal sannolikhet (ML) värde som den sekundära strukturen för RNA-sekvensen. ML-förutsägelse av SCFG-baserade modeller kan göras med Cocke-Younger-Kasami (cykel) – algoritmen. I likhet med energiminimering implementeras cykel-algoritmen genom dynamisk programmering. Målet med modelldesign är att få ML-uppskattningar som liknar de kända RNA-sekundära strukturerna som möjligt, vilket gör tilldelning av sannolikheter till regler till en kritisk och utmanande uppgift. Rivas erbjuder en mer djupgående inblick i olika aspekter av RNA-sekundär strukturmodellering.

nuvarande förväntningsmaximering (EM) modellutbildningsmetoder består i allmänhet av följande två steg: för det första används cykel-algoritmen för strukturförutsägelse av varje RNA-sekvens i träningsuppsättningen (maximeringssteg). För det andra beräknas scfg: s regelsannolikheter baserat på räkningarna eller frekvenserna för deras händelser i förutsägelserna (uppskattningssteget). Dessa uppskattningar kan beräknas antingen med hjälp av Laplace tidigare tillvägagångssätt förklaras i Durbin et al. eller använda liknande frekvensbaserade metoder. Den iterativa em-proceduren kan fortsätta tills de resulterande regelsannolikheterna ger önskad noggrannhet. Modellutbildningstekniker kan variera, antingen i definitionen av ML-kriteriet (gemensamt vs. villkorat) eller i regel-sannolikhetsbedömningstekniker . En SCFG-baserad RNA-vikningsmodell kan antingen bestå av en lätt SCFG med bara några grammatikregler eller det kan vara en tungviktig grammatik som består av många regler som supergrammer som beskrivs i Rivas et al. .

i detta arbete, Shannon entropi av SCFG, betecknas här som grammatik utrymme (GS) entropi, beräknas analytiskt och introduceras som en kritisk grammatik funktion i RNA sekundär struktur modellering. Presenterade formuleringar överensstämmer med den allmänna formen av grammatik entropi känd som derivational entropi, och finns i Grenander och Soule . I Avsnitt 9.2 Presenteras en formulering för beräkning av Shannon-entropin av det oändligt stora probabilistiska utrymmet för strukturellt entydiga RNA-modellerande grammatiker1 som överensstämmer med de derivativa entropiformuleringarna som presenteras i Grenander . GS-entropivärdena för flera väletablerade RNA-vikningsmodeller beräknas sedan under olika parameteruppsättningar i avsnitt 9.3. I avsnitt 9.4 föreslås ett kriterium för SCFG-baserad RNA-sekundär strukturmodellutbildning baserat på GS-entropin. Slutligen består avsnitt 9.5 av diskussioner och slutsatser.