Die sich weltweit rasant entwickelnden Biowissenschaften und sich daraus neu ergebenen Einsatzgebiete von Computern führen zu einer enormen Menge an neuen biologischen Daten und gleichzeitig zu vielen ungelösten Fragestellung. Man denke in diesem Zusammenhang an die Sequenzzierung des menschlichen Genoms.

Um die in den Daten enthaltenen Informationen „sichtbar“ zu machen wurden verschiedene Ansätze versucht. Da die Standardanalysemethoden, wie Spreadsheets, ad-hoc Abfragen (SQL) und einfache statistische Verfahren, für diese riesigen Mengen an Daten nicht mehr hinreichend waren, steigerte sich die Nachfrage nach Methoden und Software zur intelligenten und automatisierten Auswertung dieser Datenmassen.

Die ab den 80er Jahren entwickelten Data Mining Ansätzen für das Bankwesen waren für die Bioinformatik der Grundstein für das Data Mining in den Biodaten. Dazu wurden Ansätze übertragen und an die neuen Daten angepasst. Durch den großen Unterschied zwischen den Daten aus diesen Bereichen mussten aber vor allem neue Ansätze entwickelt werden, die auf die neue Charakteristik der Daten abgestimmt sind.

In dieser Ausarbeitung soll ein Überblick gegeben werden, wie man mit verschiedenen Methoden aus der riesigen Menge von Daten nutzbare Informationen ziehen kann. Einleitend werden ganz allgemein auf die Begriffe Data Mining und Bioinformatik definiert und erläutert. Im weiteren wird auf die Anwendung des Data Mining in den Bereichen Biomarker Discovery, Genklassifikation und Proteinklassifikation eingegangen.

Da Data Mining in der Bioinformatik ein sehr großes Einsatzgebiet hat, kann in dieser Ausarbeitung nur ein kurzer Überblick gegeben werden.

2. Data Mining

2.1. Data Mining als Phase des KDD

Im Zeitalter der elektronischen Datenverarbeitung werden viele Daten erzeugt und auf elektronischen Speichermedien gespeichert. Die Masse der abgelegten Daten ist von Menschen nicht mehr überschaubar. Um diese Daten auswerten zu können, muss der Mensch auf geeignete Informationssysteme zurückgreifen, die eine Aufarbeitung der Datenbestände möglich machen.

Um neues Wissen aus den Daten zu extrahieren, entwickelte sich ein neues Forschungsgebiet in der Informatik, dass Knowledge Discovery from Databases (KDD). KDD stellt einen umfangreichen Prozess dar und wird nach Fayyad ([OB00]) wie folgt definiert:

Knowledge Discovery in Databases (KDD) bezeichnet den nichttrivialen Prozess der Identifikation valider, neuartiger, potentiell nützlicher und klar verständlicher Muster in Daten.

Der Ablauf dieses Prozesses ist in Abbildung 2.1 schematisch dargestellt. Der Prozess beinhaltet fünf Phasen, sie sequentiell durchlaufen werden. Die Phasen sind:

Selection

In dieser ersten Phase werden die Zieldatensätze identifiziert. Dabei wird eine

Auswahl aus der Roh-Datenmenge getroffen, da evtl. nur ein Teilbereich der Daten untersucht werden soll oder die Roh-Datenmenge zu umfangreich ist.

Preprocessing

Unter der Phase Preprocessing versteht man die Aufbereitung und Säuberung der ausgewählten Daten durch eventuelle Beseitigung oder Korrektur falscher Einträge, Ergänzung fehlender Objekte, Beseitigung unnötiger Information sowie Vereinheitlichung von Feldwerten.

Transformation

In dieser Phase werden die Daten für die nachfolgende Analyse vorbereitet, indem die Daten zum Beispiel durch Reduktion von Dimensionen oder andere Transformationsmethoden reduziert werden können.

Data Mining

Durch Anwendung bestimmter Verfahren des Data Mining werden interessierende Muster und Beziehungen in den Daten erkannt. Das Data Mining ist das Herzstück des KDD Prozesses und wird im nächsten Abschnitt noch etwas genauer beschrieben.

Interpretation/Evaluation

Diese Phase schließt den KDD Prozess ab. Die Ergebnisse (Muster) werden den Benutzer visuell ausgeben. Der Benutzer interpretiert die Ergebnisse. Werden die Ergebnisse als ausreichend und valide (gültig) erkannt, so ist der Prozess beendet. Ansonsten kann wahlweise jeder der vorigen Schritte beliebig wiederholt

Abbildung 2.1: Knowledge Discovery from Databases (nach [OB00])

2.2. Definition Data Mining

Data Mining wird von Fayyad in Abgrenzung zum Begriff KDD wie folgt definiert:

Data Mining ist ein Teilschritt des KDD-Prozesses, der aus Algorithmen besteht, die in akzeptabler Rechenzeit aus einer vorgegebenen Datenbasis eine Menge von Mustern liefern.

Für das Data Mining verwendet man als Datenbasis eine Datenbank oder ein Data Warehouse. Aus diesen Daten wird versucht Beschreibungen von Beziehungen zwischen Datensätzen oder den Daten innerhalb eines Datensatzes zu entdecken und Regelmäßigkeiten innerhalb den Daten aufzudecken. Diese Beziehungen und Regelmäßigkeiten in den Daten nennt man Muster (engl. patterns). Diese Muster sind die versteckten, aber potentiell nützlichen Informationen, die in den rohen Daten versteckt sind.

Ein wesentliches Merkmal von Data Mining ist die Hypothesenfreiheit. Die Hypothesenfreiheit bedeutet, dass zu Beginn der Analyse der Daten keine Hypothese entwickeln werden müssen. Die Hypothesen über mögliche Zusammenhänge, Muster oder Trends werden vom Data Mining Systemen automatisch generiert und anhand der Daten bzw. eines Trainingsdatensatz überprüft, um so aus einer Vielzahl von möglichen Hypothesen die Beste zu erkennen. Der Anwender hat lediglich die Interpretation der Ergebnisse vorzunehmen. Beim Data Mining werden die Annahmen datengetrieben generiert, ganz Gegensatz zum OLAP (Online Analytical Processing), bei denen der Nutzer durch die Betrachtung der Daten aus unterschiedlichen Sichten Hypothesen entwickelt, diese durch Wechseln der Sichtweise überprüft, verfeinert bzw. verwirft, d.h. bekannte Hypothesen verifiziert.

