Genomweite Assoziationsstudie - ein Ausflug in die Bioinformatik
Vor kurzem habe ich mich im Rahmen eines Wettbewerbs der Webseite Innocentive, mit der Lösung eines Problems aus der Bioinformatik befasst. Auch wenn ich bisher keinerlei Erfahrung mit Anwendungen aus der Bioinformatik hatte, und leider nicht genug Zeit mich hinreichend damit zu befassen, so war das ganze dennoch sehr lehrreich. Es sollte aus unvollständigen Informationen über das Genom von 100 Individuen einer Maispflanze, ein möglichst gutes Regressionsmodell entwickelt werden, mit dem man möglichst genau vorhersagen kann wie stark sich eine bestimmte Eigenschaft der Maispflanze ausprägen wird. Eine Gelegenheit, ein paar Algorithmen wie Neuronale Netze, Decision Trees, Random Forest, K-Means Clustering und SVMs auf ein Regressionsproblem mit wirklich vielen unabhängigen Eigenschaften, aber leider (zu) wenig Datensätzen loszulassen.
Inhaltsverzeichnis |
Die Aufgabe
Die Herausforderung auf Innocentive läuft unter dem Titel Predictive Data Analysis - dem Gewinner winken 100.000 US Dollar Preisgeld, daher arbeiten wie es scheint auch einige echte Koriphäen daran.
Die Aufgabe besteht darin, ein neuartiges und überlegenes Verfahren für ein Problem zu entwickeln, was in Fachkreisen als Genomweite Assoziationsstudie (bzw. Genome wide association study) bekannt ist.
In diesem Fall lagen für 250 individuelle Maispflanzen Informationen aus deren Genom vor - Von 32.000 bekannten Genen ist bekannt, wie stark diese ausgeprägt sind, und für 6.000.000 Basenpaare der vollständigen DNS liegt vor, ob diese sich vom Referenzgenom des Mais unterscheiden. Diese Unterschiede in den Basenpaaren nennen sich dann "Single Nucleotide Polymorphisms" oder kurz SNPs.
Der Trainingsdatensatz besteht dabei aus 100 dieser 250 Individuen. Für diese 100 Individuen liegt die Information vor, wie stark sie eine gewisse Zieleigenschaft ausgeprägt haben. Welche Eigenschaft das ist, wird im Rahmen des Wettbewerbs nicht verraten, es könnte z.B. die Grösse, Gewicht, Stärkegehalt, Resistenz gegen ein Herbizid oder ähnliches sein.
Einfach gesagt, besteht die Aufgabe jetzt daraus, ein Verfahren zu entwickeln was aus den vorliegenden Informationen der 100 Trainingsdatensätze möglichst Allgemeingültig und korrekt vorherzusagen wie stark sich die Zieleigenschaft ausprägen wird. Der Haken an der Sache ist jedoch, dass dieses Verfahren an 150 anderen Mais-Individuen (den Testdatensätzen) geprüft wird.
Über ein auf Innocentive.com eingebautes Online-Tool namens Predator kann man die Qualität des eigenen Regressionsmodells sehr schnell bewerten indem man diese Testdatensätze in eine Rangfolge nach Stärke der vorhergesagten Eigenschaftsausprägung bringt, und die Reihenfolge einsendet. Innerhalb von Sekunden wird ein Spearman Rang Koeffizient berechnet der angibt, wie gut die eigene Lösung ist.
Um Manipulation vorzubeugen, wurde diese Bewertungsmethode allerdings eingeschränkt hinsichtlich der Anzahl der täglichen Einsendungen. Darüber hinaus müssen die besten Verfahren im Anschluss noch ihre Fähigkeiten an völlig unabhängigen Testdaten beweisen.
Die Herausforderungen
Wer jetzt denkt, das wäre einfach, man müsse einfach nur ein paar (oder ein paar hundert) stark mit der Zieleigenschaft korrelierende Eigenschaften finden und aufgrund dieser dann sein Modell trainieren, der täuscht sich. Die Zusammenhänge und das Zusammenspiel der verschiedenen Eigenschaften sind durchaus komplex.
Fehlende Daten / Imputationsverfahren
Die Daten sind unvollständig und potentiell Fehlerbehaftet. Für viele der möglichen Nukleotid-Differenzen liegen bei einzelnen Individuen gar keine, oder nur unscharfe Daten vor. Aus diesem Grund scheint es notwendig, eine sogenannte Imputation fehlender Daten durchzuführen. Dabei wird die Tatsache ausgenutzt, dass die Individuen ja durchaus miteinander verwandt sind, oder sein können, um fehlende informationen von verwandten Individuen abzuleiten. Wäre dies nicht der Fall, würde man dadurch keinen Nennenswerten Informationsgewinn für andere Klassifikatoren erhalten.
Ein einfaches Verfahren was dabei gerne eingesetzt wird ist das bekannte K-Means Clustering, welches global eingesetzt wird um zu jedem Individuum die K-ähnlichsten Individuen zu finden, und aus ihren Eigenschaften Mittelwerte zu bilden die dann verwendet werden.
Ein besseres Verfahren ist jedoch, ein "lokales" Clustering - d.h. für jede zu schätzende Position auf dem Genom, wird für alle anderen Individuen die Ähnlichkeit *im Umfeld* dieser Position bestimmt. Auf Basis dieser Daten kann eine genauere Imputation der Daten erfolgen, da dadurch konkret eine Wahrscheinlichkeit ermittelt werden kann welche anderen Individuen über Erbgänge eben die gleiche Eigenschaft an dieser Position geerbt haben.
Eine weitere Unsicherheit die hinzukommt, ist dass bei den SNPs nicht bekannt ist, inwiefern ein Basenpaar vom Referenzgenom abweicht, nur ob es dies tut. In diesem Zusammenhang ist es also möglich, dass zwei Individuen an der gleichen Stelle im Genom einen Unterschied zum Referenzgenom aufweisen, allerdings einen *anderen* Unterschied. Mittels lokalem Clustering kann auch diese Wahrscheinlichkeit bestimmt werden, und so eine statistische Disambiguierung durchgeführt werden.
Mehr zu diesem Imputationsverfahren findet sich u.A. in der Studie Browning SR, Browning BL. Rapid and accurate haplotype phasing and missing-data inference for whole-genome association studies by use of localized haplotype clustering. Am J Hum Genet. 2007 Nov;81(5):1084-97 Komplettes PDF
Lösungsansätze
Ohne Imputation der fehlenden Daten ist es nahezu unmöglich, in die Top-Ten der Rangliste auf Innocentive.com zu diesem Problem vorzudringen. Ein SVM basierender Regressionsansatz mit linearem Kernel (bei so vielen Eigenschaften braucht man nicht *noch mehr* Dimensionen) den ich auf Basis einer Selektion von Nicht-Imputierten Daten erstellt habe, hat es immerhin auf Platz 24 der Rangliste des Wettbewerbs geschafft. Bei insgesamt über 1700 Teilnehmern, und dafür dass ich nicht viel Zeit hineingesteckt habe, nicht schlecht denke ich.
Weitere von mir erdachte Ansätze involvierten eine Variante des Random Forest Verfahrens, bei dem jedoch statt einzelner Decision Trees, Neuronale Netzwerke zum Einsatz kommen sollten. Darüber hinaus habe ich es mit einem Decision Tree versucht, der in jeder Node bis zu 500 Kriterien verwendete um die Daten zu segmentieren. Die Eigenschaften nach denen getrennt wurde, sowie die Schwellwerte wurden dabei nach maximaler Korrelation mit der Zielvariable, und maximaler Entropiereduktion in den Unterknoten ausgewählt. Beim durchlaufen des Trees, wurden immer alle Pfade verfolgt, wobei für jeden Knoten anhand des Bayes Satz die Wahrscheinlichkeit bestimmt wurde dass das entsprechende Individuum tatsächlich in diesen Knoten gehört.
Eine Interpretation dieser Ergebnisse konnte dann durch Mittelwertbildung, oder ein anschliessendes Neuronales Netz erfolgen. Dabei sollte als Eingabe für das anschliessende Neuronale Netz (MLP) die "aktivierung" jeder Node des Decision Trees, sowie ein Vektor mit Pearson-Distanzen zu den allen 100 Individuen des Testdatensatzes verwendet werden. Auf diese Art und Weise - so mein Plan - würde das Neuronale Netz sowohl die spezifischen Unterschiede der Individuen, als auch die Ähnlichkeit in seine Ergebnisse einbeziehen können. Durch die hohe Anzahl von Kriterien bei der Auswertung des Decision Trees, wäre es zudem robust gegenüber fehlenden Daten. Durch diese beiden Eigenschaften könnte das System ohne ein Imputationsverfahren auskommen.
Beim Testen dieser Verfahren hat sich wieder einmal erwiesen, wie wichtig Cross-Validation ist - denn es war viel zu leicht, ein Modell zu entwickeln welches völlig überangepasst war. Das wirkliche Problem allerdings war, dass die Verfahren - selbst wenn sie mit Cross-Validation auf die Trainingsdaten ein sehr gutes Ergebnis erzielten - nicht gut für die Testdatensätze generalisierten. Daraus kann ich nur folgern, dass die Individuen aus dem Testdatensatz weniger eng mit den Trainings-Individuen verwandt waren, als diese untereinander.
Ich bin daher zum Schluss gelangt, dass man schon ein lokales Imputationsverfahren benötigt um verwandtschaftliche Feinheiten berücksichtigen zu können, und zwingend auch eine Disambiguierung der SNPs durchführen muss um zu konkurrenzfähigen Ergebnissen in der Regressionsanalyse zu kommenen.
Momentan fehlt mir die Zeit um all die Ideen dich ich zu diesem Thema habe auszuprobieren, aber ich denke auch ohne die 100.000 USD Preisgeld halte ich das Thema für interessant genug um sich demnächst noch weiter damit zu beschäftigen.