Shannon Entropy

9.1 Úvod

Chomsky původně formalizoval bezkontextové gramatiky (CFGs) jako pokus modelovat jazyky. Od té doby se široce používají v různých aplikacích informatiky. Cfg mají rekurzivní povahu a jsou složeny ze sad pravidel, které mohou řídit řetězce abeced, označované také jako slova. Množina slov generovaných gramatikou se označuje jako jazyk této gramatiky. Gramatika je považována za jednoznačnou, pokud existuje vzájemná korespondence mezi slovy a jejich popisnými derivacemi. Stochastické CFGs (SCFGs) přiřadí pravděpodobnosti každému pravidlu, které zase přiřadí hodnotu pravděpodobnosti každému slovu vynásobením pravděpodobností pravidel použitých k odvození tohoto slova . Grenander , Kuich , Hutchins , Soulová a jiní mají zkoumány důležité vlastnosti CFGs a SCFGs, jako je konvergence průměrná délka derivace, kapacity, nebo shannonovy entropie (Shannon entropie), jak je definováno v , použití generujících funkcí techniky. Sekundární strukturní schéma RNA má také bezkontextovou povahu, což umožňuje, aby byla popsána takovými gramatikami. Sekundární struktura RNA byla poprvé formálně popsána Smithem a Watermanem . Kombinatorické rysy sekundárních struktur RNA pak zkoumali Stein a Waterman a následně studovali Viennot a Vauchaussade de Chaumont, Hofacker et al. , Nebel, Liao a Wang, Doslic et al. a další pomocí generujících funkcí a funkcí generujících pravděpodobnost.

Scfg měly velký vliv na studie sekundární struktury RNA . RNA sekundární struktury modelování nám pomáhá, aby předpovědi o RNA struktura a její následné biologické funkce, jako funkce mnoha RNAs jako jsou různé třídy neproteinové-coding Rna (ncRNA) jsou spojené s jejich konstrukcí. Predikce sekundární struktury RNA se obvykle provádí minimalizací skládací energie sekvence pod termodynamickým skládacím modelem, jako je Boltzmannův soubor . Scfg jsou naproti tomu kovarianční modely, které mohou napodobovat skládání RNA s větší flexibilitou. V případě skládacího modelu založeného na SCFG jsou hodnoty pravděpodobnosti přiřazeny všem možným scénářům skládání sekvence RNA. Potom se jako sekundární struktura sekvence RNA předpovídá struktura s hodnotou maximální pravděpodobnosti (ML). ML predikce modelů založených na SCFG může být provedena algoritmem Cocke-Younger-Kasami (CYK). Podobně jako minimalizace energie je algoritmus CYK implementován pomocí dynamického programování. Cílem návrhu modelu je získat odhady ML, které jsou co nejvíce podobné známým sekundárním strukturám RNA, čímž se přiřazení pravděpodobností pravidlům stává kritickým a náročným úkolem. Rivas nabízí hlubší vhled do různých aspektů modelování sekundární struktury RNA.

současné tréninkové přístupy k maximalizaci očekávání (EM) se obecně skládají z následujících dvou kroků: nejprve se algoritmus CYK používá pro predikci struktury každé RNA sekvence tréninkové sady(krok maximalizace). Za druhé, pravděpodobnosti pravidel SCFG jsou přeceňovány na základě počtů nebo frekvencí jejich výskytu v předpovědích (krok odhadu). Tyto odhady lze vypočítat buď pomocí Laplaceova předchozího přístupu vysvětleného v Durbin et al. nebo nasazení podobných přístupů založených na frekvenci. Iterativní postup EM může pokračovat, dokud výsledné pravděpodobnosti pravidel nepřinesou požadovanou přesnost. Techniky modelového výcviku se mohou lišit buď v definici kritéria ML (společné vs. podmíněné), nebo v technikách odhadu pravděpodobnosti pravidla . Skládací model RNA založený na SCFG může sestávat buď z lehkého SCFG s pouze několika gramatickými pravidly, nebo to může být těžká gramatika skládající se z mnoha pravidel, jako jsou super-gramatiky popsané v Rivas et al. .

V této práci, Shannon entropie SCFG, zde označený jako gramatika prostor (GS) entropie, je analyticky vypočítána a představen jako kritické gramatické funkce v RNA sekundární struktury modelování. Předložené formulace jsou v souladu s obecné formě gramatiky entropie známý jako derivační entropie, a lze je nalézt v Grenander a Soule . V Oddíle 9.2, formulace je uvedena pro výpočet Shannon entropie nekonečně velké pravděpodobnostní prostor strukturálně jednoznačné RNA-modelování grammars1, který je v souladu s derivační entropie formulace prezentovány v Grenander . Hodnoty entropie GS u několika dobře zavedených modelů skládání RNA se pak vypočítají pod různými sadami parametrů v oddíle 9.3. V oddíle 9.4 je navrženo kritérium pro trénink modelu sekundární struktury RNA na bázi SCFG na základě entropie GS. Konečně Oddíl 9.5 se skládá z diskuse a závěrů.