2.3. Data Mining Techniken

Der Kern des Data Mining sind die Algorithmen mit denen nach den Mustern gesucht wird. Es sind drei wichtige Techniken bekannt, die jetzt kurz vorgestellt werden.

Assoziationsregeln

Diese Data Mining Technik besteht in der Suche von Verbindungen, sprich konditionalen Regeln. Eine konditionale Regel ist eine Folge von ” Wenn Bedingungen, dann Ergebnis“. Ein Sonderfall der Assoziationsregeln ist die Warenkorbanalyse (engl. Market Basket Analyse), bei der überprüft wird welche Produkte häufig zusammen gekauft werden um so die den Verkauf zu steigern.

Clustering

Die Clusteranalyse unterteilt eine Menge von ungeordneten Objekten in Gruppen (Clustern), deren Objekte ähnlich sind. Zur Unterscheidung der Objekte wird ein Ähnlichkeitsmaß benutzt, welches den Abstand einzelner Objekte voneinander als Zahlenwert angibt. Die Wahl des Abstandsmaßes ist von Technik zu Technik unterschiedlich, ein einfaches Beispiel in 2D ist das euklidische Maß. So ergeben sich in Abbildung 2.2 zwei Cluster.

Abbildung 2.2: Zwei Cluster nach dem Euklidischen Maß

Klassifikation

Bei der Klassifikation werden Daten anhand einer Beispielmenge analysiert und so die Zuordnung von Objekten zu Klassen mit gemeinsamen Eigenschaften durchgeführt. Dabei wird die Beispielmenge benutzt um ein Modell zu erstellen, welches es erlaubt neue Daten aufgrund ihrer Eigenschaften in eine Klasse einzuordnen.

Um das Klassifizierungsproblem zu lösen gibt es eine Reihe von Techniken

§ Entscheidungsbäume

Ein Entscheidungsbaum ist eine Aneinanderkettung von logischen Regeln, die automatisch aufgebaut werden aufgrund einer Beispieldatenbank, dabei besitzt jede Regel die if. . . then Struktur.

§ Genetische Algorithmen

Genetische Algorithmen basieren auf denselben Regeln wie die natürliche Auslese. Sie beschreiben die Entwicklung einer Testgruppe in Abhängigkeit von seiner Umwelt.

§ Baysche Netze

Baysche Netze sind eine klassische Technik. Sie wird benutzt, um die Wahrscheinlichkeit eines Ereignis zu finden, wenn andere Ereignisse bekannt sind.

3. Bioinformatik

3.1. Begriffserklärung

Moderne Forschung in den naturwissenschaftlichen Fächern, wie Biologie, Genetik und Chemie, findet in immer höheren Maße unter Einsatz von Computern statt. Die Bioinformatik führt die beiden Disziplinen Informationstechnik und Molekularbiologie zusammen und beschäftigt sich mit der Erfassung, Speicherung, Bearbeitung und Verbreitung biologischer Daten (Biodaten) mittels elektronischer Hilfsmittel.

In [LG01] wird Bioinformatik definiert als:

conceptualising biology in terms of molecules (in sense of physical chemistry) and applying “informatics techniques” (derives from disciplines such as applied maths, computer science and statistics) to understand and organise the information associated with these molecules, on a large scale. In short, bioinformatics is a management information system for molecular biology and has many practical applications.

3.2. Einsatzgebiete

Die Haupteinsatzgebiete der Bioinformatik sind:

Sequenzanalyse

Die Sequenzanalyse beschäftigt sich mit der Sequenzzierung der Gene, also das mit neuartigen Laborautomaten durchgeführte Ablesen des Genoms und der Bestimmung der Bedeutung bzw. der Funktion dieser Sequenz (Abfolge der Basen).

Ein Problem welches bei der Sequenzzierung auftritt ist, dass die Gene zu lang sind um an einem Stück sequenziert zu werden. Deshalb werden die Gene in kleineren Stücken analysiert und später wieder zu größeren Abschnitten zusammengefasst.

Strukturanalyse, Molecular Modelling

Bei der Strukturanalyse soll die räumliche Struktur von Proteinen bestimmt werden und der Faltungsprozess analysiert werden.

Ein verwandtes Gebiet ist das Drug Design, bei der mit Hilfe von Computern neue Medikamente entwickelt werden. Es wird versucht den Zusammenhang von Struktur und Funktion einer Sequenz auszunutzen.

Expressionsdatenanalyse

Die vollständige Kenntnis eines Genoms ist wünschenswert, aber unzureichend. Die Expressionsanalyse analysiert die wechselseitige Beziehung bzw. das Zusammenspiel der Gene, um genauere Kenntnisse über die Abläufe in der Zelle zu bekommen. Hierzu wird alle mRNA, die sich zu einem bestimmten Zeitpunkt in der Zelle befindet bestimmt und nach der Klonierung auf einen DNS – Chip aufgetragen. Es kommt somit zu einer quantitativen Bestimmung der mRNA aller in diesem Moment transkribierten Gene der Zelle, der jedoch, da natürlich viele Zellen auf einmal untersucht werden müssen (die sich z. B. in verschiedenen Stadien des Zellzyklus befinden können), immer nur einen Durchschnittswert ist.

3.3. Ziele

Die Ziele der Bioinformatik sind nach [LG01] folgende

Organisation der Daten

Die biologischen Daten sollen so organisiert werden, so dass Forscher einen einfachen Zugang zu den existierenden Daten haben und neue Ergebnisse einfach übermittelt werden können. Dazu ist der Aufbau einfacher Datenbanken nötig, die von jedem Wissenschaftler ohne größere Probleme genutzt werden können.

Entwicklung von Systemen

