This is an old page and only archived here for historic reasons.

Click here to get to the present project page.

	Deutsches Krebsforschungszentrum Abteilung Molekulare Biophysik Prof. Dr. S. Suhai
	Universität Heidelberg  Institut für Medizinische Biometrie und Informatik  Prof. Dr. R. Haux

Projektleitung:
Prof. Dr. Sándor Suhai
DKFZ-Heidelberg, Abteilung Molekulare Biophysik H0200.

Mitarbeiter:
Dipl.-Inform. Med. Bastien Chevreux
Dipl.-Inform. Med. Thomas Pfisterer

Förderung:
Bundesministerium für Bildung, Wissenschaft, Forschung und Technologie
Förderkennzeichen 01 KW 9611

Kooperationen:
Institut für Molekulare Biotechnologie e.V.  07708 Jena
Prof. Dr. Thomas Wetter, Abteilung Medizinische Informatik
 

Gesamtprojekt

Problematik
Da die Ergebnisse der Elektrophorese einen gewissen Fehleranteil besitzen (durchschnittlich 1-2%), muss auch bei der Assemblierung mit Fehlern gerechnet werden. Es wird also nicht nur nach genauen Übereinstimmungen gesucht, sondern ein gewisses Maß an Abweichungen (andere Base oder Einfügung oder Löschung einer Base) muss  beim Vergleich inKauf genommen werden. Bei der Assemblierung kann es nun vorkommen, dass Übereinstimmungen nicht gefunden werden, da sich die Fragmente zu stark unterscheiden oder dass Fragmente fehlerhaft wegen zufälligen Ähnlichkeiten zusammengesetzt werden.

Die Abweichungen durch Fehler bei der Elektrophorese und die nicht oder fehlerhaft gefundenen Übereinstimmungen müssen nachträglich manuell bearbeitet werden (Editieren). Dies ist ein sehr zeitaufwendiger Prozess, der sich zunehmend als Flaschenhals bei der Sequenzierung herausstellt.

Zielsetzung:
Das Assemblieren und Editieren genomische Sequenzdaten soll durch geeignete Werkzeuge unterstützt werden. Hierbei soll sowohl die Assemblierung verbessert werden (Teilprojekt 1) indem weniger Fragmente nicht oder falsch eingesetzt werden und es sollen bisher manuell durchgeführte Editierprozesse teilweise automatisiert werden (Teilprojekt 2).

Stand des Projekts:
Siehe Stand der Teilprojekte.

Teilprojekt 1: Assemblieren von Nukleotidsequenzen

Gegenstand und Motivation
Nach einer ersten Vorverarbeitungsstufe - zum Säubern der Rohdaten von schlechtem Datenmaterial - stellt die Shotgunassembliereung von Gensequenzstücken den erste Schritt zur Rekonstruktion eines Genoms dar. Die zur Zeit existierenden und benutzten Verfahren arbeiten jedoch nur Basenorientiert und/oder auf sequentieller Basis, ohne bei Bedarf auf die Rohdaten zurückzugreifen.

Problematik
Für die Assemblierung lassen sich folgende große Problemkreise definieren:

• Nach der o.g. Vorverarbeitungsstufe beinhalten die Sequenzdaten noch immer ca. 1 bis 2% fehlerhafte oder falsch interpretierte Basen. Zusätzlich kann sich noch aus dem Reproduktionsprozess stammende und nicht erkannte Fremd-DNA (Sequencing-Vector) in den Fragmenten (Reads) befinden.
• Im Genom befinden sich zum Teil sehr lange Stücke in mehrfacher Ausführung (Repeats), welche sich nicht oder (schlimmer) nur in einigen wenigen Basen unterscheiden.
• Die Richtung der Reads im ursprünglichen Genom ist unbekannt. Jeder Read muss deshalb in seiner Vorwärtsrichtung, als auch seiner Rückwärtsrichtung (Komplementärrichtung) untersucht werden.

Zielsetzung
Ziel der Arbeit ist es, ein Verfahren zu entwickeln, das aufgrund der Gesamtheit der zur Verfügung stehenden Rohdaten eine möglichst optimale Assemblierung gewährleistet, welche die noch zu korrigierenden Fehler für Teilprojekt 2 minimal hält. Weiterhin sollen Methoden für den automatischen Editierer bereitgestellt werden, z.B. um die Benutzung von verdeckten Daten in Reads zu ermöglichen, welche eine größtmögliche Sicherheit in den Entscheidungskriterien schaffen.

