Fakultät für Informatik - Technische Universität München Lehrstuhl für Effiziente Algorithmen

Systementwicklungsprojekt

DNS Signaturen zum Herkunftsnachweis bei Rindfleisch

Hintergrund: Im Rahmen eines Projektes des Lehrstuhls für Tierzucht der TU München wird eine standardisierte DNS Signatur zum Herkunftsnachweis und für die Abstammungskontrolle bei Rindern entwickelt. Damit soll die Rinderzucht unterstützt und die Lebensmittelsicherheit verbessert werden.

Bei dem Verfahren wird aus dem Genom eines Rinds ein eindeutiger Identifikator generiert. Dieser Identifikator besteht aus einer Sequenz der Länge 40 (später sollen es 96 oder sogar 384 Zeichen werden). Jedes Zeichen kann vier verschiedene Werte annehmen, wobei einer der Werte für „unbestimmt” steht. Es soll eine Datenbank angelegt werden, in der später 100.000 bis 100.000.000 DNS Signaturen verschiedener Rinder gespeichert werden.

Aufgabe: Ein wichtiges Problem ist das Wiederauffinden einer Signatur in der Datenbank. Dabei müssen einerseits Messfehler und andererseits die unbestimmten Zeichen berücksichtigt werden. Bei einem Vergleich einer neuen Sequenz mit der Datenbank sollen alle Sequenzen gefunden werden, die eine hinreichende Ähnlichkeit mit der Mustersequenz haben. Dabei können nur Zeichen, die in keiner der zu vergleichenden Sequenzen unbestimmt sind, in Betracht gezogen werden. Es muss also eine bestimmte Mindestzahl an Übereinstimmungen vorliegen, und gleichzeitig darf es nur eine Maximalzahl von Fehlern geben.

Es wird erwartet, dass in einem späteren Stadium bis zu 10.000 neue Sequenzen pro Tag gemessen, mit den vorhandenen Sequenzen verglichen und in die Datenbank eingeordnet werden müssen. Dabei soll die Datenbank und der Vergleich auf einem herkömmlichen PC laufen.

Im Rahmen dieses Systementwicklungsprojektes soll ein Algorithmus entworfen, implementiert und getestet werden, der diesen Anforderungen genügt. Zudem besteht die Möglichkeit sich an der Einbindung in das Projekt (z.B. Datenbankanbindung etc.) zu beteiligen.

Vorkenntnisse: Zur Lösung des Problems wird man voraussichtlich neue Algorithmen entwerfen bzw. bekannte Algorithmen modifizieren müssen. Dazu sind Kenntnisse von Text-Algorithmen von Vorteil (z.B. aus den Vorlesungen „Algorithmische Bioinformatik I/II” oder „Effiziente Algorithmen I/II”), aber nicht unbedingt Voraussetzung.

Wegen der großen Datenmengen empfiehlt sich eine Implementation in einer „schnellen”, imperativen Sprache, wie z.B. „C” oder „C++”.