Diese Systeme soll die Analyse der gespeicherten Daten durchführen und vereinfachen. Um solche Systeme zu entwickeln, müssen Fachkräfte in beiden Gebieten gut zusammenarbeiten und Grundwissen von dem jeweils anderen Gebiet haben.

Einsatz der Systeme

Mit den entwickelten Systeme sollen die Daten aus biologischer Sicht analysiert und interpretiert werden.

Um diese drei Ziele zu erreichen, können Ansätze des Data Mining angewendet werden.

3.4. Allgemeine Charakteristik von Biodaten

In den unschiedlichen Anwendungsbereichen der Bioinformatik entstehen eine Menge von Biodaten, die sehr unterschiedlich sind. Ein Überblick der verschiedenen Datenquellen wird in [LG01] gegeben und dient bei dieser Aufstellung als Grundlage.

DNA-Rohdaten (engl. Raw DNA sequence)

DNA Sequenzen sind eine lineare Abfolge kleiner molekularer Baueinheiten, die sogenannten Basen die mit den Buchstaben A, C, G und T (für die vier Nukleotide Adenin, Cytosin, Guanin und Thymin) bezeichnet werden. In den Datenbanken sind diese Sequenzen als Zeichenketten abgelegt, die eine typische Länge von 1000 Basen haben.

Protein Sequenzen

Die Grundbausteine der Proteine sind 20 Aminosäuren, die mit den Buchstaben A, C, D, E, F, G, H, I, K, L, M, N, P, Q, R, S, T, V, W und Y bezeichnet werden. Diese Aminosäuren werden durch eine Dreierfolge von Nukleotiden kodiert. Die Proteinsequenzen sind die lineare Abfolgen dieser 20 Aminosäuren und haben eine typische Länge von 300 Zeichen.

Makromolekulare Strukturen

Makromolekulare Strukturen sind eine komplexere Form der Information und geben die Struktur eines Proteins wieder. Eine typische Datei für so eine Struktur enthält die xyz-Koordinaten von rund 2000 Atomen.

Genome

Unter einem Genom versteht man das gesamte Erbmaterial eines Organismus. So besteht das menschliche Genom aus 46 langen DNA-Molekülen, den sogenannten Chromosomen. Jedes Chromosom besteht aus einem DNA-Doppelstrang und die Bausteine der Chromosomen sind vier Nukleotide. Die Größe des Genom hängt von dem Organismus, so hat das Genom des Menschen 3 Milliarden Basenpaare und das Genom von Haemophilus influenzea hat nur 1.6 Milliarden Basenpaare.

Genexpressionsdaten

Diese Daten entstehen bei der Genexpression und enthalten Informationen, welche Gene transkripiert sind.

Metabolische und regulatorische Pathways

Ein metabolischer Pfad ist eine abstrakte Darstellung eines Stoffwechselprozesses. Er gibt die Abfolge der Reaktionen beim Stoffwechsel wieder und listet die daran beteiligten Proteine und Moleküle auf.

Die regulatorischen Pfade übernehmen dabei die Steuerungsvorgänge und die interzelluläre Kommunikation.

Medizinische Daten/Versuchsreihen

Auch im Krankenhaus entstehen auch sehr viele Daten. So werden eine Menge an Daten über verschiedene Krankheiten und ihrer Behandlung gespeichert, aber auch Daten über Medikamente und deren Wirkung.

Literatur

Eine wichtige Quelle für die Forscher sind die Publikationen andere Forschungsteams. Die Abstracts dieser Publikationen werden auch in verschiedenen Datenbanken gespeichert und dienen als Vorwissen für eigene Versuche, um so neue Erkenntnisse ableiten zu können.

Tabelle 1 gibt eine kurzen Überblick in welchen Datenbanken die verschiedenen Biodaten gespeichert sind und deren Datenmengen.

Datenquellen	Datenbank	Datenmenge
DNA Sequenzen	GenBank EMBL	15.465.000 Sequenzen (Feb. 02) 16.244.527 Sequenzen (März 02)
Protein Sequenzen	PIR-PSD SWISS-PROT	283.153 Einträge (März 02) 105.967 Einträge (März 02)
Makromelekulare Strukturen	PDB	4500 Einträge (Feb. 95)
Genom	ECD MGD
Genexpression	dbEST
Metabolische Pfade	KEGG WIT2
Literatur	PubMed

Tabelle 1: Datentypenübersicht mit wichtigen Datenbanken

Das Wachstum der biologischen Daten ist exponentiell. Waren im Jahr 1982 nur 606 Sequenzen mit 680338 Basenpaaren in der Datenbank GenBank gespeichert so sind das im Jahre 1990 schon 39533 Sequenzen (49179285 Basenpaare) und im Jahr 2001 sogar schon 14976310 Sequenzen (15849921438 Basenpaare). Dieses exponentiell Wachstum ist in Abbildung 3.1und 3.2 noch einmal graphisch an zwei verschiedenen Datenbanken dargestellt.

4. Data Mining an ausgewählten Bereichen der Bioinformatik

Wie in dem letzten Abschnitt gezeigt, gibt es sehr unterschiedliche Biodaten. Diese Biodaten sind sehr heterogen. Um aus diesen riesigen Mengen an Daten neue Informationen zu gewinnen, werden Ansätze des induktiven Lernens (Entdeckung neuer Zusammenhänge in großen Datenbeständen) angewendet. Dem induktiven Lernen sind die Data Mining Systeme zugeordnet.

In diesem Abschnitt werden an ausgewählten Datentypen der Bioinformatik Ansätze des Data Mining aufgezeigt. Im ersten Abschnitt dieses Kapitels geht es um die Daten, welche in verschiedenen Versuchsreihen gewonnen wurden. Dabei möchte man aus diesen Daten sogenannte biologische Marker oder Biomarker gewinnen. Im zweiten Abschnitt geht es um die DNA Sequenzen und im dritten Abschnitt um die Proteinsequenzen.

4.1. Biomarker Discovery

4.1.1. Definition

Nach [TS00] wird ein Biomarker (oder biologischer Marker) definiert als:

