Shannon Entropy

9.1 Introduction

Chomsky alun perin virallisti kontekstivapaat kieliopit (CFGs) yrityksenä mallintaa kieliä. Sen jälkeen niitä on käytetty laajasti erilaisissa tietojenkäsittelytieteen sovelluksissa. Cfg on rekursiivinen luonne ja koostuvat joukko sääntöjä, jotka voivat ajaa merkkijonoja aakkoset, myös kutsutaan sanoja. Kieliopin synnyttämää sanajoukkoa kutsutaan kyseisen kieliopin kieleksi. Kieliopin sanotaan olevan yksiselitteinen, jos sanojen ja niiden deskriptiivisten derivointien välillä on yksi yhteen-vastaavuus. Stokastiset CFGs (SCFGs) antavat todennäköisyydet jokaiselle säännölle, joka puolestaan antaa todennäköisyysarvon jokaiselle sanalle kertomalla kyseisen sanan johtamiseen käytettyjen sääntöjen todennäköisyydet . Grenander, Kuich , Hutchins, Soule ja muut ovat tutkineet tärkeitä ominaisuuksia CFGs ja SCFGs, kuten lähentyminen keskimääräinen pituus johdannaisten, kapasiteetti , tai Shannonin entropia (Shannon entropia), kuten on määritelty, käyttäen tuottaa-toimintoja tekniikoita. RNA: n sekundaarirakennekaavio on myös asiayhteydestä vapaa, mikä mahdollistaa sen kuvaamisen tällaisilla kieliopeilla. RNA: n sekundaarirakenteen kuvasivat ensin virallisesti Smith ja Waterman . Tämän jälkeen Stein ja Waterman tutkivat RNA: n sekundaarirakenteiden kombinatorisia piirteitä ja myöhemmin Wienot ja Vauchaussade de Chaumont , Hofacker et al. , Nebel, Liao ja Wang, Doslic et al. ja toiset käyttävät generoivia funktioita ja todennäköisyyksiä tuottavia funktioita.

SCFGs: llä on ollut suuri vaikutus RNA: n sekundaarirakennetutkimuksiin . RNA: n sekundaarirakenteen mallinnus auttaa meitä tekemään ennusteita RNA: n rakenteesta ja sen myöhemmästä biologisesta toiminnasta, koska monien RNA: iden, kuten erilaisten nonproteiinia koodaavien RNA: iden (ncrna) toiminnot liittyvät niiden rakenteisiin. Tyypillisesti RNA: n sekundaarirakenteen ennustaminen tapahtuu minimoimalla sekvenssin taittoenergiaa termodynaamiseen perustuvassa taittomallissa, kuten Boltzmannin Ensemblessä . SCFGs taas ovat kovarianssimalleja, jotka voivat jäljitellä RNA: n taittumista joustavammin. SCFG-pohjaisen taittomallin tapauksessa todennäköisyysarvot annetaan kaikille mahdollisille RNA-sekvenssin taittumisskenaarioille. Tämän jälkeen RNA-sekvenssin sekundaarirakenteeksi ennustetaan rakenne, jolla on maksimitodennäköisyysarvo (ML). SCFG-pohjaisten mallien ML-ennustus voidaan tehdä Cocke-Younger-Kasami (CYK) – algoritmilla. Energian minimoinnin tapaan CYK-algoritmi toteutetaan dynaamisen ohjelmoinnin avulla. Mallisuunnittelun tavoitteena on saada mahdollisimman samankaltaisia ML-estimaatteja kuin tunnetut RNA-toisiorakenteet, jolloin todennäköisyyksien jakaminen sääntöihin on kriittinen ja haastava tehtävä. Rivas tarjoaa syvällisemmän näkemyksen RNA: n sekundaarirakenteen mallinnuksen eri osa-alueista.

Current expectation maximization (EM) – mallin koulutusmallit koostuvat yleensä seuraavista kahdesta vaiheesta: ensinnäkin CYK-algoritmia käytetään jokaisen harjoitusjoukon RNA-sekvenssin rakenteen ennustamiseen (maksimointivaihe). Toiseksi SCFG: n sääntötodennäköisyydet arvioidaan uudelleen niiden ennusteissa esiintyvien esiintymistiheyksien perusteella (estimointivaihe). Nämä estimaatit voidaan laskea joko Durbin et al-asiakirjassa selitetyllä Laplace prior-lähestymistavalla. tai samankaltaisten taajuusperusteisten lähestymistapojen käyttöönotto. Iteratiivista EM-menettelyä voidaan jatkaa, kunnes tuloksena olevat säännön todennäköisyydet antavat halutun tarkkuuden. Mallikoulutustekniikat voivat vaihdella joko ML-kriteerin määrittelyssä (yhteinen vs. ehdollinen) tai säännön todennäköisyyden estimointitekniikoissa . SCFG-pohjainen RNA-taittuva malli voi koostua joko kevyestä SCFG: stä, jossa on vain muutama kielioppisääntö, tai se voi olla raskaansarjan kielioppi, joka koostuu monista säännöistä, kuten Rivas et al. .

tässä teoksessa SCFG: n Shannonin entropia, joka merkitään tässä grammar space (GS) entropiaksi, lasketaan analyyttisesti ja otetaan käyttöön RNA: n sekundaarirakenteen mallinnuksessa kriittisenä kieliopin ominaisuutena. Esitetyt muotoilut ovat yhdenmukaisia kieliopin entropian yleisen muodon kanssa, joka tunnetaan derivoituvana entropiana, ja niitä löytyy Grenanderista ja Soulesta . Jaksossa 9.2, kaava on esitetty laskettaessa Shannon entropia äärettömän suuri probabilistinen tilaa rakenteellisesti yksiselitteinen RNA-mallinnus grammars1, joka on yhdenmukainen derivoituvien entropia muotoiluja esitetty Grenander . Useiden vakiintuneiden RNA-taittomallien GS-entropia-arvot lasketaan tämän jälkeen 9.3 kohdan eri parametrijoukoissa. Kohdassa 9.4 ehdotetaan kriteeriä SCFG-pohjaiselle RNA-sekundaarirakennemallin koulutukselle GS-entropian perusteella. Lopuksi 9.5 jakso koostuu keskusteluista ja johtopäätöksistä.