Quo Vadis: Algorithmen

Kochrezepte hin zur Haute Cuisine für Computer

  • Abb. 1: Suffixbaum für zwei Zeichenketten A und B. Im Baum sind alle Suffixe (Endungen) eingetragen, die in A und B vorkommen, vergleiche die Markierungen unter A: CCGCCT und B: CGCG. Die Bläter des Baumes geben den Beginn der Suffixe an. Die Wurzel des Baumes ist rot und der Pfad, der zum gemeinsamen Teilwort CGC gehört, ist orange markiert.Abb. 1: Suffixbaum für zwei Zeichenketten A und B. Im Baum sind alle Suffixe (Endungen) eingetragen, die in A und B vorkommen, vergleiche die Markierungen unter A: CCGCCT und B: CGCG. Die Bläter des Baumes geben den Beginn der Suffixe an. Die Wurzel des Baumes ist rot und der Pfad, der zum gemeinsamen Teilwort CGC gehört, ist orange markiert.
  • Abb. 1: Suffixbaum für zwei Zeichenketten A und B. Im Baum sind alle Suffixe (Endungen) eingetragen, die in A und B vorkommen, vergleiche die Markierungen unter A: CCGCCT und B: CGCG. Die Bläter des Baumes geben den Beginn der Suffixe an. Die Wurzel des Baumes ist rot und der Pfad, der zum gemeinsamen Teilwort CGC gehört, ist orange markiert.
  • © Prof. R. Merkl
  • Abb. 2: Prinzip von korrelierten Mutationen. Links sind intramolekulare Interaktionen dargestellt; die kompensierenden Mutationen treten an zwei räumlich benachbarten Positionen i und j des Proteins 1 auf. Rechts sind intermolekularen Interaktionen veranschaulicht. Sie betreffen zwei Positionen k und l, die zu zwei verschiedenen Proteinen (Protein 1 und Protein 2) gehören und im Interface eines Proteinkomplexes liegen. Eine Voraussetzung für den sicheren Nachweis korrelierter Mutationen ist die Analyse einer großen Anzahl homologer Sequenzen (seq1–seqn), die zu ­einem multiplen Alignment zusammengefasst sind.
  • Dr. R. Merkl

 

Rainer Merkl
 
Algorithmen sind Berechnungsverfahren, die  übersetzt in Programme der Computer-Hardware vorschreiben, wie gewisse Aufgaben zu lösen sind. Die in den letzten Jahren stetig erzielten Fortschritte in der Vorhersagequalität sind vor allem auf präzisere Modelle, die Akkumulation von Wissen aus den Anwendungsbereichen und die Zunahme der Rechenleistung zurückzuführen. Von besonderer Bedeutung für die Biowissenschaften sind sequenz- und strukturbasierte Algorithmen, auf die hier eingegangen wird.
 
Algorithmen: Präzise definierte ­Arbeitsanleitungen für Computer
 
Soll ein spezielles Gericht nachgekocht werden, empfiehlt es sich, die Anweisungen eines Kochrezepts genau zu befolgen. Analog zu dieser Vorgehensweise wird Computern mithilfe von Algorithmen vorgeschrieben, wie sie die Zutaten (die Eingabedaten) zu verarbeiten haben. Im Folgenden wird untersucht, wie sehr die Raffinesse dieser speziellen „Kochrezepte“ in den letzten Jahrzehnten zugenommen hat.
 