A charakteristic that is objectively measured and evaluated as an indicator of normal biological processes, pathogenic processes or pharmacological responses to therapeutic intervention.

Ein Biomarker ist also ein Merkmal welches von einem Organismus gemessen werden kann und anzeigt, dass die biologischen und chemischen Prozesse „normal“ ablaufen. Normal in diesem Fall heißt, dass alle biologischen Prozesse für einen gesunden Organismus gemessen werde.

Biomarker können also als Indikator für eine Krankheit benutzt werden. Mit Hilfe dieser Indikatoren kann überprüft werden, ob ein Patient eine bestimmte Krankheit hat. Die Biomarker liegen für ein bestimmtes Merkmal in einem konkreten Bereich, der anzeigt das der Patient gesund ist. Möchte man jetzt einen neuen Patienten überprüfen, so misst man die Werte des Patienten und vergleicht diese neuen Werte mit dem Biomarker. Weichen die Werte sehr stark voneinander ab, so ist das ein Anzeichen das der Patient diese Krankheit hat.

4.1.2. Anwendungsfälle

In der Medizin existieren eine Menge sehr gut bekannten Biomarkern. Dabei unterscheidet man zwischen einfachen und zusammengesetzten Biomarkern. Bei einfachen biologischen Markern betrachtet man nur ein Merkmal. Beispiel dafür ist der Cholesterinspiegel, welcher ein Biomarker für Herzkrankheiten ist. Je höher der Cholesterinspiegel ist, um so höher ist die Wahrscheinlichkeit an einer Herzkrankheit zu erkranken.

Ein weiterer Biomarker ist die Konzentration des Prostata Specific Antigen (PSA) im Blut. Eine hohe Konzentration deutet auf Prostatakrebs hin. Dabei sei noch ein mal drauf hin gewiesen, dass ein Patient diese Krankheit aber nicht unbedingt haben muss. Die Konzentration ist nur ein Indikator für diese Krankheit, in anderen Worten, sie korrelieren mit der Krankheit.

Die bis jetzt aufgezählten Biomarker waren alle einfache Biomarker, also wo nur ein Wert einen biologischen Marker bestimmt. Heutige Biomarker bestehen meist aus einer Kombination von verschiedenen Indikatoren.

Ein Beispiel dafür, ist das Verhältnis zwischen T-Zellen und Gesamtanzahl der weißen Blutkörperchen, welcher ein Biomarker für Asthma ist.

Diese zusammengesetzten Marker sind meist bessere Indikatoren für eine Krankheit, als wenn sie separat genutzt werden.

4.1.3. Charakteristik der Daten

In klinischen Studien und Versuchsreihen über Krankheiten oder Medikamente sammelt man eine Reihe von Daten. Dieses Daten können Stammdaten des Patienten sein, wie Alter, Größe, Gewicht, Raucher. Aber der größte Teil der Daten sind Messungen verschiedener Werte des Patienten, wie Blut- und Urinwerte oder Konzentration verschiedener Stoffe im Blut. Diese Daten werden alle in einer Datenbank abgespeichert und müssen im Anschluss ausgewertet werden.

Dabei unterscheiden sich diese Datensätze sehr von „normale“ Datensätzen, wie sie zum Beispiel in der Wirtschaft auftreten. In diesem Zusammenhang spricht man von „breiten“ Datensätzen. Solch ein „breiter“ Datensatz zeigt Abbildung 4.1.

Observation	clinicalCls	m1	m2	…	m20000
1	Asthma			…
. . .	. . .	. . .	. . .	…	. . .
200	Healthy			…

Abbildung 4.1: breiter Datensatz (nach [HU01])

In diesem Datensatz befindet sich in der ersten Spalte die Anzahl der Beobachtungen, in der zweiten Spalte die beobachteten Krankheiten und in den weiteren Spalten die einzelnen Fakten dieser Krankheiten. Die Fakten bestehen zum großen Teil aus medizinischen Messungen, die stattgefunden haben. Die Spalten werden in diesem Artikel ([HU01]) als Dimensionen bezeichnet.

Es ist ersichtlich, dass die Anzahl der Messungen viel größer ist, als die Anzahl der Beobachtungen. So ist in der Abbildung die Anzahl der Messungen 100 mal größer als die Anzahl der Beobachtungen. Dies ist ein typischer Datensatz für dieses Einsatzgebiet der Bioinformatik. Denn in einer Studie sind meist nur wenige Patienten vertreten, aber die Anzahl der Messungen die im Verlauf der Studie vorgenommen werden sind enorm.

Ganz im Gegensatz zu „normalen“ Datensätzen, wie sie zum Beispiel im Bankwesen auftreten. Dort ist diese Beziehung gerade umgekehrt. So sammelt eine Bank verschiedene Daten über ihre Kunden. Wie zum Beispiel Name, Alter Anschrift usw., aber die Anzahl dieser Attribute ist viel kleiner als die Anzahl der Kunden, die eine Bank hat.

Ein Datensatz für das Finden von biologischen Markern ist sehr hochdimensional. Das bedeutet er hat sehr viele Attribute (Spalten). Aber warum ist die Anzahl der Messungen eigentlich so hoch? Dafür gibt es mehrere Gründe. Erstens bestehen gute Biomarker aus einer Kombination von Merkmalen, wie im Beispiel oben gezeigt. Beim Finden von Biomarker muss man eine maximale Größe der Kombination geben. Bei heutigen Rechnerleistungen liegt diese Grenze ca. bei 3 Messungen pro Kombination, denn sonst steigt der Rechenaufwand ins astronomische. Das zweite Problem bei der Identifikation von Biomarkern ist das wenige Wissen über biologische Prozesse. Man kann im Blut mehr als 10000 Proteine messen, wobei bei der Suche nach Biomarker aber nur ein paar wenige eine Rolle spielen. Aber man muss sie alle messen, denn sonst könnten gute Marker verloren gehen. Gute Kenntnisse über diese Prozesse würde die Dimensionsreduzierung wesentlich vereinfachen.

