PUB - Publikationen an der Universität Bielefeld

Hidden Markov Models (HMMs) und stochastische Grammatiken können zur Modellierung biologischer Makromoleküle wie Proteinen, DNA und RNA verwendet werden. Hierbei wird die Primär- und (mit gewissen Einschränkungen) auch die Sekundärstruktur erfasst. Bestimmte Elemente der Sekundärstruktur (wie z.B. Pseudoknoten) können jedoch nicht modelliert werden. Hierfür werden die sogenannten "Parallel-Grammatiken" eingeführt. Zusätzlich zu den üblichen Regeln einer kontextfreien Grammatik treten hierbei "Parallelregeln" auf. Eine solche Parallelregel stellt ein Paar von zwei Regeln einer regulären Grammatik dar; dementsprechend ergeben sich rechtsrechtslineare und rechtslinkslineare Parallelregeln. Die Anwendung einer Parallelregel besteht in der quasi gleichzeitigen Anwendung ihrer beiden Einzelregeln. Die durch Parallelgrammatiken erfassten Sprachen sind in der Chomsky-Hierarchie zwischen den kontextfreien und den kontextsensitiven anzusiedeln. Durch entsprechende Adaptionen des Earley'schen Algorithmus ist es möglich, das Problem der Syntaxanalyse ("Parsing") auch für Parallelgrammatiken zu lösen. Weiterhin wird gezeigt, wie der Earley'sche Algorithmus in Zusammenhang mit stochastischen Grammatiken vorteilhaft genutzt werden kann. Biologische Anwendungsbeispiele stochastischer Grammatiken wie Klassifikation unterschiedlicher Proteinfamilien, Erzeugung von Alignments, Rekonstruktion von Sekundärstrukturen von RNAs werden gegeben.