Shannon Entropy

9.1 Introducere

Chomsky a formalizat inițial gramatici fără context (cfg) ca o încercare de a modela limbile. De atunci, acestea au fost utilizate pe scară largă într-o varietate de aplicații de informatică. Cfg – urile au o natură recursivă și sunt compuse din seturi de reguli care pot conduce șiruri de alfabete, denumite și cuvinte. Setul de cuvinte generate de o gramatică este denumit limba acelei gramatici. Se spune că o gramatică este lipsită de ambiguitate dacă există o corespondență unu-la-unu între cuvinte și derivările lor descriptive. Cfg-urile stocastice (SCFGs) atribuie probabilități fiecărei reguli, care la rândul său atribuie o valoare de probabilitate fiecărui cuvânt prin înmulțirea probabilităților regulilor utilizate pentru a deriva acel cuvânt . Grenander, Kuich, Hutchins, Soule și alții au investigat proprietăți importante ale cfg – urilor și Scfg-urilor, cum ar fi convergența lungimii medii a derivărilor, capacitatea sau entropia lui Shannon (entropia Shannon) așa cum este definită în, folosind tehnici de funcții generatoare. Structura secundară schematică a ARN are, de asemenea, o natură fără context, permițându-i să fie descrisă de astfel de gramatici. Structura secundară a ARN a fost descrisă pentru prima dată formal de Smith și Waterman . Caracteristicile combinatorii ale structurilor secundare ARN au fost apoi explorate de Stein și Waterman și ulterior studiate de Viennot și Vauchaussade de Chaumont , Hofacker și colab. , Nebel, Liao și Wang, Doslic și colab. și alții care folosesc funcții generatoare și funcții generatoare de probabilitate.

Scfg-urile au avut un impact mare asupra studiilor de structură secundară ARN . Modelarea structurii secundare a ARN ne ajută să facem predicții despre structura ARN și funcția sa biologică ulterioară, deoarece funcțiile multor ARN-uri, cum ar fi diferite clase de ARN-uri care codifică nonproteină (ncRNA) sunt legate de structurile lor. De obicei, predicția structurii secundare a ARN se face prin minimizarea energiei de pliere a secvenței sub un model de pliere bazat pe termodinamică, cum ar fi ansamblul Boltzmann . Scfg-urile, pe de altă parte, sunt modele de covarianță care pot imita plierea ARN cu mai multă flexibilitate. În cazul unui model de pliere bazat pe SCFG, valorile probabilității sunt atribuite tuturor scenariilor de pliere posibile ale unei secvențe ARN. Apoi, structura cu valoare maximă de probabilitate (ML) este prezisă ca structură secundară a secvenței ARN. Predicția ML a modelelor bazate pe SCFG se poate face prin algoritmul Cocke-Younger-Kasami (CYK). Similar cu minimizarea energiei, algoritmul CYK este implementat prin programare dinamică. Scopul proiectării modelului este de a obține estimări ML care sunt cât mai similare cu structurile secundare ARN cunoscute, făcând astfel atribuirea probabilităților regulilor o sarcină critică și provocatoare. Rivas oferă o perspectivă mai aprofundată asupra diferitelor aspecte ale modelării structurii secundare ARN.abordările actuale de formare a modelului de maximizare a așteptărilor (EM) constau în general din următoarele două etape: în primul rând, algoritmul CYK este utilizat pentru predicția structurii fiecărei secvențe ARN a setului de antrenament (etapa de maximizare). În al doilea rând, probabilitățile de regulă ale SCFG sunt reevaluate pe baza numărului sau frecvențelor aparițiilor lor în predicții (etapa de estimare). Aceste estimări pot fi calculate fie folosind abordarea anterioară Laplace explicată în Durbin și colab. sau implementarea unor abordări similare bazate pe frecvență. Procedura EM iterativă poate continua până când probabilitățile regulii rezultate produc precizia dorită. Tehnicile de formare a modelelor pot varia, fie în definiția criteriului ML (comun vs. condițional), fie în tehnicile de estimare a probabilității regulii . Un model de pliere ARN bazat pe SCFG poate consta fie dintr-un SCFG ușor, cu doar câteva reguli gramaticale, fie poate fi o gramatică grea formată din multe reguli, cum ar fi super-gramatici descrise în Rivas și colab. .

în această lucrare, entropia Shannon a SCFG, notată aici ca entropie a spațiului gramatical (GS), este calculată analitic și introdusă ca o caracteristică gramaticală critică în modelarea structurii secundare a ARN. Formulările prezentate sunt în concordanță cu forma generală a entropiei gramaticale cunoscută sub numele de entropie derivativă și pot fi găsite în Grenander și Soule . În Secțiunea 9.2, o formulare este prezentată pentru calcularea entropiei Shannon a spațiului probabilistic infinit de mare al gramaticilor de modelare ARN fără ambiguitate structurală1 care este în concordanță cu formulările de entropie derivativă prezentate în Grenander . Valorile entropiei GS ale mai multor modele de pliere ARN bine stabilite sunt apoi calculate sub diferite seturi de parametri din secțiunea 9.3. În secțiunea 9.4, se propune un criteriu pentru formarea modelului de structură secundară ARN bazată pe SCFG pe baza entropiei GS. În cele din urmă, secțiunea 9.5 constă în discuții și concluzii.