PUB - Publikationen an der Universität Bielefeld

Abstrakte Shapes wurden 2004 bei der Analyse von RNA-Sekundärstrukturen eingeführt und haben seither viele Anwendungen gefunden. Abstrakte Shapes sind Abstraktionen von Strukturen, wobei eine einzelne Shape eine Klasse von ähnlichen Strukturen enthält. Weiterhin enthält eine Shape als repräsentative Struktur diejenige mit der kleinsten freien Energie. Das Werkzeug RNAshapes bietet 5 verschiedene Abstraktionslevel (Shape-Typen), die hierarchisch aufgebaut sind. Je niedriger das Shape-Level, desto mehr Strukturelemente - wie Bulge oder Internal-Loops - werden in die Shape-Repräsentation einbezogen. Die Anzahl der Shapes ist exponentiell in der Sequenzlänge, wächst aber langsamer als die Anzahl der Strukturen. Das Wachstumsverhalten ist aus zwei Gründen interessant: Erstens geht es in die asymptotische Laufzeit von Algorithmen zur Shape-Analyse ein. Zweitens gibt die Gesamtzahl der Shapes eine Obergrenze für die Größe von Shape-Indices an, zu denen RNA-Datenbanken für die Struktur-basierte Suche vorverarbeitet werden. Die offene Frage der asymptotischen Anzahl der Shapes hat einiges Interesse in der theoretischen Bioinformatik gefunden. Die Asymptotik der Anzahl der Shapes wurden durch Lorenz, Ponty und Clote (2008) für Sequenzen der Länge n (Shape Typ 3 und 5) bestimmt, während Nebel und Scheid (2009) Shapes der Länge n untersuchten (Shape Typ 1-5). Das Anliegen der Arbeit war es, gewisse kombinatorische Aussagen über abstrakte Shapes zu gewinnen. Wieviel Shapes gibt es mit n Klammerpaaren? Wieviel Shapes gibt es zu Sequenzen der Länge n? Was ist die erwartete Anzahl der Shapes für eine Sequenz der Länge n? Zur letzten Frage erscheint ein theoretischer Zugang schwierig; daher wurden empirische Messungen ins Auge gefasst. In meinen Ergebnissen habe ich die Rekurrenzformel für die Anzahl der Shapes aller Sequenzen der Längen <=n und ihrer asymptotischen Anzahl berechnet. Weiterhin habe ich die Rekurrenzformel für die Anzahl der Shapes mit n Klammerpaaren für Shape-Typ 1-5 durch Shape-Grammatik hergeleitet und die asymptotische Anzahl für Shape 3, 4 und 5 berechnet. Die Asymptotik für Shape Typen 3 und 4 ist gleich, weil die Shapes die gleichen Repräsentationen haben. Trotzdem hat eine konkrete Sequenz mehr Typ 4- als Typ 3-Shapes! Das liegt am Unterschied in den Shape-Abstraktionsabbildungen und ist auf der Ebene der Shapes-Notationen nicht mehr erkennbar. Der asymptotische Wert für die Anzahl der Shapes aller Sequenzen der Länge n hat die allgemeine Formel a^n*b*n^(-3/2). Dies gilt für alle Shape-Typen. Ein solche Formel entspricht dem Erwartungswert für die Anzahl der Shapes. Mit Hilfe des Programms RNAshapes habe ich für eine große Menge Sequenzen bestimmter Länge die jeweiligen Anzahlen des Shapes-Typs 5 im Shape Raum bestimmt. Mit der statistischen Analyse habe ich die Parameter a und b der allgemeinen Formel bestimmt.