Eine häufige bioinformatische Fragestellung ist das Auffinden von gemeinsamen Teilworten zweier Sequenzen A und B. Eine sehr effiziente Problemlösung basiert auf Suffixbäumen. In der Abbildung 1 ist ein Suffixbaum gezeigt, in dem alle Suffixe (Endungen) der Zeichenketten A = CCGCCT und B = CGCG eingetragen wurden. Kanten sind mit den in den Suffixen vorkommenden Zeichen markiert, das $-Zeichen gibt das Ende der Suffixe an und die Blätter verweisen auf die Positionen, an der die Suffixe in der Zeichenkette beginnen. Folgen wir ab der Wurzel dem Pfad C, G, C, so benötigen wir nur drei Schritte, um zu einem Knoten zu gelangen, der zwei Blätter (A, 2) und (B, 1) besitzt, die zu Suffixen aus A bzw. B gehören. Damit ist illustriert, dass in A und B gemeinsam vorkommende Teilworte mit linear von der Länge abhängigem Aufwand gefunden werden können. Suffixbäume und -arrays spielen aufgrund ihrer hohen Speicher- und Laufzeiteffizienz eine zentrale Rolle, z. B. um große Datensätze aus Sequenzierprojekten auszuwerten. 
 
Obiges Beispiel belegt, dass eine klug gewählte Datenstruktur eine rasche Suche nach gemeinsamen Teilworten ermöglicht und man könnte vermuten, dass alle wissenschaftlichen Fragestellungen mithilfe effizienter Algorithmen untersucht werden können.

Dies ist nicht der Fall: Eine große Menge von Problemen wird mittels brute-force Verfahren bearbeitet, wobei alle Lösungsmöglichkeiten durchprobiert werden müssen. Ein anschauliches Beispiel ist die Frage, wie viele Einträge ein Sudoku-Rätsel enthalten muss, damit es eindeutig mit Zahlen gefüllt werden kann. 2011 bewies ein brute-force Ansatz, dass kein Rätsel mit nur 16 Zahleneinträgen eindeutig lösbar ist. Für den Nachweis wurden 7.5 Millionen CPU-Stunden auf einem Cluster bestehend aus 640 Sechskernprozessoren benötigt [1]. Brute-force Algorithmen, die sämtliche Lösungen erzeugen und vergleichen, sind aufgrund der Komplexität wissenschaftlicher Problemstellungen oft zu zeitaufwendig. Andrerseits gibt es aber oft keinen Lösungsweg, der mit weniger Aufwand zum optimalen Ergebnis führt. Es ist einsichtig, dass in solchen Fällen Kompromisse und suboptimale Lösungen ausreichen müssen. 

 
Ein Beispiel aus der Bioinformatik ist das de novo Enzym-Design, bei dem für ein katalytisches Zentrum eine optimale Kombination von Residuen und ihrer Ausrichtung bestimmt werden muss. Aus Komplexitätsgründen wird hierfür oft eine beschränkte Menge von Rotameren kombiniert. Generell gilt, dass für viele Probleme, deren Lösung auf Modellbildung angewiesen ist, approximative Heuristiken verwendet werden müssen.
 
Sind Big Data Ansätze für die Lebens­wissenschaften geeignet?
 
Mit hoher Wahrscheinlichkeit generiert im Jahre 2025 die Genomik – und beispielsweise nicht die Astronomie – das größte Datenaufkommen, weil das Sequenzieren des kompletten Genoms ein wichtiges Element der Therapie vieler Krankheiten des Menschen sein wird [2]. Deep-Sequencing Projekte werden den Datenbestand noch weiter erhöhen, sodass es sinnvoll ist, nach Algorithmen Ausschau zu halten, die auf große Datensätze anwendbar sind. Beispielsweise eignen sich für die Klassifikation von hochdimensionalen Datensätzen nur wenige Verfahren wie Random Forests oder Support-Vektor-Maschinen [3].
 
Der Term „Big Data“ ist seit einigen Jahren ein Modewort in der Informatik. Mit diesem Begriff sind einerseits Datenmengen gemeint, die zu groß und zu komplex sind, als dass sie mit den üblichen Algorithmen ausgewertet werden könnten. Mit Big Data werden aber auch Untersuchungen des Benutzerverhaltens, Methoden der prädiktiven Analyse oder andere fortgeschrittene Analyseverfahren bezeichnet, die aus Daten (unternehmerischen) Mehrwert ziehen. Insbesondere die Leistungen moderner Suchmaschinen sind beeindruckend, sodass es naheliegt, ähnliche Algorithmen auch für wissenschaftliche Zwecke in Betracht zu ziehen. 
 