4.1.4. Verfahren zur Entdeckung des Biomarker

Um aus den „breiten“ Datensätzen Biomarker zu gewinnen, setzt man Methoden des Data Mining ein. In diesem Abschnitt wird ein Verfahren verwendet welches in [HU01] vorgestellt wird und ist in Abbildung 4.2 graphisch dargestellt.

Abbildung 4.2: SurroMed’s Data Mining Plattform für Biomarker Discovery (nach [HU01])

In einem ersten Schritt werden aus allen vorhandenen Messungen die relevanten Daten herausgefiltert, um eine kleine Einschränkung der zu durchsuchenden Daten zu bekommen. Diese Messungen werden die Trainingsmenge für den biologischen Marker, um aus ihnen einen Klassifizierer zu bilden. Dabei tritt aber bei diesen „breiten“ Datensatz ein Problem auf, denn der Datensatz ist zu hochdimensional. Das bedeutet, dass ein einzelnes Objekt aus dem Datensatz von einer sehr großen Menge an Merkmalen repräsentiert wird. Also ist ein weiterer Schritt die Dimensionsreduzierung der Daten, welches in Abbildung 4.3 schematisch dargestellt ist.

Abbildung 4.3: Dimensionsreduzierung (nach [HU01])

Dabei ist es wichtig zwischen Dimensionsreduzierung und Datenreduktion zu unterscheiden. Bildlich heißt Dimensionsreduzierung weglassen von Spalten einer Tabelle und Datenreduktion heißt weglassen von Zeilen in einer Tabelle. Für die Dimensionsreduzierung werden drei Möglichkeiten in [HU01] vorgestellt.

Merkmal Elimination

Bei der Merkmal Elimination wird die Dimension (Anzahl der Attribute) reduziert, indem „unwichtige“ Dimensionen aus dem Datensatz gelöscht werden.

Dabei wird eine Dimension eliminiert, wenn sie:

Irrelevant ist

Hier wird jede Dimension separat bewertet und eine Punktzahl gebildet, wie gut die Dimension zwischen zwei Klassen unterscheiden kann. Liegt der Punktwert unter einer vorgegebenen Grenze, wird sie gelöscht.

Redundant ist

Für die Redundanz wird jedes Dimensionspaar auf Ähnlichkeit bewertet und wenn die Ähnlichkeit zu groß ist, kann eine Dimension eliminiert werden. Dazu werden die Ähnlichkeitsalgorithmen BLAST oder FASTA verwendet.

Merkmal Synthese

Die Hauptidee dieser Methode ist es, die originalen Dimensionen, in neuere und weniger Dimensionen zu zerlegen. Dazu werden die aus der Mathmatik bekannten Verfahren PCA (Principal Component Analysis) oder PLS (Partial Least Square Regression) angewendet. Im Anschluss wird kurz auf das Verfahren PCA eingegangen.

Die zentrale Idee PCA ist eine Reduktion der Dimension einer Menge an Mustern, die aus einer großen Anzahl an untereinander unabhängigen Punkten im hochdimensionalen Raum besteht. Dabei soll möglichst wenig der durch die Muster gegebenen Varianz verloren gehen. Dies wird durch eine lineare Transformation auf eine neue Menge von Mustern erreicht, die paarweise unkorreliert sind. Zudem sind sie so geordnet, dass die ersten Variablen die größte Varianz aller ursprünglichen Variablen repräsentieren, diese heißen dann Hauptkomponenten.

Ein Beispiel in 3D ist auf den nächsten fünf Abbildungen dargestellt ([HB01]).

Man stelle sich folgende Ansammlung von Stichprobenelementen im dreidimensionalen Raum vor (Abbildung 4.4). Als erstes wird der Koordinatenursprung gemäß Richtung und Länge des Vektors c in den Schwerpunkt der Stichprobe (der Stichprobenmittelwert) verschoben (Abbildung 4.5). Als nächstes wird die X-Achse in Richtung der größten Varianz der Daten (im Abbildung 4.6 der hellblaue Pfeil) gedreht. Dann wird die Y-Achse mit der Richtung der zweitgrößten Varianz der Daten (im Abbildung 4.7 der gelbe Pfeil) in Übereinstimmung gebracht, indem um die bereits festgelegte X-Achse rotiert wird.

In höherdimensionalen Räumen würden nun noch d - 3 weitere, unabhängige Achsen verbleiben, die ebenfalls noch ausgerichtet würden. An diesem Beispiel ist aber schon erkennbar, dass nach dem Ausrichten der ersten beiden Achsen, der Informationsverlust beim Weglassen der dritten (hier z-)Achse, sehr viel geringer geworden ist.

Merkmal Selektion

Bei dieser Methode ist die Hauptidee aus den Dimensionen Untermengen zu erzeugen und mit diesen dann einen Klassifizierer zu bilden. Dabei spielen zwei Verfahren eine große Rollen. Das erste Verfahren ist SDA (Stepwise discriminant analysis) und das zweiten Verfahren ist die Cross-entropy-based Merkmals Elimination.

Der Algorithmus für SDA ist in Abbildung 4 dargestellt.

Abbildung 4.9:Stepwise discriminant analysis Algorithmus

Der Algorithmus startet mit der leeren Menge und versucht iterativ einen Kandidaten der Dimensionsuntermenge auszuwählen. In der Abbildung beschreibt F(S,v) eine Statistik, welche den Beitrag der Dimension v zur Gruppenunterscheidung in bezug auf dem Beitrag einer gegebenen Dimension S misst. Dabei ist M die Eingangsmenge der Dimensionen und in B steht dann die Untermenge der Dimensionen. Mit dieser Untermenge wird dann im weiteren Verlauf der Klassifizierer erzeugt.

Nach Anwendung einer der drei Möglichkeiten oder besser der Kombination der Verfahren, bekommt man einen Datensatz mit weniger Attributen. Mit diesen Daten kann man dann alle Kombinationen von Messungen bis zu einer gegebenen Länge analysieren und einen Klassifizierer bauen. Man zählt dabei die Fehler, die der Klassifizierer macht. Die beste Kombination, die die wenigsten Fehler gemacht hat, kann man dann als Biomarker auswählen.