Stand des Projekts (15.9.1998)
Die vorverarbeiteten Rohdaten werden gescannt und jedes Fragment mit allen anderen verglichen. Potentielle Matchingkandidaten werden genauer anlysiert. Daraus wird ein Gesamtüberblick des Assemblierungsprojektes erstellt und die so gewonnenen Informationen werden für den Aufbau von Contigs genutzt. Das assemblierte Projekt wird im standardisierten CAF Format ausgegeben, wodurch es für gängige Finishingtools konvertiert werden kann.
Zur Zeit wird ein Verfahren erarbeitet, welches fälschlich eingebaute Reads (z.B. versursacht durch hochrepetitive Sequenzen) durch signalbasierte Entscheidungen erkennt und wieder freigibt.

Plattform: UNIX, z.Z. SGI, Linux (Intel) und SUN Solaris
Programmiersprachen: C/C++, Shell-Skripte

Teilprojekt 2: Automatisches Editieren

Gegenstand und Motivation
Bei der Sequenzierung von DNA oder RNA ist eine manuelle Nachbearbeitung der Sequenzdaten nach dem Assemblieren erforderlich. Diese Nachbearbeitung (Editieren) wird durch qualifiziertes Laborpersonal durchgeführt und stellt eine große zeitliche Belastung neben der Labortätigkeit dar.

Problematik
Durch die beim Assemblieren gefundenen Überlappungen stehen meistens an einer bestimmten Stelle der Sequenz die Basen aus mehreren Fragmenten (Reads) zur Verfügung. Sind diese Basen nicht identisch, so entsteht das Entscheidungsproblem: Welches ist die korrekte Base an dieser Stelle? (oder ist hier sogar ein Fragment fehlerhaft eingesetzt worden?). Diese Entscheidung wird dann unter Zuhilfenahme der Rohdaten (vor Bestimmung der Basen , dem sog. Basecalling - denn darin vermuten wir ja einen möglichen Fehler) der beteiligten Sequenzen getroffen. Bei der Beurteilung der Signale wird auch Wissen über die Leserichtung der einzelnen Reads und über Eigenschaften der verwendeten Färbechemie verwendet.

Zielsetzung
Ziel dieser Arbeit ist es den manuellen Editieraufwand beim Sequenzieren zu verringern. Dabei sollen für die Repräsentation und Verarbeitung des beteiligten Fachwissens geeignete Methoden der Wissensverarbeitung eingesetzt werden und in einem Werkzeug zur Verfügung gestellt werden.

Weiterhin sollen Funktionen bereitgestellt werden, die im Rahmen der Assemblierung verwendet werden können um zusätzliche Entscheidungskriterien für zweifelhafte Situationen zu ermitteln.

Stand des Projekts (15.09.98)
Der Ablauf des Editierprozesses ist auf der Ebene der Inferenzstruktur modelliert. Ein einfacher Prototyp der die Entscheidungsprobleme "Overcall" (eine Base wurde zu oft gelesen) und "Additional Call" (eine Base wurde zusätzlich gelesen) die sich auf die Konsensussequenz auswirken, regelbasiert bearbeitet, wurde implementiert und evaluiert.

Die Evaluation zeigte, daß die Qualität der Entscheidungen zufriedenstellend ist, so daß eine Erweiterung bezüglich der Breite der behandelten Probleme sinnvoll ist. Dies soll sowohl durch eine verbesserter Problemidentifikation die auch für mehrfache Fehler sinnvolle Hypothesen erzeugt und durch die Realisierung der bisher fehlenden Entscheidungsprobleme "Missing Call", "Undercall" und "Wrong Call" erreicht werden. Dieser Prototyp wird derzeit realisiert.
 

Plattform: UNIX, z.Z. SGI, Linux (Intel) und SUN Solaris
Programmiersprachen: C, C++, CLIPS, Tcl/Tk.

Publikationen

• WETTER T, PFISTERER T (1998): Modeling for Scalability - Ascending into Automatic Genome Sequencing. Eleventh Workshop on Knowledge Acquisition, Modeling, and Management (KAW'98) Banff, Canada, April 18-23, 1998.

• CHEVREUX C, PFISTERER T, WETTER T, SUHAI S (1998): Projekt 01 KW 9611(englisch).

• PRIMER ON MOLECULAR GENETICS. U.S. Department of Energy, Office of Energy, June 1992 (online version)