Im Februar 2009 erschien in der Zeitschrift Nature ein Artikel, mit dem gezeigt wurde, dass der räumliche und zeitliche Verlauf von Grippe-Epidemien in den USA durch die Analyse der bei Google nachgefragten Begriffe sehr präzise innerhalb eines Tages vorhergesagt werden kann [4]. Die Autoren konnten für den Zeitraum von 2004 - 2008 eine nahezu perfekte Korrelation zwischen den aus der Häufigkeit der Google-Suchterme abgeleiteten Verteilungsmustern und den vom CDC veröffentlichten zeigen. Das amerikanische Center for Disease Control and Prevention (CDC) benötigt für die Dokumentation solcher Epidemien mithilfe klassischer Techniken ein bis zwei Wochen, daher ist dieser Zeitgewinn bemerkenswert.
 
Belegt dieses Beispiel den Nutzen derartiger Big Data Ansätze für wissenschaftliche Anwendungen? Eher nicht: 2012 wurde von diesem Algorithmus eine Epidemie vorhergesagt, die sich im Umfang um den Faktor zwei von den CDC-Daten unterschied. Was war der Grund für diese Fehlprognose? 2012 gab es in den USA eine heftige Grippewelle, über die in den Medien ausführlich berichtet wurde. Vermutlich haben diese Nachrichten viele Grippe-bezogenen Suchen ausgelöst, die allerdings von Internetnutzern initiiert wurden, die nicht grippekrank waren [5]. Dieses Beispiel zeigt ganz deutlich die Schwäche solcher Ansätze: Sie können, obwohl die Stichproben enorm groß sind, nur Korrelationen, aber keine kausalen Zusammenhänge ableiten, da es sich um theoriefreie Ansätze handelt. Solche Big Data Ansätze sind daher kein Ersatz für traditionelle Datensammlung und Auswertung. 
 
Eine leise Revolution im ­wissenschaftlichen Rechnen
 
Eine Analyse der Qualität von Wettervorhersagen belegt, dass sich die Prognosen innerhalb der letzten dreißig Jahre deutlich besserten: Lag die Genauigkeit für 5-Tages-Vorhersagen im Jahr 1981 bei 50 - 65 %, so erreicht sie nun Werte von über 80 % [6]. Dieser Anstieg ist auf vier Ursachen zurückzuführen: 1) Das Modell für das Wettergeschehen wurde in den letzten Jahren kontinuierlich verfeinert. 2) Die initialen Parameter, mit denen die Berechnung gestartet wird, sind exakter fixiert, da z. B. per Satellit das Wettergeschehen genauer beobachtet werden kann. 3) Das Wettergeschehen kann aufgrund der wesentlich höheren Rechenleistung von Compute-Clustern mit einem feineren Gitter modelliert werden. Allerdings ist der Aufwand enorm: Um die Modellauflösung von 30 km auf 5 km zu steigern, muss die Anzahl von Rechner-Kernen von 104 auf 106 erhöht werden. 4) Die verbliebene Modell-Unsicherheit wird mithilfe von Ensemble-Methoden abgeschätzt: Ausgehend von einem initialen atmosphärischen Zustand wird nicht nur eine, sondern ein ganzes Ensemble von Vorhersagen erzeugt. Die einzelnen Berechnungen werden dazu mit unterschiedlichen Parametersätzen gestartet, die Unsicherheiten der Modellbildung reflektieren. Sind alle Vorhersagen generiert, werden sie überlagert und aus den Gemeinsamkeiten und Unterschieden werden Wahrscheinlichkeiten für das Eintreten des Wettergeschehens abgeleitet. Stimmen beispielsweise viele Vorhersagen darin überein, dass es in einem bestimmten Gebiet regnen wird, ist die entsprechende Wahrscheinlichkeit hoch, sagen nur wenige Modelle Regen vorher, ist sie niedrig. 
 