Um aber einen Zusammenhang in den einzelnen Messungen aufzudecken wird mit der erzeugten Untermenge von guten Kombinationen wird die sogenannte Warenkorbanalyse durchführe n. Es wird versucht Kombinationen von Messungen zu finden, die häufig mit einer Krankheit auftreten. Die beste Kombination wird als Biomarker ausgewählt.

4.2. Gen Klassifikation

Ein weiteres Einsatzgebiet der Bioinformatik, ist die Analyse des menschlichen Genoms. Diese Aufgabe wurde von verschiedenen Gruppen aus der ganzen Welt durchgeführt. Die Daten, die diese Gruppen lieferten, waren meist kleine codierte Portionen in Form von Expressed Sequence Tags (EST), da diese leichter zu bestimmen sind, als die gesamte DNA Abfolge.

4.2.1. Charakteristik der Daten

Nach [SC99] sind Expressed Sequence Tags zufällig ausgewählte, partielle cDNA Sequenzen. Wobei cDNA für complemantary DNA steht und das Komplement der mRNA ist.

EST sind DNA Sequenzen und somit eine lineare Abfolge der 4 Nukleotide (Adenin, Cytosin, Guanin und Thymin) Ein Beispiel dafür ist in Abbildung 4.10 zu sehen.

Abbildung 4.10: Expressed Sequence Tag

Die Länge so einer Sequenz liegt in der Größenordnung von rund 1000 Basen In Datenbanken, wie dbEST oder GenBank werden die Sequenzen als Zeichenketten abgespeichert.

Diese Daten haben aber ein großes Problem, sie sind sehr redundant und haben hohe Fehlerraten. Das hängt zum ersten damit zusammen, dass diese Sequenzen von verschiedenen Gruppen gefunden wurden und zum zweiten mit den Verfahren wie diese Sequenzen erzeugt wurden. Beim Analysieren der DNA soll die Abfolge der Nukleotide bestimmt werden, dazu wird die DNA stückweise „abgelesen“. Doch je länger diese Sequenzen sind, um so höher sind die Fehler die dabei auftreten können.

Doch mit diesen Sequenzen allein kann man noch nichts anfangen, es müssen Verfahren angewendet werden, um in diesen Daten die versteckten Informationen zu finden. Mit diesem Problem beschäftigt sich der nächste Abschnitt.

4.2.2. Verfahren

Das Ziel ist es, mit Hilfe dieser Sequenzen, Bereiche in der DNA zu finden, die Gene codieren. Ein Gen ist ein bestimmter Teilabschnitt des Genom, der die Informationen für den Aufbau eines bestimmten Proteins enthält. Diese Abschnitte werden auch als codierende Regionen des Genom genannt. Daneben hat das Genom auch sogenannte nichtkodierende Regionen, die unter anderem die Übersetzung der Gene steuern, deren Rolle aber bis heute weniger gut verstanden ist. Ein zusätzliches Problem ergibt sich daraus, dass die kodierenden Bereiche nicht notwendigerweise verbunden sind.

Ein weiteres Ziel ist, aus den EST Datenbanken Gene zu finden, welche bei bestimmten Krankheitsgewebe up- oder down-reguliert sind. Man möchte also Gene finden, die bei bestimmten Krankheiten sehr häufig oder sehr selten in bestimmten Gewebeschichten vorkommen.

Hier wird exemplarisch das Verfahren nach [SC99] beschrieben. Der gesamte Ablauf ist in Abbildung 4.11 schematisch dargestellt.

Abbildung 4.11: Abfolge der Schritte nach [SC99]

In einem ersten Schritt werden alle redundanten EST eliminiert. Dazu wird das bekannte Ähnlichkeitsalgorithmus BLAST benutzt. BLAST ist ein Algorithmus dem eine Sequenz übergeben wird und durch Vergleiche eine Sequenz mit der größten Übereinstimmung gefunden wird.

In diesem Fall wird jede Sequenzen mit jeder anderen Sequenz verglichen. Wird dabei eine kürzere Sequenz gefunden, welche perfekt mit einer längeren Sequenz überein, wird das kürzere Stück eliminiert. Das Ergebnis ist eine Menge von nicht redundanten EST.

Im nächsten Schritt werden mit Hilfe einer iterativen Such- und Zusammenstezungssprozedur (AUTEX: a protocol for the automatic extension of partial DNA sequences) Sequenzen mit maximaler Länge erzeugt. Zu diesem Zweck wird eine Kern-Sequenz ausgewählt und mit Hilfe von BLAST homologe Sequenzen gesucht. Mittels multiplen Alignments wird werden die Sequenzen zusammengeführt. Die so erhaltene Sequenz ist der Ausgangspunkt für die weitere Suche. Diese Prozedur wird so lange durchgeführt, bis eine Sequenz mit maximaler Länge entsteht.

Im folgenden Schritt wird das sogenannte „Electronic Northern“ durchgeführt. Electronic Northern wird definiert als:

The use of an electronic database of cDNA sequences (or probes derived from them) in order to measure the relative levels of mRNAs expressed in different cells or tissues.

Es wird untersucht, ob die gefundenen Sequenzen zu einem bestimmten Gewebe (Gehirn, Brust, Dickdarm, Leber, Lunge, Prostata, Uterus und Eierstock) gehören. Das Ergebnis sind Gene, welche in einer bestimmten kranken Gewebeschicht häufiger vorkommen.

Im letzten Schritt wird eine statistische Evaluation der Sequenzen durchgeführt, um die Verteilung der Treffer zwischen normalen und kranken Gewebe zu beurteilen, welche bei der BLAST Suche beobachtet wurden. Dazu wird der bekannte statistische Test, der Fisher-Test, benutzt. Dazu wird der P-Wert des Fisher-Tests bestimmt, welcher die Richtigkeit der Nullhypothese „Die Verteilung eines Genes, ist die selbe in normalen und kranken Gewebe“ (nach [SC99]) bestimmt. Je näher der Signifikanz-Wert an 1,0 ist, umso mehr Beobachtungen stimmen mit der Nullhypothese überein. So wird die Zuordnung der Sequenzen zu einzelnen Krankheiten nochmals überprüft.

