Shannon-Entropie

9.1 Einführung

Chomsky formalisierte zunächst kontextfreie Grammatiken (CFGs) als Versuch, Sprachen zu modellieren. Seitdem werden sie in einer Vielzahl von Informatikanwendungen eingesetzt. CFGs sind rekursiv und bestehen aus Regelsätzen, die alphabetische Zeichenfolgen steuern können, die auch als Wörter bezeichnet werden. Die Menge der Wörter, die von einer Grammatik erzeugt wird, wird als die Sprache dieser Grammatik bezeichnet. Eine Grammatik gilt als eindeutig, wenn zwischen den Wörtern und ihren beschreibenden Ableitungen eine Eins-zu-Eins-Entsprechung besteht. Stochastische CFGs (SCFGs) weisen jeder Regel Wahrscheinlichkeiten zu, die wiederum jedem Wort einen Wahrscheinlichkeitswert zuweist, indem sie die Wahrscheinlichkeiten der Regeln multiplizieren, die zum Ableiten dieses Wortes verwendet werden . Grenander , Kuich , Hutchins , Soule und andere haben wichtige Eigenschaften von CFGs und SCFGs untersucht, wie Konvergenz der durchschnittlichen Länge von Ableitungen, Kapazität oder die Shannon-Entropie (Shannon-Entropie), wie in definiert , unter Verwendung von Generierungsfunktionstechniken. Das Sekundärstrukturschema der RNA hat auch eine kontextfreie Natur, so dass es durch solche Grammatiken beschrieben werden kann. Die Sekundärstruktur der RNA wurde erstmals von Smith und Waterman formal beschrieben. Kombinatorische Merkmale von RNA-Sekundärstrukturen wurden dann von Stein und Waterman untersucht und anschließend von Viennot und Vauchaussade de Chaumont untersucht , Hofacker et al. , Nebel , Liao und Wang , Doslic et al. und andere mit generierenden Funktionen und wahrscheinlichkeitsgenerierenden Funktionen.

SCFGs hatten einen großen Einfluss auf RNA-Sekundärstrukturstudien . Die RNA-Sekundärstrukturmodellierung hilft uns, Vorhersagen über die RNA-Struktur und ihre nachfolgende biologische Funktion zu treffen, da die Funktionen vieler RNAs wie verschiedener Klassen von nicht proteinkodierenden RNAs (ncRNA) mit ihren Strukturen zusammenhängen. Typischerweise wird die Vorhersage der RNA-Sekundärstruktur durch Minimierung der Faltungsenergie der Sequenz unter einem thermodynamischen Faltungsmodell wie dem Boltzmann-Ensemble durchgeführt . SCFGs hingegen sind Kovarianzmodelle, die die RNA-Faltung flexibler imitieren können. Im Falle eines SCFG-basierten Faltungsmodells werden allen möglichen Falt-Szenarien einer RNA-Sequenz Likelihood-Werte zugeordnet. Dann wird die Struktur mit maximalem Wahrscheinlichkeitswert (ML) als Sekundärstruktur der RNA-Sequenz vorhergesagt. Die Vorhersage von SCFG-basierten Modellen kann durch den Cocke-Younger-Kasami (CYK) -Algorithmus erfolgen. Ähnlich wie bei der Energieminimierung wird der CYK-Algorithmus durch dynamische Programmierung implementiert. Das Ziel des Modelldesigns ist es, ML-Schätzungen zu erhalten, die den bekannten RNA-Sekundärstrukturen so ähnlich wie möglich sind, wodurch die Zuordnung von Wahrscheinlichkeiten zu Regeln zu einer kritischen und herausfordernden Aufgabe wird. Rivas bietet einen tieferen Einblick in verschiedene Aspekte der RNA-Sekundärstrukturmodellierung.Current Expectation Maximization (EM) -Modelltrainingsansätze bestehen im Allgemeinen aus den folgenden zwei Schritten: Zunächst wird der CYK-Algorithmus zur Strukturvorhersage jeder RNA-Sequenz des Trainingssatzes verwendet (Maximierungsschritt). Zweitens werden die Regelwahrscheinlichkeiten der SCFG basierend auf den Zählungen oder Häufigkeiten ihres Auftretens in den Vorhersagen neu geschätzt (Schätzschritt). Diese Schätzungen können entweder unter Verwendung des Laplace-Prior-Ansatzes berechnet werden, der in Durbin et al. oder ähnliche frequenzbasierte Ansätze einsetzen. Das iterative EM-Verfahren kann fortgesetzt werden, bis die resultierenden Regelwahrscheinlichkeiten die gewünschte Genauigkeit ergeben. Modelltrainingstechniken können variieren, entweder in der Definition des ML-Kriteriums (Joint vs. conditional) oder in Regelwahrscheinlichkeitsschätzungstechniken . Ein SCFG-basiertes RNA-Faltmodell kann entweder aus einem leichten SCFG mit nur wenigen Grammatikregeln bestehen oder es kann sich um eine schwergewichtige Grammatik handeln, die aus vielen Regeln besteht, wie sie in Rivas et al. .

In dieser Arbeit wird die Shannon-Entropie der SCFG, hier als Grammar space (GS) Entropy bezeichnet, analytisch berechnet und als kritisches grammatikalisches Merkmal in die RNA-Sekundärstrukturmodellierung eingeführt. Die vorgestellten Formulierungen stimmen mit der allgemeinen Form der Grammatikenentropie überein, die als Derivationsentropie bekannt ist, und kann in Grenander und Soule gefunden werden . In Abschnitt 9.2 wird eine Formulierung zur Berechnung der Shannon-Entropie des unendlich großen probabilistischen Raums strukturell eindeutiger RNA-modellierender Grammatiken1 vorgestellt, die mit den in Grenander vorgestellten derivativen Entropieformulierungen übereinstimmt. Die GS-Entropiewerte mehrerer etablierter RNA-Faltungsmodelle werden dann unter verschiedenen Parametersätzen in Abschnitt 9.3 berechnet. In Abschnitt 9.4 wird ein Kriterium für das SCFG-basierte RNA-Sekundärstrukturmodelltraining vorgeschlagen, das auf der GS-Entropie basiert. Schließlich besteht Abschnitt 9.5 aus Diskussionen und Schlussfolgerungen.