Auf ähnliche Weise haben sich in den letzten 20 Jahren auch bioinformatische Verfahren geändert, beispielsweise bei der Berechnung phylogenetischer Bäume, die Taxa als Knoten und Verwandtschaftsbeziehungen mittels Kanten repräsentieren: Einfache Verfahren zur Modellierung von Mutationsvorgängen wurden durch aufwendigere ersetzt, zur Schätzung von Mutationshäufigkeiten werden Optimierungsverfahren verwendet und a posteriori Wahrscheinlichkeiten geben für die Kanten die verbleibende Unsicherheit an. Ein weiteres Beispiel für den Einzug von Ensemblemethoden ist die Vorhersage von Protein-3D-Strukturen, die sich auf die Superposition mehrerer Strukturmodelle stützt.
 
Paradigmen und Algorithmen der ­Bioinformatik werden kontinuierlich der Datenlage angepasst
 
Generell ist auch in der Bioinformatik eine stetige Veränderung der Paradigmen und Algorithmen zu beobachten: Zur Funktionszuweisung wurden anfangs Sequenzen paarweise mit Programmen wie FASTA oder BLAST verglichen, die auf Geschwindigkeit optimiert waren. Mittlerweile werden Proteine meist als Elemente größerer Gruppen beschrieben: Die Strukturen von Proteindomänen wurden Faltungstypen zugeordnet und Sequenzen sind in Form von Proteinfamilien zusammengefasst. Aufgrund der vielen Sequenzierprojekte kann ein Pfam- oder InterPro-Eintrag, der jeweils eine Menge homologer Proteine beschreibt, mehrere zehntausend Sequenzen enthalten. 
 
Es bot sich daher an, neue Algorithmen zu entwickeln, die das mit dem Sequenzieren zusätzlich erworbene Wissen zur Präzisierung der Modelle nutzen. Anstelle einer universellen Scoring-Matrix zum paarweisen Vergleich von Sequenzen werden nun für jede Proteinfamilie mithilfe eines Hidden-Markov-Modells (HMM) die speziellen Präferenzen einer jeden Residuenposition beschrieben. Aus einem HMM kann exakt abgeleitet werden, in welchen Bereichen eines Proteins Insertionen und Deletionen toleriert werden. Daher gehören HMMs zu den Stand-der-Technik Verfahren des Sequenzvergleichs und die Qualität von Protein-3D-Modellen hat sich aufgrund des paarweisen Vergleichs von Target- und Templatsequenz mittels HMMs [7] deutlich stabilisiert. Deep-Sequencing Ansätze, aus denen die Position von Nukleosomen abgeleitet wird, werden ebenfalls häufig mit HMMs oder anderen, sehr ausgefeilten Verfahren analysiert [8].
 
Neue Herausforderungen und Möglich­keiten in der Bioinformatik
 
Für Proteine ist klar geworden, dass eine gemeinsame Abstammung (Homologie) nicht gleichbedeutend ist mit übereinstimmender Funktion: So ist mittlerweile bekannt, dass fast 40 % aller Proteinsuperfamilien funktionell diverse Vertreter enthalten. Mit einfachem Sequenzvergleich sind feine Unterschiede aber kaum zu erkennen, im Gegensatz dazu haben die jüngst entwickelten Sequence Similarity Networks (SNNs) das Potenzial, großen Proteinfamilien eine Feinstruktur zu geben [9]. In einem SNN werden homologe Proteinsequenzen zu Clustern gruppiert, die Netzwerke bilden. Die Charakterisierung von Proteinen aus den unterschiedlichen Clustern eröffnet die Chance, deren Diversität zu erforschen. 
 