4.2.3. Ergebnisse

In [SC99] wurde anhand des oben beschriebenen Vorgehen eine Fallstudie an einem CGAP Datensatz (NCI_CGAP_Br1.1) vorgenommen.

Als Ergebnis lieferte [SC99] ein Klassifikationsschema für diesen Datensatz, welches in Abbildung 4.12 dargestellt ist.

Abbildung 4.12: Klassifikations Schema für den Grad von verschiedenen Expression für die Fallstudie

In dieser Tabelle werden die unterschiedlichen Stufen von Expressionen und die Auflistung aller Fälle von Expressionen, die bei dieser Studie gefundenen wurden, ersichtlich.

Zwei unabhängige Kriterien (Expressionsrate und P-Wert des Fisher-Test) wurde benutzt um die Stufen der Gen Expression einzuteilen. Diese wurden vor Beginn des Experimentes festgelegt. Ein Gen wurde in eine Klasse eingeordnet, wenn die jeweils die beide gemessen Kriterien mit der dritten und vierten Spalte übereinstimmen. Ein kleines Beispiel wäre: für ein Gen wird eine Expressionsrate von 12 und eine P-Wert von 0,0005 ermittelt. Diese beiden Werte erfüllen die Kriterien in der zweiten Zeile der Tabelle und so fällt das Gen in Klasse I.

Diese Einordnung in verschiedene Klassen wird für Gene durchgeführt, über die schon eine Menge an Wissen gesammelt wurde. Mit Hilfe dieser Klassifikation können für neu entdeckte Gene daraus Rückschlüsse gezogen werden. So wurden verschiedene Gene, die mit Tumoren in Verbindung stehen, bei diesen Verfahren meist in die Klassen II und III eingeordnet. Fällt ein neues Gen jetzt auch in einer dieser Klassen, ist dies eine Hinweis, dass dieses Gen auch mit einem Tumor in Verbindung steht.

4.3. Protein Klassifikation

Der Wissenschaft gelang den genetischen Code zu erkennen, mit dem die Basenpaare eines Genes in die Grundbausteine der Proteine (Aminosäuren) übersetzt werden. So wird eine Aminosäure durch eine Dreierfolge von Nukleotiden kodiert.

Die entdeckten Gene der Gen Klassifikation werden mit diesem genetischen Code in die Aminosäuren übersetzt und als Ergebnis entsteht eine Proteinsequenz, aus der im weiteren Verlauf weitere Informationen gewonnen werden.

4.3.1. Charakteristik der Daten

Proteine bilden den Hauptbestandteil jeder Zelle (bis zu 50% der trockenen Masse). Sie formen die wichtigsten Strukturelemente der Zelle und besitzen eine Schlüsselrolle bei fast allen intra- und interzellulären Prozessen. Proteine sind unverzweigte Kettenmoleküle (Polymere), die aus 20 Bausteinen, den sogenannten Aminosäuren, aufgebaut sind. Wie die DNS sind auch Proteine lange molekulare Ketten, die aus bis zu mehreren hundert Aminosäuren bestehen. Diese Ketten falten sich spontan oder im Beisein von Helferproteinen in einer eindeutigen Art und Weise. Die dadurch erhaltene Raumstruktur des Proteins bildet die Grundlage für seine Funktion.

Abgespeichert sind die Proteine als lineare Abfolge über dem Alphabet {A, R, N, D, C, E, Q, G, H, I, L, K, M, F, P, S, T, W, Y, V}. Wobei es sich bei den Buchstaben um die 20 Aminosäuren handelt.

Diese Sequenzen sind in verschiedenen Datenbanken abgelegt. Die wichtigsten Datenbanken sind SWISSPROT und PIR. So liefert zum Beispiel die Suche nach Lektinen in einer Datenbank die Daten, die in Abbildung 4.13 dargestellt sind.

Abbildung 4.13: Ergebnis bei der Abfrage von Lektinen ([LE01])

In jeder Zeile ist eine Sequenz eines Lektines abgebildet. Die erste Zeile zeigt zum Beispiel das einfachste Lektin, das Hevein. Ein wichtiges Strukturelement der Lektine sind die Cysteine, welche hier mit gelben Balken markiert sind, sie bilden vier Schwefelbrücken aus.

Diesen Zeichenketten können auch Lücken aufweisen, was in der Abbildung durch Striche gekennzeichnet ist. Diese Lücken kennzeichnen Stücke, die nicht eindeutig bestimmt werden konnte.

Mit Hilfe dieser Sequenzen soll die Struktur der Proteine bestimmen werden. Denn die 3-dimensionale Gestalt der Proteine bestimmt ihre Funktion. Um schwierige Laboruntersuchungen zu vermeiden, werden Informatikmethoden zur Proteinfaltung eingesetzt, die die Struktur eines Proteins aus seiner Aminosäuresequenz ermitteln. Dabei unterscheidet man die Primär-, Sekundär-, Tertiär- und Quartärstrukturen. Die Primärstruktur ist die Aminosäuresequenz, die Sekundärstruktur ist eine Abstraktion der 3-dimensionalen Gestalt in Form von lokalen Faltungsmustern, die Tertiärstruktur ist die 3-dimensionale Gestalt von Proteinuntereinheiten und die Quartärstruktur gibt wieder, wie sich die verschiedenen Untereinheiten eines Proteins räumlich zusammenlagern.

Abbildung 4.14: Struktur des Hevein

4.3.2. Verfahren

In diesem Abschnitt wird ein Verfahren vorgestellt mit dem große Proteinmengen in Untermengen aufteilen kann, welche funktionell abhängig sind.

Aus diesen Unterklassen kann man dann Rückschlüsse von Funktion und Struktur neu entdeckter Gene gewinnen. Fallen zwei Proteine in die gleiche Unterklassen haben sie ähnliche Funktionen, also auch eine ähnliche Struktur

