Diese Seiten können nicht richtig dargestellt werden, da Sie Ihren Internet Explorer mit aktivierter Kompatibiltätsansicht verwenden. Wir empfehlen 'fu-berlin.de' aus der Liste der Websites mit aktivierter Kompatibilitätsansicht zu entfernen:
- Blenden Sie bitte in Ihrem Internet Explorer die Menüleiste ein, indem Sie entweder 'Alt' drücken oder in der Adressleiste mit der rechten Maustaste klicken und dann 'Menüleiste' auswählen.
- Klicken Sie auf 'Extras' und wählen das Menü 'Einstellungen der Kompatibilitätsansicht' aus.
- Wählen Sie unter 'Zur Kompatibilitätsansicht hinzugefügte Websites' 'fu-berlin.de' aus.
- Klicken Sie auf 'Entfernen'.
Suffixbaum (Informatik)
Ein wichtiger Bereich der Informatik ist die Verarbeitung von Zeichenketten (z. B. Buchstaben oder Zahlen), welche auf Englisch als Strings bezeichnet werden. Zur Speicherung von Strings können als Datenstrukturen sogenannte Suffixbäume genutzt werden. Suffixbäume erlauben unter anderem die schnelle Suche von Wörtern in einem langen Text. In der Bioinformatik kommen sie insbesondere im Umgang mit biologischen Sequenzen wie DNA-, RNA- oder Proteinsequenzen zum Einsatz.
Ein Substring eines Strings ist jede beliebige Teilfolge von Zeichen eines Strings. Substrings des Strings BANANE sind beispielsweise BA, ANA oder NE.
Ein Suffix eines Strings ist ein Substring am Ende dieses Strings; so sind beispielsweise BANANE, ANANE, NANE, ANE, NE und E die Suffixe des Strings BANANE.
Als gerichteten Baum bezeichnet man in der Informatik einen speziellen Graphen, der aus Knoten und Kanten besteht, die in eine bestimmte Richtung zeigen, sodass keine Zyklen entstehen (siehe Abbildung). Der oberste Knoten ist die Wurzel des Baumes. Jeder Knoten, von dem weitere Kindknoten ausgehen, ist ein innerer Knoten, während Knoten ohne ausgehende Kindknoten als Blätter bezeichnet werden.
Ein Suffixbaum für einen String der Länge n ist ein gerichteter Baum mit den folgenden Eigenschaften:
- Der Baum hat genau n Blätter, die von 1 bis n nummeriert werden.
- Jeder innere Knoten mit Ausnahme der Wurzel hat mindestens zwei Kindknoten.
- Jede Kante zwischen zwei Knoten ist mit einem nicht-leeren Substring des Strings beschriftet.
- Alle Kanten, welche denselben Knoten verlassen, müssen Beschriftungen haben, die mit unterschiedlichen Zeichen beginnen.
- Der String, den man enthält, wenn man alle Kantenbeschriftungen auf dem Weg von der Wurzel bis zum i-ten Blatt zusammensetzt, ist das i-te Suffix des Strings.
Für gewöhnlich wird ein $-Zeichen an das Ende des Strings und somit auch an das Ende jedes Suffix angefügt, welches anzeigt, wann ein Suffix zu Ende ist.
Der unten abgebildete Baum ist ein unvollständig ausgefüllter Suffixbaum für den String ANANAS$. Ordnen Sie die Substrings ihren jeweiligen Kanten zu. Ziehen Sie dafür die Substrings per Drag & Drop in den Suffixbaum.
Sie erhalten ein Feedback zu den einzelnen Antworten, indem Sie auf das klicken.
Die Lösung der Aufgabe lautet wie folgt