Eine jüngst in der Zeitschrift Science publizierte Arbeit belegt sehr anschaulich, wie eine Kombination von bioinformatischen und experimentellen Studien genutzt werden kann, bisher nicht untersuchte Enzyme zu identifizieren und zu charakterisieren [10]. Die Autoren waren daran interessiert, die Funktion häufiger Enzyme des humanen Darm-Mikrobioms zu bestimmen. Da diese Mikroorganismen nicht kultivierbar sind, wurde aus Metagenom- und Metatranskriptom-Daten abgeleitet, welche Enzymfamilien in diesem Habitat besonders häufig vorkommen. Interessante Kandidaten wurden auf ein SNN abgebildet; mithilfe weiterer bioinformatischer Verfahren konnte deren Funktion eingeschränkt werden. Enzymatische Tests dienten schließlich zum Funktionsnachweis. Diese Arbeit ist ein beeindruckendes Beispiel für den Trend, Algorithmen zur Formulierung von Hypothesen zu nutzen, die anschließend im Nasslabor überprüft werden. Trotz vieler Unzulänglichkeiten schränken bioinformatische Verfahren die Anzahl zu überprüfender Hypothesen drastisch ein und machen so eine gezieltere Suche „nach einer Nadel im Heuhaufen“ möglich.
 
Nutzung schwacher Korrelationssignale
 
Große Datensätze erlauben es, schwächere Signale mit höherer Zuverlässigkeit nachzuweisen. Damit werden neue Algorithmen einsetzbar, die bei kleineren Stichprobenumfängen scheitern. In den letzten Jahren wurden beispielsweise sequenzbasierte Verfahren zur Vorhersage der 3D-Struktur von Proteinen und Proteinkomplexen entwickelt, die erst jetzt verlässliche Vorhersagen liefern, da die Datengrundlage hinreichend umfangreich geworden ist. Diese Methoden basieren auf dem Konzept der korrelierten Mutationen, das in Abbildung 2 erläutert wird. 
 
Es ist leicht einzusehen, dass in Proteinen durch Mutationen bedingte, destabilierende Effekte durch nachfolgende Mutationen aufgehoben werden können. So kann beispielsweise der Austausch einer größeren Seitenkette durch eine kleinere, aus der eine energetisch ungünstige Kavität resultiert, durch eine zweite Mutation kompensiert werden. Dies gilt, wenn eine räumlich benachbarte, kleinere Seitenkette durch eine größere ersetzt wird. Im Umkehrschluss folgt, dass Muster, die auf kompensierende Mutationen hindeuten, von Residuenpositionen stammen, die in der 3D-Struktur benachbart liegen. Gelingt es also, eine ausreichende Anzahl solcher Korrelationsmuster zu identifizieren, können Algorithmen, die für die Strukturaufklärung per NMR-Verfahren entwickelt wurden, völlig analog genutzt werden. Die Arbeitsgruppe um D. Baker hat jüngst mit einem solchen sequenzbasierten Ansatz 137 neue Protein-Faltungstypen vorhergesagt, die bisher nicht in der Natur beobachtet wurden [11]. Um die Datenbasis zu erweitern, wurden auch in diesem Fall zusätzlich Metagenomdaten analysiert.
 
Korrelierte Mutationen treten auch in den Interfaces von Proteinkomplexen auf und die damit verknüpften Signale werden zur Vorhersage von interagierenden Proteinen verwendet. Auch bei diesem Ansatz ist die Anzahl bekannter Sequenzen für den Erfolg ausschlaggebend, sodass im Moment nur ein kleiner Anteil möglicher Kandidaten untersucht werden kann [12]. Es ist allerdings nur eine Frage der Zeit, bis dieses Verfahren häufiger die Vorhersage von Proteinkomplexen zulässt. 
 
Ausblick
 