Dieses Verfahren heißt SPLASH und ist ein Muster Discovery Algorithmus und beruht auf Top-Down Clustering. Das Ziel ist die Entdeckung biologisch signifikante Motifs in den Daten. Motifs sind kurze Sequenzen die häufig und wiederholt auftreten und vergleichbar mit regulären Ausdrücken.

Das Grundprinzip des Verfahren, welches in Abbildung 4.15 dargestellt ist, ist es eine Superfamilie P in zwei Untermengen:

P1, Sequenzen die das Motif haben
P0, Sequenzen die das Motif nicht haben

zu teilen.

Abbildung 4.15: Superfamilie mit funktionalen Subfamilien (nach [LC01])

Der Algorithmus läuft nach dem Prinzip ab, wie er in Abbildung 4.16 dargestellt ist.

Abbildung 4.16: Ablauf von SPLASH nach IB02

Ausgangspunkt des Algorithmus ist eine Menge P von Proteinsequenzen. Die Mustersuche läuft iterativ ab. Als erstes werden die Standardwerte für die Beschränkung benutzt und mit dieser Belegung die Suche nach einem Motif durchgeführt. Wird kein Motif gefunden, werden die Werte geändert bis ein Motif gefunden wird. Werden mehrere Motifs gefunden, wird das Motif mit der größten Signifikanz ausgewählt. Mit diesem gefundenen Muster wird die Menge P in zwei Untermengen aufgeteilt. In eine Menge Pi0, in der das Motiv übereinstimmt und eine Menge Pi1, wo es keine Übereinstimmung mit dem Muster gibt. Diese Prozedur wird für jeden neuen Knoten so lange durchgeführt bis eine benutzerdefinierte maximale Anzahl von Motifs gefunden wurde oder eine vorher festgelegte untere Schranke bei den zu verändernden Werte erreicht wurde.

Als Ergebnis erhält man einen binären Baum, der im nächsten Schritt ausgewertet werden kann. Zu nennen sind dafür die Hidden Markov Modelle (HMM).

4.3.3. Ergebnisse

Nach dem Aufbau des Baumes kann man mit einem unbekanntes Protein diese Klassifikation durchführen bis ein Blatt erreicht wurde. Mittels Vergleiche mit bekannten Proteinen der Untermenge, kann man auf die Funktion und Struktur des unbekannten Proteins schließen.

5. Zusammenfassung

Die Bioinformatik erzeugt in ihren verschiedenen Einsatzgebieten eine riesige Menge sehr unterschiedlicher Daten. Doch Daten sind nicht gleichzusetzen mit neuen Informationen. Um Informationen zu gewinnen können unterschiedliche Ansätze benutzt werden. Eine Möglichkeit ist der Einsatz von Data Mining Verfahren.

Doch es gibt keine allgemeine Lösung für das Data Mining in Biodaten. Jeder Datentyp verlangt seine eigene Strategie.

Vor einigen Monaten wurde die gesamte Abfolge der menschlichen DNA entschlüsselt. Aber die Verfügbarkeit des Genoms eines Organismus bildet nur die prinzipielle Grundlage für ein vollständiges Verstehen der molekularen Bestandteile und Prozesse dieses Lebewesens. Es muss im einzelnen jedoch aufgeklärt werden, wie der Organismus die genomische Information interpretiert. Hier befindet sich der wichtigste Ansatzpunkt für das Data Mining.

Mit Hilfe der einzelnen DNA Sequenzen werden Gene entdeckt, die die Informationen zum Aufbau der Proteine enthält. Weiterhin kann durch Mustersuche, die Struktur der Proteine bestimmt werden, welche sehr großen Einfluss auf die Funktion der Proteine hat. Durch Vergleiche der Struktur der Proteine kann man auch Rückschlüsse auf genetische Abstammung von Lebewesen gewinnen.

Dieses Forschungsgebiet befindet sich aber noch im Anfangsstadium. Es gibt für die einzelnen Datentypen speziell entwickelte Algorithmen, die versteckte Informationen finden können. Aber für die Anwendung dieser Werkzeuge braucht man das nötige Fachwissen. Erste Ansätze für ein System, welches die Data Mining Ansätze durchführt wird in [LI01] vorgestellt.

6. Quellen

TS00 Tsur,S.: Data Mining in the Bioinformatics Domain; Proc. 26. Intl. Conf.on VLDB, 2000

HU01 Huyn, N.: Data Analysis and Mining in the Life Sciences; SIGMOD Record 30(3), 2000

LC01 Liu, A., Califano, A.: Functional Classification of Proteins by Pattern Discovery and Top-Down Clustering of Primary Sequences; IBM System Journal, 40(2), 2001

SC99 Schmitt et al.: Exhaustive mining of EST liraries for genes differentially expressed in normal and tumour tissues; Nucleic Acids Research, Vol. 27, Nr. 21, 1999

LG01 Luscombe, N., Greenbaum, D.,Gerstein, M.: What is bioinformatic? An introduction and overview; IMIA 2001 Yearbook, 2001

LI01 Lee, C., Irizarry, K.: The GeneMine system for genom/protenome annotation and collaborative data mining; IBM System Journal, 40(2), 2001

OB00 Oberlé, V.: Data Mining: eine Einführung; 2000

http://vincent.oberle.com/data-mining.pdf

ST01 Schmitt-Thieme, L.: Web Mining; Skript für das WS ½

http://viror.wiwi.uni-karlsruhe.de/webmining/

LE01 Lengauer, T.: Bioinformatik : Einführung und Arbeiten an der GMD

http://web.informatik.uni-bonn.de/FGL/_vorl_ws9899z/bioinf.html

HB01 Hein, E., Becker, C.: PCA

http://www.digimusik.de/PCA/

LE01 Lenhof, H.: Vorlesung Bioinformatik

http://www.zbi.uni-saarland.de/zbi/stud/lehrveranstaltungen/ws01/bioinformatikI/materialien/BioinfI3.pdf

IB02 IBM Website zu SPLASH

http://research.ibm.com/splash/