Shannon entrópia

9.1 Bevezetés

Chomsky kezdetben formalizálta a kontextusmentes nyelvtanokat (cfg-k) a nyelvek modellezésére tett kísérletként. Azóta széles körben használják őket a különféle számítástechnikai alkalmazásokban. A cfg-k rekurzív jellegűek, és olyan szabálykészletekből állnak, amelyek ábécé karakterláncokat vezethetnek, más néven szavakat. A nyelvtan által generált szavak halmazát az adott nyelvtan nyelvének nevezik. A nyelvtan akkor egyértelmű, ha a szavak és azok leíró származékai között egy-egy összefüggés van. Sztochasztikus cfg-k (SCFGs) valószínűségeket rendelnek minden szabályhoz, ami viszont valószínűségi értéket rendel minden szóhoz az adott szó levezetéséhez használt szabályok valószínűségének szorzásával . Grenander, Kuich , Hutchins, Soule és mások a cfg-k és Scfg-k fontos tulajdonságait vizsgálták, mint például a származékok átlagos hosszának konvergenciája, kapacitás , vagy a Shannon entrópiája (Shannon entrópia) a generáló függvények technikáinak alkalmazásával. Az RNS másodlagos szerkezeti vázlata szintén kontextusmentes jellegű, lehetővé téve az ilyen nyelvtanok leírását. Az RNS másodlagos szerkezetét először Smith és Waterman írta le hivatalosan . Az RNS másodlagos struktúráinak kombinatorikus jellemzőit ezután Stein és Waterman vizsgálta, majd Viennot és Vauchaussade de Chaumont , Hofacker et al. , Nebel, Liao és Wang, Doslic et al. és mások generáló függvényeket és valószínűséggeneráló függvényeket használnak.

az Scfg-k nagy hatással voltak az RNS másodlagos szerkezeti vizsgálataira . Az RNS szekunder struktúrájának modellezése segít előrejelzéseket készíteni az RNS szerkezetéről és annak későbbi biológiai funkciójáról, mivel számos RNS funkciója, például a nonprotein-kódoló RNS-ek (ncrns) különböző osztályai kapcsolódnak szerkezetükhöz. Jellemzően az RNS másodlagos szerkezetének előrejelzését úgy végezzük, hogy minimalizáljuk a szekvencia hajtogatási energiáját egy termodinamikai alapú hajtogatási modell, például a Boltzmann együttes alatt . Az scfg-k viszont kovariancia modellek, amelyek nagyobb rugalmassággal utánozhatják az RNS hajtogatását. SCFG-alapú hajtogatási modell esetén valószínűségi értékeket rendelnek az RNS-szekvencia összes lehetséges hajtogatási forgatókönyvéhez. Ezután a maximális valószínűségű (ML) értékű szerkezetet az RNS-szekvencia másodlagos szerkezeteként jósoljuk meg. Az SCFG-alapú modellek ML-előrejelzése a Cocke-Younger-Kasami (CYK) algoritmus. Az energia minimalizálásához hasonlóan a CYK algoritmust dinamikus programozással valósítják meg. A Modelltervezés célja, hogy az ismert RNS másodlagos struktúrákhoz a lehető leginkább hasonló ML becsléseket kapjunk, így a valószínűségek hozzárendelése a szabályokhoz kritikus és kihívást jelentő feladat. A Rivas mélyebb betekintést nyújt az RNS szekunder szerkezet modellezésének különböző aspektusaiba.

Az aktuális elvárás maximalizálási (EM) modell képzési megközelítései általában a következő két lépésből állnak: először a CYK algoritmust használják a képzési készlet minden RNS-szekvenciájának szerkezeti előrejelzésére (maximalizálási lépés). Másodszor, az SCFG szabály valószínűségeit újraértékeljük az előrejelzésekben előforduló események száma vagy gyakorisága alapján (becslési lépés). Ezeket a becsléseket a Laplace előzetes megközelítésével lehet kiszámítani, amelyet Durbin et al. vagy hasonló frekvenciaalapú megközelítések alkalmazása. Az iteratív EM eljárás addig folytatódhat, amíg a kapott szabály valószínűségek meg nem adják a kívánt pontosságot. A modellképzési technikák változhatnak, akár az ML kritérium meghatározásában (közös vs .feltételes), akár szabály-valószínűség becslési technikákban. Az SCFG-alapú RNS hajtogatási modell vagy egy könnyű SCFG-ből állhat, csak néhány nyelvtani szabállyal, vagy nehézsúlyú nyelvtan lehet, amely sok szabályból áll, például a Rivas et al. .

ebben a munkában az SCFG Shannon-entrópiáját, amelyet itt grammatikai tér (GS) entrópiának nevezünk, analitikusan kiszámítjuk és kritikus nyelvtani jellemzőként vezetjük be az RNS szekunder szerkezet modellezésében. A bemutatott készítmények összhangban vannak a nyelvtanok entrópiájának általános formájával, amelyet derivációs entrópiának neveznek, és megtalálhatók Grenanderben és Soule-ban . A 9. Szakaszban.2, egy formulát mutatunk be a strukturálisan egyértelmű RNS-modellező nyelvtanok végtelenül nagy valószínűségi terének Shannon-entrópiájának kiszámítására1, amely összhangban van a Grenanderben bemutatott levezetési entrópia készítményekkel . Ezután több jól bevált RNS hajtogatási modell GS-entrópiaértékeit a 9.3. szakaszban különböző paraméterkészletek alapján számítjuk ki. A 9.4. szakaszban az SCFG-alapú RNS szekunder struktúramodell-képzés kritériumát javasoljuk a GS entrópia alapján. Végül a 9.5. szakasz vitákból és következtetésekből áll.