Mit weiter zunehmender Rechenleistung wird es möglich, genauere und höher aufgelöste Modelle zu berechnen, sodass die Performanz wissenschaftlicher Algorithmen weiterhin kontinuierlich zunehmen wird. Damit kommt dem Verständnis der komplexen Prozesse, die simuliert werden sollen, eine besondere Bedeutung zu, da es die Qualität der Computer-Modelle bestimmt. Richtungsweisende wissenschaftliche Erkenntnisse sind aufgrund der Komplexität der Systeme vor allem von interdisziplinären Kooperationen unter Einbeziehung der Informatik zu erwarten.
 
Kontakt
Prof. Dr. Rainer Merkl
Universität Regensburg
Regensburg
rainer.merkl@ur.de
 
Lebenslauf
Dr. R. Merkl 
studierte an der Hochschule Giessen /Friedberg Biomedizinische Technik und 
an der Fernuniversität Hagen Informatik. 
Er wurde an der Universität Göttingen promoviert und hat sich an der Universi­tät Regensburg im Fach Bioinformatik habilitiert. Er leitet dort als apl. 
Prof. die Arbeitsgruppe Proteindesign 
und Evolution.
 
Weitere Beiträge zum Thema: http://www.git-labor.de/search/gitsearch/big%20data%20type:topstories
 

Referenzen

1.            McGuire G., Tugemann B. und Civario G.: Experimental Mathematics 23, 190-217 (2014) doi: 10.1080/10586458.2013.870056

2.            Stephens Z. D., Lee S. Y., Faghri F., Campbell R. H., Zhai C., Efron M. J., Iyer R., Schatz M. C., Sinha S. und Robinson G. E.: PLoS Biol 13, e1002195 (2015) doi: 10.1371/journal.pbio.1002195 pmid:26151137

3.            Merkl R. Bioinformatik: Grundlagen, Algorithmen, Anwendungen. Weinheim: WILEY-VCH; 2015.

4.            Ginsberg J., Mohebbi M. H., Patel R. S., Brammer L., Smolinski M. S. und Brilliant L.: Nature 457, 1012-1014 (2009) doi: 10.1038/nature07634 pmid:19020500

5.            Lazer D., Kennedy R., King G. und Vespignani A.: Science 343, 1203-1205 (2014) doi: 10.1126/science.1248506 pmid:24626916

6.            Bauer P., Thorpe A. und Brunet G.: Nature 525, 47-55 (2015) doi: 10.1038/nature14956 pmid:26333465

7.            Söding J.: Bioinformatics 21, 951-960 (2005) doi: 10.1093/bioinformatics/bti125 pmid:15531603

8.            Segal E., Fondufe-Mittendorf Y., Chen L., Thåström A., Field Y., Moore I. K., Wang J. Z. und Widom J.: Nature 442, 772-778 (2006) 

9.            Gerlt J. A., Bouvier J. T., Davidson D. B., Imker H. J., Sadkhin B., Slater D. R. und Whalen K. L.: Biochim Biophys Acta 1854, 1019-1037 (2015) doi: 10.1016/j.bbapap.2015.04.015 pmid:25900361

10.          Levin B. J., Huang Y. Y., Peck S. C., Wei Y., Martinez-Del Campo A., Marks J. A., Franzosa E. A., Huttenhower C. und Balskus E. P.: Science 355, (2017) doi: 10.1126/science.aai8386 pmid:28183913

11.          Ovchinnikov S., Park H., Varghese N., Huang P. S., Pavlopoulos G. A., Kim D. E., Kamisetty H., Kyrpides N. C. und Baker D.: Science 355, 294-298 (2017) doi: 10.1126/science.aah4043 pmid:28104891

12.          Hopf T. A., Scharfe C. P., Rodrigues J. P., Green A. G., Kohlbacher O., Sander C., Bonvin A. M. und Marks D. S.: Elife 3, (2014) doi: 10.7554/eLife.03430 pmid:25255213

Jetzt registrieren!

Die neusten Informationen direkt per Newsletter.

To prevent automated spam submissions leave this field empty.