1. Einleitung

Die rasante Entwicklung der Bioinformatik hat die Informatikforschung vor viele neue Herausforderungen gestellt. So auch auf dem Gebiet des Workflow-Managements. Die Sequenzierung des menschlichen Genoms hätte ohne den Einsatz von Systemen, die die Prozesse in den Forschungslabors unterstützen und so die Produktivität erhöhen, nicht in so kurzer Zeit erreicht werden können. In der vorliegenden Arbeit wird ein Überblick über die Charakteristika von Bioinformatik-Workflows gegeben. Daraus werden Anforderungen abgeleitet, die ein Workflow-Management-System für den Einsatz in der Bioinformatik erfüllen muss. Außerdem werden drei Systeme vorgestellt, die in Forschunglaboren eingesetzt werden. Zunächst folgt eine kurze Vorstellung der grundlegenden Begriffe des Workflow-Managements.

Die Workflow Management Coalition (WfMC) definiert Workflow in [Al00] als die Automatisierung eines Geschäftsprozesses, bei dem Dokumente, Informationen oder Aufgaben zur Verarbeitung von einem Teilnehmer an einen anderen weitergereicht werden (Datenfluss), gesteuert durch eine Menge prozeduraler Regeln (Kontrollfluss). Ein Workflow setzt sich aus logischen Schritten zusammen, die auch als Aktivitäten bezeichnet werden. Aktivitäten können entweder von Anwendungsprogrammen ausgeführt werden (z.B. Sequenz-Alignment durch das Programm BLAST) oder menschliche Interaktion erfordern (z.B. Ausfüllen eines Formulars).

Ein Workflow-Management-System (WfMS) stellt Software zur Workflow-Modellierung, Wf-Kontrolle und Wf-Tracking (Speicherung aller Daten der Wf-Ausführung) zur Verfügung. Die Workflow-Ausführung wird von einer oder mehreren Workflow-Engines gesteuert: Sie interpretieren die Prozessdefinition, interagieren mit den Workflow-Teilnehmern und rufen zu gegebenen Zeitpunkten benötigte Anwendungen auf.

Der Einsatz von WfMS kann die Effektivität und Produktivität durch stärkere Automatisierung der Abläufe erhöhen. Außerdem werden bei der Modellierung Kontroll- und Datenfluss sichtbar gemacht und dadurch besser verstanden. Das kann dazu beitragen, dass Schwachstellen und Fehler gefunden und durch Überarbeitung des Prozesses beseitigt werden.

2. Charakterisierung von Workflows in der Bioinformatik

In diesem Kapitel werden die grundlegenden Eigenschaften, die Workflows in der Bioinformatik charakterisieren und von Workflows in anderen Gebieten unterscheiden, kurz vorgestellt.

2.1 Hohes Volumen der Daten und Experimente

„High-Throughput“ ist ein häufig benutztes Schlagwort in Verbindung mit Projekten in der Bioinformatik. Es bedeutet „hoher Durchsatz“ und bezieht sich vor allem auf zwei Aspekte: die Anzahl der Experimente und die Daten, die bei deren Ausführung benötigt oder generiert werden.

Gründe für den hohen Durchsatz sind zum Beispiel:

- Wiederholte Ausführung desselben Experiments, um Informationen über Fehlerraten zu erhalten (-> Qualitätstest, Verifikation der Algorithmen/Experimente).

- Automatisierung der Experimente: Durch Einsatz von Robotern können die Schritte, die kein menschliches Eingreifen benötigen, sehr viel schneller erledigt werden.

- Größe der zu untersuchenden Genome (z.B. Mensch: 3 Milliarden DNA-Basen, etwa 100.000 Gene).

- Menge der für die Forschung interessanten Informationen, die bei einem Experiment mit einer DNA-Probe erzeugt werden können und gespeichert werden müssen (z.B. kodierende und nicht-kodierende Regionen, Genprodukt, zugehöriges Protein, dessen Sekundär- und Tertiärstruktur, Funktion,...).

Veranschaulichen kann man sich die hohen Datenmengen an der Anzahl von Einträgen in Proteindatenbanken, z.B. beinhaltete Swiss-Prot 1998 etwa 80.000 Sequenzen, 2001 sind es mehr als 100.000 [SP02]. Die in solchen wissenschaftlichen Datenbanken gespeicherte Informationsmenge verdoppelt sich etwa alle 15 Monate und ein Labor kann mehr als 100 Gigabyte Daten pro Tag produzieren [LGG01]. Da die Rohdaten (also die reinen DNA-Sequenzen) ohne Analyse nutzlos sind, werden viele Experimente durchgeführt. In Abbildung 1 werden die in der Bioinformatik auftretenden Datentypen mit der Menge aufgeführt, die bis zum Jahr 2000 analysiert wurde.

2.2 Komplexität

Eine zweite wichtige Eigenschaft betrifft die Komplexität der Daten und Abläufe. Laut [GRS95] sind Prozesse in den Bioinformatik-Laboren ein komplexes Netz aus manuellen und automatisierten Laboraktivitäten, man spricht deshalb auch von semi-automatisierten Workflows. Zu den manuellen Aufgaben gehören die Planung und Aufstellung von Experimenten, die Kontrolle der Roboter, Aufnahme von Rohdaten, verschiedene Zwischenanalysen und Qualitätskontrollen und die Freigabe der Resultate. Die Prozesse, die durch Verknüpfung dieser Aufgaben entstehen, sind zum einen sehr stark strukturiert, das heißt die Aktivitäten im Workflow sind klar definiert und voneinander abgegrenzt. Zum anderen drückt sich die Komplexität der Abläufe in vielen Verzweigungen und Synchronisationsbedingungen im Kontrollfluss aus.

Ebenso komplex wie die Workflows sind die Daten selbst. Auch wenn DNA-Proben auf den ersten Blick als simple Zeichenketten erscheinen, werden deutlich komplexere Datenstrukturen benötigt. In [GRS95] werden als Beispiel die Gruppierung von DNA-Strängen auf DNA-Chips genannt, wobei die Chips wiederum für ein Roboter-gesteuertes Experiment gruppiert werden können (sog. ‚convoy’). Jedes DNA-Molekül auf dem Chip besitzt also bereits eine komplexe Datenstruktur (z.B. Sequenz, Exons/Introns, Genprodukte), und der Chip besitzt zusätzlich eigene Attribute (z.B. Aufbau, Referenz auf enthaltene DNA-Sequenzen). Weitere Beispiele für komplexe Datenstrukturen sind Abbildung 1 zu entnehmen, z.B. die räumliche Struktur der Makromoleküle.

2.3 Ungewöhnliche Datentypen

Der größte Teil der WfMS-Forschung konzentrierte sich bisher auf Geschäftsprozesse. Diese sind meist dokumentenorientiert und bieten daher vor allem Datentypen an, die sich für die Repräsentation von Formularen eignen. In der Bioinformatik stehen dagegen die DNA-Sequenzen im Vordergrund des wissenschaftlichen Interesses, zu deren Repräsentation ungewöhnliche Datentypen benötigt werden.

Abbildung 1 führt die wichtigsten Datentypen der Genomforschung auf und verschafft einen Überblick über die Menge und Vielfalt von Informationen, die bei Experimenten erzeugt werden.

Datentyp	Datenmenge	Bioinformatik-Themen
DNA-Rohdaten	8,2 Mio. Sequenzen (9,5 Mrd. Basen)	- Erkennung von Exons und Introns - Vorhersage von Genprodukten
Proteinsequenzen	300.000 Sequenzen (~ je 300 Aminosäuren)	- Sequenzvergleiche - Multiple Sequenz-Alignments
Makromolekulare Struktur	13.000 Strukturen (~ je 1.000 Atom-Koordinaten)	- Vorhersage von Sekundär-, Tertiärstruktur - 3D-Struktur-Alignment - Molekulare Simulationen (Kraftfeld-Simulationen, Molekulare Bewegungen, ...)
Genome	40 komplette Genome (je 1,6 Mio. bis 3 Mrd. Basen)	- Phylogenetische Analyse - Methabolische Pathways - Analyse Gene - Krankheiten
Genexpression	~ 6.000 Gene	- Korrelierende Expressionsmuster - Zusammenhang Expressionsdaten mit Sequenzdaten, strukturellen und biochemischen Daten

Abbildung 1: Datentypen in der Bioinformatik (nach [LGG01])

2.4 Schneller Wandel der Workflows

In einer noch relativ jungen Forschungsdisziplin wie der Bioinformatik, die zusätzlich mit der sich rasch entwickelnden Computertechnik stark verbunden ist, sind die Workflows häufigen Änderungen unterworfen. Neue Forschungserkenntnisse, technischer Fortschritt oder auch die experimentelle Unsicherheit führen ständig dazu, dass in Workflows die Reihenfolge von Einzelschritten umgestellt wird, ganze Teilschritte ausgelassen oder neue Teilprozesse eingefügt werden. Besonders häufig kommt es vor, dass in einem Prozessschritt zusätzliche Informationen gespeichert werden sollen ([BSR96]). Im Whitehead Institut / MIT Center for Genome Research kommen kleinere Protokolländerungen laut [SRG95] wöchentlich vor und größere Änderungen, wie das Hinzufügen oder Entfernen von einem oder mehreren experimentellen Schritten, etwa monatlich.

2.5 Klassifikation Bioinformatik-Workflows

Man kann Workflows unterschiedlich klassifizieren. Eine in der Fachliteratur übliche Einteilung ist: Administrative Workflows, Ad-hoc-Workflows, Production-Workflows.

Abbildung 2: Klassifikation Workflows (nach [GHS95])

Wie in Abbildung 2 illustriert sind Struktur und Komplexität der Aufgaben bei administrativen Workflows am einfachsten. Es handelt sich um wiederkehrende, planbare Prozesse mit einfachen Koordinierungsregeln für die einzelnen Aktivitäten, die automatisiert werden können. Die meisten Entscheidungen müssen jedoch von Menschen getroffen werden. Administrative WfMS basieren meistens auf E-Mail als Kommunikationsmittel.

Ad-hoc-Workflows dagegen besitzen keine feste Struktur für den Kontrollfluss und können deshalb nicht automatisiert werden. Sie müssen von Menschen koordiniert werden. Der Begriff „ad hoc“ deutet darauf hin, dass Entscheidungen über Ausführungsreihenfolge kurzfristig und während der Ausführung des Workflows getroffen werden. Es handelt sich um Aufgaben, bei denen typischerweise nur wenige Leute über relativ kurze Zeiträume zusammenarbeiten. WfMS, die Ad-hoc-Workflows unterstützen, werden auch als Groupware bezeichnet.

Die dritte Kategorie bilden die Production-Workflows. Hierbei handelt es sich zwar wie bei administrativen Workflows um wiederkehrende und planbare Prozesse, jedoch ist die Struktur hier sehr viel komplexer und es wird auf verschiedene Informationssysteme zugegriffen. Außerdem liegt ein höherer Grad an Automatisierung vor: Bei administrativen Workflows werden die meisten Entscheidungen von Menschen getroffen, bei Production-Workflows können viele Entscheidungen automatisch aufgrund der Datenlage getroffen werden.

Nach den oben beschriebenen Eigenschaften sind Prozesse der Bioinformatik am ehesten als Production-Workflows einzuordnen, die jedoch durch die ständigen Veränderungen in den Abläufen und die enormen Datenmengen besonders kompliziert sind.

3. Anforderungen der Bioinformatik an Workflow-Management-Systeme

In diesem Kapitel werden die speziellen Anforderungen der Bioinformatik an Workflow-Management-Systeme erläutert, wie sie sich aus den in Kapitel 2 vorgestellten Eigenschaften ergeben (nach [GRS95]). Es wird auch darauf eingegangen, wieso bisherige kommerzielle Systeme diesen nicht genügen.

3.1 Workflow-Modellierung

Bei der Workflow-Modellierung werden die Ausführungsreihenfolge, benötigte Eingabedaten und die Übergangsbedingungen zwischen den Workflow-Einzelschritten festgelegt. Solch ein Modell kann explizit (durch einen deklarativen Formalismus spezifiziert) oder implizit (in Anwendungsprogramme eingebettet) vorliegen. Auch Mischformen davon sind möglich, wenn zum Beispiel in einem Workflow-Graphen die Schritte und deren Reihenfolge explizit modelliert sind, weitere Übergangsbedingungen jedoch durch Implementation in Anwendungsprogrammen implizit modelliert sind.

Explizite Modellierung ist zu bevorzugen, weil sie einen besseren Überblick über den Workflow, die Daten und die Abhängigkeiten bieten kann. Um dies zu unterstützen und den Anforderungen in Genlaboren zu genügen, muss das Workflow-Metamodell nach [GRS95] die folgenden Möglichkeiten bieten:

Unterstützung komplexer Daten

Hierbei ist vor allem wichtig, dass die Teil-Ganzes-Beziehung unterstützt wird, da diese in Labor-Workflows sehr häufig benötigt wird. Beispiele sind die Zerlegung eines DNA-Strangs in DNA-Teilstränge für Experimente oder die in Abschnitt 2.2 beschrieben DNA-Chips. Die benötigte Komplexität kann z.B. durch ein objektorientiertes Datenmodell erreicht werden, das aber meist in den Anwendungen modelliert werden muss, weil es von kommerziellen WfMS kaum angeboten wird.

Modellierung von Ein- und Ausgabedaten

Jede Aktivität und jeder Workflow kann Eingabedaten als Argumente benötigen, diese können von einer vorherigen Aktivität erzeugt worden sein. Ebenso werden Ausgabedaten produziert, die wiederum die Eingabedaten für eine andere Aktivität bilden können. Ein- und Ausgabedaten sollen im Workflow-Metamodell modelliert werden können. Zwar ist dies in den meisten kommerziellen WfMS möglich, jedoch reicht die unterstützte Komplexität für die Bedürfnisse der Bioinformatik oft nicht aus (objektorientiertes Modell benötigt, siehe voriger Absatz).

Modellierung von Transitionsbedingungen

Transitionsbedingungen beschreiben, unter welchen Umständen es erlaubt ist, von einer Aktivität in eine andere zu wechseln. Insbesondere muss es möglich sein, Synchronisation und Datenbedingungen zwischen Workflows auszudrücken. Es soll möglich sein, die Bedingungen im WfMS zu modellieren, weil dies für die Workflow-Ausführung notwendig ist. Einfache Transitionsbedingungen gehören zum Standard der Workflow-Modellierung, während z.B. Synchronisation nicht immer unterstützt wird.

Unterstützung komplexer Workflows

Um dies zu erreichen, muss es möglich sein, ein neues Workflow-Schema aus existierenden zu konstruieren. Dafür benötigte Mechanismen sind die Hintereinanderausführung von Workflows, Subworkflows für verschieden detaillierte Sichten (Aktivitäten in einem Workflow-Schema bestehen aus einem kompletten Subschema) und die Möglichkeit, alternative Pfade in einem Workflow-Schema zu modellieren (entspricht einer OR-Verzweigung). Diese Möglichkeiten werden im Wesentlichen von kommerziellen WfMS unterstützt.

3.2 Workflow-Ausführung

Workflow-Ausführung betrifft die gesamte Ablaufsteuerung während der Ausführung von Workflow-Aktivitäten. Die richtige Ausführungsreihenfolge muss sichergestellt werden, d.h. die Anwendungsprogramme müssen in der richtigen Reihenfolge ausgeführt werden und der Nutzer muss zur richtigen Zeit aufgefordert werden, benötigte Daten einzugeben. Die Komponente eines WfMS, die diese Aufgaben übernimmt, wird auch als Workflow-Engine bezeichnet.

In der Bioinformatik wird die Kontrolle der Workflows durch deren Komplexität, Flexibilität und die enormen Datenmengen erschwert. In Abschnitt 4.2 wird mit BioOpera ein System vorgestellt, das die Workflow-Ausführung weitgehend automatisiert und somit auch die Performanz deutlich steigern kann.

3.3 Workflow-Tracking

Die dritte Hauptaufgabe eines WfMS ist es, alle Informationen über die Workflow-Ausführungen zu speichern. In der sogenannten „Event History“ wird zu jeder Aktivität gespeichert, von wem zu welcher Zeit und mit welchem Ergebnis sie ausgeführt wurde. Diese Informationen können hauptsächlich für die Analyse der Workflows benutzt werden, z.B. für Statistiken über die Auslastung, um Schwachstellen in der Effektivität aufzuspüren. Weitere Kriterien, nach denen die Ergebnisse ausgewertet werden können, sind Dauer der Ausführung, Fehlerraten usw.

Workflow-Tracking gehört zu den Standardaufgaben eines WfMS und wird deshalb von den meisten kommerziellen WfMS unterstützt. Schwierig wird die Aufgabe in der Bioinformatik jedoch wieder durch die Flexibilität, denn zu jedem Workflow muss auch genau festgehalten werden, unter welcher Schemaversion er ausgeführt wurde, sonst ist eine spätere Interpretation der gespeicherten Daten unmöglich (siehe 3.7).

3.4 Sichten auf Daten und Experimente

Die drei bisher beschriebenen Anforderungen gehören zu den Standardaufgaben von WfMS. Diese unterliegen nun in der Bioinformatik der zusätzlichen, sehr zentralen Anforderung, dass die Proben, die im Genlabor untersucht werden, im Mittelpunkt der Betrachtung stehen. Sowohl die Datenstrukturen als auch das Datenbankdesign müssen dies unterstützen.

Typische Anfragen sind:

- Bestimme den Status der Proben in allen Workflow-Instanzen.

- Finde alle kürzlich produzierten Ergebnisse für eine bestimmte Probe.

- Zeige die Event History aller Aktivitäten, die eine bestimmte Probe betreffen.

Ebenso sind aber neben den Daten natürlich auch die Experimente von Interesse. So kann eine Anfrage lauten, alle Proben zu finden, die in einem Experiment benutzt wurden. Man muss also gewissermaßen zwischen zwei Sichten wechseln können: der datenorientierten und der experimentorientierten Sicht. Man kann aber in der Datenbank nur eine Sicht direkt implementieren, die andere Sicht muss durch einen View realisiert werden. Die Datenbank kann zum Beispiel wie in LabBase (siehe Abschnitt 4.1) ereignisorientiert aufgebaut sein, d.h. zu jedem Workflow-Einzelschritt werden die gewünschten Informationen gespeichert. Dann sind aber die Informationen zu den Laborproben verstreut und müssen durch eine Abfrage über alle Schritte, in denen sie vorkommen, zusammengestellt werden. Solch einen View zu definieren wird durch die ständigen Veränderungen im Workflow-Schema zusätzlich erschwert, da sich die vielen alten Versionen alle im Datenbankschema widerspiegeln (siehe 3.7). In Abschnitt 4.1 wird eine Lösungsmöglichkeit vorgestellt.

3.5 Bedienbarkeit

Für die bessere Unterstützung der Entwickler werden von [GRS95] die Bereitstellung folgender Tools gefordert:

Workflow Editor

Ein grafischer Editor soll die Definition der Aktivitäten und Transitionen erleichtern. Wichtig ist hierbei, dass das Workflow Metamodell voll unterstützt werden sollte, das für Genlabore, wie in 3.1 beschrieben, sehr komplex ist. Ansonsten werden grafische Workflow Editoren von den meisten kommerziellen Systemen angeboten.

Workflow Browser

Damit die Nutzer die Ausführung besser kontrollieren und verfolgen können, wird ein Workflow Browser benötigt, um den Status der Experimente und deren Resultate leicht überprüfen zu können. Zwar verfügen die meisten WfMS über einen Browser, allerdings mangelt es am Punkt der datenorientierten Sicht. Es wird sowohl die Kontrolle über Experimente als auch über die DNA-Proben benötigt. Die dadurch auftretenden Schwierigkeiten wurden in Abschnitt 3.4 näher erläutert.

Debugger / Simulator

Ein Debugger wird gebraucht, um nicht korrekt definierte Workflows zu analysieren. Einige kommerzielle Systeme bieten zwar einen Debugger an, jedoch noch nicht in ausreichender Komplexität. Ein Simulator kann helfen, Engpässe in den Abläufen oder Fehler in der Workflow-Logik (insbes. Deadlocks) zu identifizieren. Beide Tools werden auch außerhalb der Bioinformatik in den meisten Workflow-Anwendungen benötigt und sind somit nicht spezifisch für die Bioinformatik.

Application Program Interface (API)

Zur Entwicklungsunterstützung ist es hilfreich, wenn vom WfMS ein API bereitgestellt wird. Es sollte Abstraktionen für häufig vorkommende Interaktionen zwischen Programmen und dem WfMS anbieten. Für immer wiederkehrende Aufgaben sollten vordefinierte Workflows bereitgestellt werden, die dann nur noch an die speziellen Gegebenheiten eines Labors angepasst werden müssen.

Generische Statusreports

Sie sollen einen Überblick über die Aktivitäten der Workflows während eines gewissen Zeitraums bieten. Das können zum Beispiel Statistiken sein, die besagen, wie viele Proben innerhalb einer Woche sequenziert wurden und bei wie vielen Fehler bei der Bearbeitung auftraten. Ein speziell auf die Bioinformatik zugeschnittenes WfMS sollte die Form solcher Reports beispielhaft vorgeben, und trotzdem Anpassungen an die konkreten Bedürfnisse jedes Labors erlauben.

3.6 Performanz

Um bei der gegebenen Datenflut und Komplexität der Algorithmen akzeptable Rechenzeiten zu erhalten, muss das WfMS performant arbeiten. In [AB+99] wird kritisiert, dass erheblicher Forschungsaufwand für die Optimierung von Algorithmen betrieben wird, jedoch zu wenig dafür, wie man diese Algorithmen auf sehr große Datenmengen anwenden kann. Für das Problem des Sequenzvergleiches zum Beispiel gibt es inzwischen mehrere verschiedene Algorithmen, aber kaum gute Ansätze, wie man damit Milliarden Sequenzvergleiche durchführt.

Mainframes bieten zwar sehr hohe Rechenleistungen, stehen aber vielen Forschergruppen nicht zur Verfügung. Man benötigt folglich Ansätze wie paralleles Rechnen, jedoch reicht es nicht aus, allein den Algorithmus dafür als Workflow zu implementieren. Die eigentlichen Probleme entstehen durch den Wartungsaufwand bei langandauernden Berechnungen, der nicht zu unterschätzen ist. Die Dauer der Berechnungen kann in der Größenordnung von Monaten liegen, währenddessen können Rechner ausfallen oder von anderen Nutzern stark beansprucht werden. Die auftretenden Probleme und eine mögliche Lösung unter Benutzung von dynamischer Lastbalancierung werden in Abschnitt 4.2 vorgestellt.

3.7 Flexibilität

Wie in 2.4 bereits erwähnt, unterliegen die Arbeitsabläufe stetiger Veränderung, deshalb muss ein WfMS für Genlabore häufige Schemaänderungen der Workflows ermöglichen und unterstützen. Man unterscheidet zwischen Schemaänderungen, d.h. alle folgenden Workflow-Instanzen werden nach diesem geänderten Schema ausgeführt (=„Schemaevolution“), und Instanz-Änderung, wobei nur das Schema einer bestimmten Instanz geändert wird, das Workflow-Schema aller anderen Instanzen aber unverändert bleibt. Letzteres wird auch als „Ad-hoc-Änderung“ bezeichnet. Beispiele sind die unvorhergesehene Wiederholung eines Experiments oder dass aufgrund der Datenlage der Workflow an anderer Stelle gestartet wird als ursprünglich geplant.

Durch beide Arten von Änderungen ergeben sich zwei Herausforderungen. Zum einen müssen alle alten Versionen des Workflow-Schemas in der Datenbank aufgehoben werden, zusammen mit der Information, von welcher Version bestimmte Daten erzeugt wurden. Das ist erforderlich, weil eine Interpretation der Event History nur im Kontext des Workflow-Schemas möglich ist, von dem die Daten erzeugt wurden. Es ist ersichtlich, dass das Datenbankdesign und die Formulierung von Datenbankabfragen durch das Vorhandensein vieler Workflow-Schemaversionen erschwert werden. Ziel ist es, ein Datenbankschema zu entwickeln, das robust gegenüber Workflow-Schemaänderungen ist.

Die zweite Herausforderung besteht darin, zu entscheiden, wie die Workflows behandelt werden, die sich während der Änderung gerade in Ausführung befinden (auch als „dynamische Workflow-Modifikation“ bezeichnet). Es gibt viele Möglichkeiten der Fortsetzung und Entscheidungen müssen im Einzelfall, abhängig von den gegebenen Umständen, getroffen werden. So kann es sein, dass bereits gestartete Workflows mit dem alten Schema beendet werden können. Ebenso kann ein Abbruch erforderlich sein, oder man findet korrespondierende Schritte zwischen dem alten und dem neuen Schema, so dass der Workflow, wenn ein gewisser Status erreicht ist, zum neuen Schema wechseln kann.

Für beide Arten der Workflow-Änderung gibt es laut [RM00] zwar Ansätze, jedoch noch keine Integration in kommerzielle Lösungen.

3.8 Verfügbarkeit

Die Ausführung von Workflows kann unvorhergesehen unterbrochen werden, z.B. durch logische Fehler in der Workflow-Definition oder Hardware-Ausfälle. Bei administrativen Workflows sind dadurch entstehende Verzögerungen nicht so kritisch wie bei Production-Workflows. Hier können im Fehlerfall langandauernde Berechnungen unterbrochen werden und im schlimmsten Fall deren Zwischenergebnisse verloren sein. Es wird also ein System benötigt, dass sich auch im Falle von Hard- und Software-Ausfällen stabil verhält. Ziel ist dabei, dass möglichst wenige der bereits gelaufenen Berechnungen wiederholt werden müssen und der Neustart minimales Eingreifen von Hand erfordert. In BioOpera (Abschnitt 4.2) wird dies durch persistente Speicherung aller zur Prozessausführung gehörigen Informationen gelöst.

3.9 Unterstützung verschiedener Datenbanksysteme

Jedes WfMS benötigt eine Datenbank, um Daten und Workflow-Schemata abzuspeichern. Da in Labors oft schon vor der Einführung eines WfMS eine Datenbank in Betrieb ist und damit die Entscheidung für ein bestimmtes DBMS bereits getroffen wurde, ist es günstig, wenn das WfMS in der Lage ist, mit verschiedenen Datenbanksystemen zu arbeiten.

Kommerzielle Systeme liefern jedoch meistens ein eigenes Datenbanksystem. Wenn man trotzdem eine bestehende Datenbank benutzen will, muss man dies über Anwendungsprogramme realisieren, was Mehraufwand bedeutet.

3.10 Weitere Punkte

In [GRS95] werden drei Workflow-Features genannt, die von Forschern der Informatik zwar als wichtig angesehen werden, für die die Autoren aber noch keinen dringenden Bedarf in der Bioinformatik gefunden haben:

- Arbeitslisten und Rollenzuordnung

- Zeitbasierte Trigger und Deadlines

- Stärkere Integration mit dem Transaktionssystem der Datenbank, um mehrere Workflow-Aktivitäten als eine Transaktion in der Datenbank auszuführen

Es wird allerdings bemerkt, dass man relativ leicht auch in Genlaboren Anwendungsfälle für diese Features finden könne, diese jedoch in der bisherigen Arbeit nicht benötigt wurden. Durch weitere Untersuchungen wollen die Autoren herausfinden, ob diese Funktionalitäten für ihre Anwendungen doch wichtig sind.

4. Workflow-Management-Systeme für die Bioinformatik

In diesem Kapitel werden drei Systeme vorgestellt, die speziell für die Anwendung in der Bioinformatik (Genforschung) entwickelt wurden. Der Schwerpunkt der Designziele ist bei allen drei Systemen unterschiedlich:

- LabBase konzentriert sich auf die Datenmodellierung und Flexibilität,

- BioOpera auf Performanz und dynamische Lastbalancierung,

- METEOR auf die Unterstützung der Zusammenarbeit geografisch entfernter Forschungslabore.

4.1 LabBase

LabBase wurde am Whitehead/MIT Center for Genome Research (CGR) entwickelt. Es ist ein relationales Datenbank-Management-System (DBMS), das mit seinem Datenbankschema und einem umfangreichen API auf die Bedürfnisse der Genomforschung abgestimmt ist. Es bietet Unterstützung für:

- in der Bioinformatik gebräuchliche Datentypen, die üblicherweise nicht von kommerziellen DBMS unterstützt werden,

- häufige Änderungen in den Laborabläufen bzw. Workflows,

- verschiedene Sichten auf die Daten (daten- und ereignisorientiert).

Der in [SRG95] beschriebene „Workflow-Manager“ ist ein API, das von LabBase bereitgestellt wird. Es ermöglicht dem Programmierer, mittels vordefinierter Perl-Skripte Workflows (die Laborprotokollen entsprechen) zu definieren, zu überwachen und zu modifizieren.

Im folgenden Abschnitt 4.1.1 wird ein Beispiel-Workflow skizziert und in 4.1.2 der Begriff „Produktionskette“ erläutert. In 4.1.3 bis 4.1.5 wird das zugrundeliegende Datenmodell erläutert und beschrieben, welche Lösung LabBase für die drei oben genannten Punkte anbietet. Danach wird in den letzten beiden Abschnitten der Workflow-Manager vorgestellt.

4.1.1 Beispiel-Workflow

Um die nachfolgenden Ausführungen zu veranschaulichen, wird in diesem Abschnitt ein Beispiel-Workflow skizziert, der allerdings gegenüber den am CGR eingesetzten Workflows stark vereinfacht ist. Die wesentlichen Schritte sind in Abbildung 3 zu sehen, wobei der Kontrollfluss durch Pfeile dargestellt ist.

Ziel bei diesem Workflow ist, die unbekannte Sequenz eines langen DNA-Fragmentes (z.B. ~5.000 Basen) zu bestimmen. Dies ist nicht in einem Sequenzierungsschritt möglich, da mit heutiger Technik nur etwa bis zu 800 Basen in einem Schritt gelesen werden können. Ein weiteres Problem ist, dass es sehr teuer ist, nach einem Leseschritt von 800 Basen an der zuletzt gelesenen Base mit einem zweiten Schritt fortzusetzen. Eine mögliche Lösung des Sequenzierungsproblems ist, viele Klone des langen DNA-Fragments anzufertigen, von diesen viele kurze Sequenzen (~ 600 Basen) zufällig zu lesen und anhand von Überlappungen die lange Sequenz zusammenzusetzen. Dies erfordert aber sehr viele Lesevorgänge, um sicherzustellen, dass die gesamte Sequenz gelesen wurde und führt ebenfalls zu hohen Kosten.

Abbildung 3: Beispiel-Workflow: Bestimmung einer langen DNA-Sequenz (nach [BSR96])

Eine zweite Möglichkeit ist komplexer, benötigt aber weniger Sequenzierungsschritte. Diese Methode heißt „Transposon-gestütztes Sequenzieren“ (‚transposon-facilitated sequencing’). Ein Transposon ist ein kurzes DNA-Fragment, dessen Sequenz bekannt ist. Es kann in andere DNA-Sequenzen „springen“ und dient zur Markierung einer zufälligen Stelle der langen, unbekannten DNA-Sequenz. Diese Markierung ist leicht aufzufinden und kann benutzt werden, um die Teilsequenzen links und rechts des Transposons zu lesen. Der Workflow besteht aus folgenden groben Schritten. In Klammern werden die korrespondierenden Namen der Instanzen von ‚materials’ bzw. ‚steps’ genannt, die in den nächsten Abschnitten bei der Definition des Datenmodells näher spezifiziert werden.

Op-1. Anfertigung vieler Klone (create_clones) der DNA-Sequenz (clone), die jeweils an einer zufälligen Stelle mit einem Transposon (transposon) markiert werden (pick_tclones). Die entstehenden DNA-Sequenzen werden auch als Transposanten (tclone) bezeichnet.

Op-2. Bestimme die Position des Transposons in jedem Transposanten (t_position). Falls für einen Transposanten die Position nicht bestimmt werden kann, wird er einem Fehler-Status zugewiesen.

Op-3. Aus der Menge der Transposanten, die erfolgreich aus Schritt Op-2 hervorgehen, wird eine Untermenge gebildet (select_tclones), so dass die Abstände zwischen den Transposon-Markierungen höchstens jeweils 600 Basen betragen (da diese Länge in einem Schritt sequenziert werden kann).

Falls eine solche Untermenge nicht existiert, wird zurück zu Op-1 gesprungen, denn es werden mehr Klone benötigt.

Op-4. Nun werden die Teilsequenzen der Transposanten links und rechts der Transposons bestimmt (determine_sequence).

Op-5. Entsprechend der Überlappungen werden die Teilsequenzen aus Op-4 zusammengefügt (assemble_sequence).

Im Detail besteht der Workflow aus sehr viel mehr Schritten, allein das Anfertigen der Klone in Op-1 ist ein Subworkflow. Zum Verständnis der folgenden Ausführungen sollte aber die obige Beschreibung genügen.

4.1.2 Produktionsketten

In Abschnitt 2.5 wurde erläutert, dass Bioinformatik-Workflows zur Klasse der Production-Workflows gehören. Man bezeichnet deshalb diese Workflows auch als Produktionsketten (‚Production Lines’). Im Labor gibt es verschiedene Materialarten (z.B. Klon, Transposon, Transposant – vgl. dazu Abbildungen 3 und 4), wobei die Verarbeitung jeder einzelnen Art in einer eigenen Produktionskette repräsentiert wird. Eine Produktionskette besteht aus mehreren Schritten, in denen die Verarbeitung stattfindet (z.B. Laborexperiment). In jedem Schritt werden Informationen über die Materialien erzeugt (z.B. Sequenz eines Transposants), so dass die Datenstruktur des Materials auf dem Weg durch die Produktionskette mit Werten gefüllt wird.

Ein Schritt kann auch Teil mehrerer Produktionsketten sein, z.B. wenn ein Experiment, das durch einen Schritt repräsentiert ist, mehr als ein Material verarbeitet. Der Beispiel-Workflow aus Abschnitt 4.1.1 ist eine solche Kombination aus zwei Produktionsketten: eine Kette für die Materialart ‚clone’ und eine für ‚tclones’. Der Schritt ‚mapping’ ist nur Teil der ‚tclone’-Produktionskette während ‚assemble_sequence’ zu beiden Ketten gehört. Durch diese Interaktion von Materialarten entsteht ein Netzwerk von Produktionsketten.

Die Repräsentation dieser Produktionsketten erfolgt in LabBase gewissermaßen in zwei Teilschritten: Im Datenbankmodell wird festgelegt, welche Materialarten es gibt, von welchen Schritten sie verarbeitet werden und welche Informationen dabei gespeichert werden. Im Workflow-Manager werden die Reihenfolge der Schritte und die Übergangsbedingungen spezifiziert.

4.1.3 Das Datenmodell

Abbildung 4: Datenmodell LabBase ([BSR96b], S.11)

Abbildung 4 zeigt das Datenmodell von LabBase. Es gibt zwei wesentliche Klassen: die ‚material’-Klasse und die ‚step’-Klasse. Zu beiden gibt es Unterklassen, die die verschiedenen Arten von ‚materials’ und ‚steps’ repräsentieren. Instanzen der ‚materials’-Klasse werden in der Datenbank angelegt, wenn das Labor neue Proben erhält oder in Experimenten erzeugt. Instanzen der ‚step’-Klasse werden angelegt, wenn ein oder auch mehrere ‚materials’ von einer Workflow-Aktivität verarbeitet werden.

Ebenfalls in der Abbildung dargestellt ist die Unterteilung in zwei Ebenen. Die obere, abstrakte Ebene ist in jedem Labor gleich. Die untere Ebene, in der die speziellen Arten von ‚materials’ und ‚steps’ spezifiziert werden, ist konkret und abhängig vom Projekt, für das das Modell erstellt wird. Sie kann sich auch während des Projekts durch Schemaevolution ändern, was wie in Abschnitt 2.4 beschrieben in der Bioinformatik sehr häufig auftritt. Die einzige Anforderung an die untere Ebene ist, dass sie einen ‚create-step’ enthalten muss, der die Erzeugung neuer ‚materials’ repräsentiert. Abbildung 5 zeigt die Definitionen der beiden Klassen ‚material’ und ‚step’ und jeweils drei Beispiele für mögliche Unterklassen.

Materials:

material:

name: string

state: string

clone: ISA material

length: integer

tclone: ISA material

transposon: ISA material

Steps:

step:

who: string

when: string

create: ISA step

material: material

t_position: ISA step

      material: tclone
      left_length: integer
      right_length: integer
      mapping_successful: boolean

determine_sequence: ISA step

material: tclone
l_sequence: dna_sequence

l_start: integer

l_length: integer

r_sequence: dna_sequence

r_start: integer

r_length: integer

sequencing_successful: boolean

Abbildung 5: Beispiele für Definitionen von ‚steps’ und ‚materials’ (nach [BSR96])

Bei der Ausführung von Workflow-Aktivitäten (‚steps’) werden meistens Ergebnisse produziert, zum Beispiel die Länge einer DNA-Sequenz. Die Länge ist semantisch gesehen eigentlich ein Attribut der DNA-Sequenz und man würde erwarten, dass dieses Attribut mit der ‚materials’-Instanz abgespeichert wird. In LabBase werden diese Informationen aber alle mit der ‚step’-Instanz assoziiert, die die Workflow-Aktivität repräsentiert, von der sie erzeugt wurden (vgl. Abbildung 5: r_length). Der Grund dafür ist, dass dieselbe DNA-Sequenz mehrmals vom gleichen ‚step-kind’ verarbeitet werden kann (z.B. um Fehlerraten zu bestimmen) und man dabei nicht nur das zuletzt erzeugte, sondern jedes Ergebnis speichern will. Außerdem ist es aufgrund der Flexibilität der Workflows (die zu häufigen Änderungen der ‚step kind’-Definitionen führt) für spätere Auswertungen essentiell zu wissen, welcher ‚step’ unter welchem Schema die Information erzeugt hat. Nur dann ist deren korrekte Interpretation möglich. Über die ‚involves’-Relation (n:m) kann man zwischen den beiden Klassen navigieren und so zu jedem ‚material’ alle Attribute finden (siehe Abschnitt 4.1.5). Das ‚state’-Attribut von ‚materials’ dient dazu, den Zustand zu speichern, in dem sich die jeweilige Instanz gerade befindet.

Zu den von LabBase bereitgestellten atomaren Datentypen gehören STRING, INTEGER, FLOAT, DATE, DNA_SEQUENCE, BOOLEAN. Außerdem gibt es den atomaren Datentyp MATERIAL, der Referenzen auf ‚material’-Instanzen beschreibt. Als Typkonstruktoren gibt es LIST, TUPLE und SET.

4.1.4 Flexibilität

Im vorigen Abschnitt wurde das Datenmodell beschrieben, wie es der Nutzer von LabBase sieht. Nun wird auf die interne Repräsentation des Datenmodells in LabBase eingegangen, die für die Flexibilität des Datenbankschemas entscheidend ist.

Dazu sei noch einmal hervorgehoben, dass es zu jeder Art von Workflow-Schritt eine korrespondierende Unterklasse von ‚step’ gibt, die für jedes Resultat des Workflow-Schritts (z.B. Labormessung) ein Attribut besitzt (z.B. gemessener Wert). Würde das Datenmodell direkt implementiert, würden Schemaänderungen des Workflows auch immer Schemaänderungen in der Datenbank nach sich ziehen. Um dies zu vermeiden, gibt es in LabBase außer dem beschriebenen dynamischen Datenmodell eine interne Repräsentation, die statisch ist, also nicht durch Workflow-Änderungen beeinflusst wird. LabBase funktioniert dabei als Wrapper, der zwischen dem dynamischen Modell, das die Nutzer sehen, und dem statischen Modell, das implementiert ist, übersetzt.

Intern werden die ‚steps’ nun folgendermaßen repräsentiert: Die Oberklasse ‚step’ hat die Attribute ‚who’ (wer den den Schritt ausführte) und ‚when’ (wann ausgeführt). Jede Unterklasse erbt diese und besitzt ein Attribut, das den Namen der Unterklasse speichert (Attribut ‚step-kind’). Alle anderen Merkmale, die spezifisch für den jeweiligen ‚step-kind’ sind (sich also ändern können), werden nicht etwa als einzelne Attribute gespeichert. Das wäre zu unflexibel, da mit jeder Änderung (z.B. Hinzufügen eines Attributs) eine neue Klasse entstehen würde und damit die Information verloren ginge, welche Versionen zu einem ‚step-kind’ gehören. Eine Migration der Daten aus dem alten in das neue Schema ist ebenfalls nicht möglich, da es für die Interpretation der Daten sehr wichtig ist, unter welcher Workflow-Version die Daten erzeugt wurden. Stattdessen werden die für einen ‚step’ spezifischen Attribute in einer Menge von ‚tag-value’-Paaren gespeichert. Die Tags entsprechen dabei den dynamischen Attributen von ‚materials’ („dynamisch“, weil sie erst während der Verarbeitung entstehen). Sie werden jedoch, wie in 4.1.3 bereits begründet, zusammen mit den ‚step’-Instanzen gespeichert, von denen sie erzeugt wurden. Die statischen Eigenschaften einer ‚material’-Instanz (z.B. der Name) werden mit dem ‚create-step’ der Instanz gespeichert. Versionen von ‚steps’ unterscheiden sich somit in den ‚tag-value’-Paaren. So kann in einer neuen Version eines ‚steps’ ein ‚tag-value’-Paar hinzukommen, wenn ein zusätzliches Ergebnis gespeichert werden soll. Ebenso kann sich der Datentyp eines Attributs bzw. ‚tags’ ändern. Trotz dieser Modifikationen muss das interne Schema nicht verändert werden. Abbildung 6 zeigt die Gegenüberstellung des Datenmodells mit der internen Repräsentation einer ‚step’-Instanz.

Datenmodell:

t-position: ISA step

material: tclone

left_length: integer

right_length: integer

mapping_successful: boolean

Interne Repräsentation:

step123: instance-of step

who: ‘Lincoln’

when: ‘23/jan/1995/14:36:57’

step-kind: ‘t_position’

attribute-names: [material,
left_length, right_length, mapping_successful]

attribute-values: [material456,
1500,
1750,
true]

Abbildung 6: Vergleich Datenmodell – interne Repräsentation einer ‚step’-Instanz (nach [BSR96])

4.1.5 ‚material’-orientierte Sicht

Die beschriebene Datenrepräsentation in LabBase ist ereignisorientiert, d.h. die Informationen über einen ‚step’ sind zusammenhängend gespeichert, während die Informationen zu einem bestimmten ‚material’ über die ‚steps’ verstreut sind. Die ‚material’-orientierte Sicht soll es den Nutzern ermöglichen, Attribute von ‚materials’ abzufragen, ohne zu wissen, von welchen Schritten sie erzeugt wurden (denn dort sind die gesuchten Attribute tatsächlich gespeichert).

Allerdings ist die Definition dieser Sicht nicht trivial, da ‚materials’-Instanzen derselben Klasse unterschiedliche Attribute besitzen können. Das folgt daraus, dass die Attribute einer Instanz erst bei der Verarbeitung eines ‚steps’ „entstehen“, demnach sind die Attribute einer Instanz davon abhängig, von welchen ‚steps’ sie verarbeitet wurde und sogar von welcher Version, da sich die Definition des ‚steps’ ebenfalls ändern kann. Außerdem können wiederholte Experimente mit derselben ‚material’-Instanz zu verschiedenen Ergebnissen führen, wobei das aktuellste Ergebnis zwar von größtem Interesse ist, aber auch die alten nie verworfen werden (z.B. zwecks Bestimmung von Fehlerraten).

Die Idee hierbei ist, dass es bei der Anfrage unwichtig ist, welche Attribute im konkreten Fall mit einer ‚material’-Instanz assoziiert sind. Biologen sind meistens an einem bestimmten Attribut interessiert (z.B. die Länge eines Strangs einer DNA-Sequenz: l_length), deshalb kann einfach die Existenz dieses Attributes in der ‚tag-value’-Menge abgefragt werden. Es kann zum Beispiel vorkommen, dass der Schritt determine_sequence in determine_left_seq und determine_right_seq aufgesplittet wird. Wenn dabei aber die Namen der Attribute beibehalten werden (also l_length in der einen Klasse und r_length in der anderen), so kann das Attribut immer noch über eine Existenzabfrage in allen ‚step kinds’ (zu denen u.a. determine_sequence, determine_left_seq und determine_right_seq gehören) gefunden werden, da es unwichtig ist, welcher Schritt es erzeugt hat. Falls ein Attribut mehrmals gemessen wurde, wird standardmäßig der zuletzt gemessene Wert zurückgegeben.

Der Wert eines Attributes attr von einer ‚material’-Instanz M wird nun ermittelt, indem von allen ‚steps’, die mit der Instanz durch die ‚involves’-Relation verbunden sind und einen Wert für attr besitzen, der zeitlich aktuellste ‚step’ gewählt wird. Dessen Wert V von attr wird zurückgegeben. Diese Regel definiert eine ‚material’-orientierte Sicht der ereignisorientierten Datenbank.

Änderungen von ‚steps’ treten am häufigsten in zwei Varianten auf: (1) Die Menge der zu speichernden Attribute ändert sich, z.B. äußert sich das Hinzufügen eines Attributs darin, dass ein zusätzliches tag-value-Paar aufgenommen wird. (2) Ein komplexer Workflow-Schritt wird in einfachere Teilschritte unterteilt (d.h. aus einer Subklasse von ‚step’ werden mehrere gebildet). Die beschriebene Definition der ‚material’-orientierten Sicht muss in beiden Fällen nicht verändert werden.

4.1.6 Der Workflow-Manager

Im bisher beschriebenen LabBase-Schema können zwar einzelne Schritte und Datenstrukturen von Workflows definiert, aber noch keine Bedingungen bezüglich der Ablaufkontrolle spezifiziert werden. Dies geschieht im Workflow-Manager, dessen Routinen Teil eines API sind, das von LabBase bereitgestellt wird.

Korrespondenz Workflow-Schritt – Perl-Skript

Für jeden Schritt im Labor-Workflow existiert im Workflow-Manager ein korrespondierendes Programm, das die Bedingungen für den Schritt überprüft und die Datenbanktransaktionen behandelt. Für die Implementierung wurde Perl benutzt, vor allem aufgrund der mächtigen String-Matching-Funktionen. Von diesen Perl-Skripten werden einige durch die Nutzer gestartet, andere automatisch.

‚Workflow Description Tables’

Die Beschreibungen der Laborprotokolle werden in externen, flachen Dateien gehalten (‚protocol description files’). Darin befinden sich Tabellen, die eine Produktionskette (entspricht einem Workflow) beschreiben. Zu beachten ist die Konvention, dass eine Produktionskette, wie in 4.1.2 erwähnt, aus einer Folge von Laborschritten besteht, die ein einzelnes LabBase-‚material’ verarbeiten. Die Beschreibung benutzt ein einfaches ‚state-transition-Modell’. In Abbildung 7 ist ein Auszug aus der Datei, die den Workflow für das lange DNA-Fragment (clone) spezifiziert, zu sehen. Eine ähnliche Datei würde man für die Transposanten (tclones) erstellen. Die erste, sehr kurze Tabelle spezifiziert, welches ‚material-kind’ von dem Workflow verarbeitet wird. Die zweite Tabelle nennt alle gültigen Zustände, die angenommen werden können (mit den jeweiligen Variablennamen für die Zustände). Die dritte Tabelle legt die Reihenfolge der Ausführung fest indem alle gültigen Transitionen aufgezählt werden (jeweils spezifiziert durch Ausgangs- und Zielzustand, optional kann in einer dritten Spalte eine zusätzliche Bedingung spezifiziert werden). Diese Tabellennotation ist intuitiv und damit auch für Nutzer ohne tiefe Kenntnis von Programmiersprachen verständlich.

WORKFLOW-MATERIAL BINDING

CLONE S

STATES VARIABLE-ABBREV.

…

waiting_for_create_clones $WFCREATECL

waiting_for_select_tclones $WFSELECTTCL

waiting_for_assemble_seq $WFASSEMBLSEQ

…

TRANSITIONS FROM TO

enter_CLONE $WFCREATECL

create_clones $WFCREATECL $WFSELECTTCL
select_tclones $WFSELECTTCL $WFASSEMBLSEQ

redo_create_clones $WFSELECTTCL $WFCREATECL

…

Abbildung 7: Auszug aus ‚Protocol Description File’ aus LabBase-Workflow-Manager (nach [SRG95])

Perl-API des Workflow-Managers

Aus den oben beschriebenen Zustands- und Transitionstabellen werden zur Ausführungszeit eines Perl-Skripts automatisch LabBase-Anfragen erzeugt, die z.B. den Status eines ‚materials’ überprüfen. Diese Anfragen kann der Anwendungsprogrammierer zu komplexeren Anfragen zusammensetzen und so den Ablauf des Workflow-Schritts, für den das Perl-Skript verantwortlich ist, programmieren. Außer den automatisch erzeugten Queries stehen ihm noch zahlreiche andere Perl-Funktionen zur Verfügung. So kann auch über alle Zustände in einem Workflow iteriert werden oder der Weg einer ‚materials’-Instanz im Workflow-Graphen verfolgt werden.

‚Value Sets’

Im Datenmodell besitzt die Klasse ‚material’ ein Attribut ‚state’. Dies wird weder mit ‚steps’ noch mit ‚materials’ gespeichert, sondern durch sogenannte ‚value sets’. Dabei wird jedem möglichen ‚state’ eine Menge mit eindeutigem Namen zugewiesen, die Referenzen auf alle ‚material’-Instanzen enthält, die sich in dem jeweiligen Status befinden. So enthält zum Beispiel der ‚value set’ waiting_for_blast alle Sequenzen, die als nächstes mittels des BLAST-Algorithmus analysiert werden sollen. ‚Value sets’ bieten somit direkte Unterstützung für die Workflow-Ausführung, da der Zustand einer ‚material’-Instanz sehr schnell bestimmt werden kann.

4.1.7 Bewertung

Mit der Entwicklung von LabBase haben die Forscher am CGR eine sehr flexible Lösung gefunden, die gut auf die Anforderungen in Genlaboren abgestimmt ist. Ihr Ansatz, die Workflow-Informationen vom Datenbankschema zu trennen, führt zu einem System, das äußerst robust gegenüber Workflow-Änderungen ist. Für die meisten Änderungen reicht es aus, kleine Anpassungen in den betroffenen Perl-Skripten vorzunehmen. Gegenüber dem Hinzufügen oder Löschen von Attributen, die mit einem bestimmten ‚step-kind’ assoziiert sind, ist der Workflow-Manager sogar völlig immun.

Weitere Vorteile von LabBase sind, dass das Datenmodell auf die Bedürfnisse der Bioinformatik abgestimmt ist und sowohl eine Daten- als auch Workflow-Sicht möglich sind. Die ‚material’-orientierte Sicht erlaubt es dem Programmierer, Anfragen über die Daten zu stellen ohne den Workflow zu kennen, noch die Namen der ‚steps’ zu kennen, die die Information erzeugten und auch ohne die Workflow-Änderungen zu kennen. Die Definition der ‚material’-orientierten Sicht ist ebenfalls völlig vom Workflow unabhängig, d.h. man benötigt keine neue Definition für andere Workflows. Man beachte, dass die Workflow-Sicht (Event History) der ‚step’-orientierten Sicht entspricht und direkt implementiert ist. Über die ‚involves’-Relation können alle ‚step’-Instanzen zu einer ‚material’-Instanz gefunden und zeitlich geordnet werden.

Ein Nachteil des Ansatzes der Trennung von Datenmodell und Workflow-Definition ist jedoch, dass der Anwendungsprogrammierer die Verantwortung für die Korrektheit der Transaktionen trägt. Er kann zum Beispiel am Ende der Verarbeitung eines Schritts den Aufruf vergessen, der die verarbeitete ‚material’-Instanz in den nächsten Zustand überführt oder aufgrund eines Programmierfehlers eine Transition unter falschen Umständen auslösen. Die Entwickler von LabBase argumentieren allerdings, dass dies nur selten passiert und relativ leicht durch Ad-hoc-Anfragen korrigiert werden kann. Zusätzlich wird durch die Möglichkeit der Definition von Zusatzbedingungen in den Workflow-Beschreibungstabellen die Wahrscheinlichkeit verringert, dass fehlerhafte Übergänge durchgeführt werden.

Des Weiteren ist keine grafische Unterstützung verfügbar (grafische Definition von Workflows, grafischer Workflow-Browser). Dadurch sind komplexe Workflows relativ schwer zu modellieren, denn der Entwickler kann leicht den Überblick verlieren. Die Korrektheit von Schleifen kann ebenfalls nicht überprüft werden, Endlosschleifen können entstehen. Auch die hierarchische Modellierung von Workflows wird nicht unterstützt, obwohl dies eine der Hauptanforderungen aus Kapitel 3 ist.

4.2 BioOpera

Während bei der Entwicklung von LabBase der Entwurf und die Implementierung eines Datenbankschemas im Vordergrund stand, das die Punkte 3.1 bis 3.4 und 3.7 unterstützt, konzentrierten sich die Entwickler von BioOpera auf die Punkte Automatisierung, Performanz, Parallelität der Berechnungen und Systemstabilität im Falle von Hardware-Ausfällen / -Veränderungen (also 3.6 bis 3.8). Im Folgenden wird die Motivation der Entwickler und das Problem beschrieben und anschließend ihr Lösungsansatz mit einer Beurteilung bezüglich der Anforderungen aus Kapitel 3 dargestellt.

4.2.1 Problemstellung

Gegenstand der Betrachtungen sind hier weniger die Labore, in denen die biochemischen Experimente „in Realität“ im Reagenzglas ausgeführt werden, sondern „virtuelle Labore“. Auf in Datenbanken gespeicherten Millionen DNA-Sequenzen werden komplexe Algorithmen angewandt und Informationen gesammelt, um aus der bekannten Primärstruktur (die Sequenz der Aminosäuren) die Sekundärstruktur (dreidimensionale Struktur: α-Helix und β-Blatt) voraussagen zu können. [AB+99] bezeichnen die aufeinander aufbauenden Informationen als „Tower of Information“. Auf die in der Abbildung 8 gezeigten Zwischenschritte soll hier nicht weiter eingegangen werden. Es soll dadurch nur anschaulich werden, dass viele Zwischenschritte nötig sind, bei denen komplexe Algorithmen auf riesige Datenmengen angewendet werden.

Abbildung 8: Tower of Information ([AB+01], S. 1)

Dabei ist weniger die Speicherung der Datenmengen als die Durchführung der Berechnungen selbst das Problem. Brauchbare Ausführungszeiten können nur durch einen hohen Grad an Parallelität erreicht werden. Dabei muss das Gesamtproblem in Teilprobleme zerlegt werden, die Teilprobleme müssen den Rechnern des Computernetzes zugewiesen werden, wobei deren Auslastung beachtet werden muss und manchmal bereits zugewiesene Prozesse von überlasteten Rechnern entfernt und anderen zugewiesen werden müssen. Im Falle von Hardware-Ausfällen oder Software-Fehlern muss das System wieder gestartet werden, verlässlich weiterarbeiten und eventuell aufgetretene Fehler müssen korrigiert werden. In den meisten virtuellen Laboren wird der Hauptteil dieser komplexen Aufgaben manuell erledigt, was sehr zeitaufwändig und fehleranfällig ist.

Das Hauptziel für BioOpera besteht deshalb in der Minimierung der Notwendigkeit von manuellen Eingriffen, um dadurch die Verwaltung und Durchführung langlebiger Berechnungen zu erleichtern. Dies soll erreicht werden durch die Bereitstellung von Mechanismen für

- effizientes Scheduling von Prozessen,

- Auslastung („load balancing“),

- Kontrolle des Fortschritts der Berechnungen,

- Recovery von Hard- und Software-Fehlern,

- Systematisches Speichern von / Zugriff auf Zwischen- und Endergebnisse.

4.2.2 Gewählte Beispielimplementierung

Die Entwickler von BioOpera haben sich ein repräsentatives Beispiel ausgewählt, um die Funktionalität ihres Systems zu überprüfen und weiterzuentwickeln. Datenquelle bildet Swiss-Prot Version 38, eine Datenbank, die 80.000 Aminosäuresequenzen enthält. Referenzprozess ist das sogenannte „all vs. all“-Experiment, bei dem alle Sequenzen aus der Datenbank paarweise miteinander verglichen werden („sequence alignment“). Dieses Experiment wurde gewählt, da es bezüglich der Datenmenge (ca. 3,2·10⁹ paarweise Vergleiche) und der Komplexität des Algorithmus repräsentativ ist. Außerdem ist es laut [AB+99] standardmäßig der erste Schritt, um bei einer gegebenen Menge von Proteinsequenzen etwas über die Evolution, Struktur und Funktion der Biomoleküle herauszufinden.

Zum Vergleich, wie lange solche Berechnungen dauern: Eine Züricher Forschergruppe (Computational Biochemistry Research Group, ETH Zürich) hat während der letzten sieben Jahre die „all vs. all“-Vergleiche von Swiss-Prot Version 27 publiziert. Dabei wurden pro Update die Ergebnisse von etwa 10.000 Sequenzen veröffentlicht, deren Berechnung auf einem Cluster mit 16 Dualprozessorknoten 3 bis 4 Monate dauerte. BioOpera benötigte für alle 80.000 Sequenzen „nur“ 38 Tage, obwohl die Berechnungen mit niedriger Priorität auf stark benutzten Clustern durchgeführt wurden.

4.2.3 Prozessdesign

In BioOpera wird eine Berechnung, wie z.B. „all vs. all“, als Prozess repräsentiert. Ein Prozess wird in BioOpera wie üblich als gerichteter Graph dargestellt, mit den Knoten als Aufgaben. Aufgaben können einzelne Aktivitäten oder Subprozesse sein. Dadurch wird modulares Prozessdesign ermöglicht, wie es in Abschnitt 3.1 im Punkt „Unterstützung komplexer Workflows“ gefordert wurde. Es wird auch ein gewisses Maß an dynamischer Workflow-Modifikation ermöglicht, indem Subprozesse erst instanziiert werden, wenn sie gestartet werden („late binding“). Man kann also in einem laufenden Prozess die noch nicht begonnenen Subprozesse noch verändern.

Abbildung 9 zeigt ein einfaches Schema der Implementierung des „all vs. all“-Prozesses in BioOpera. Aktivitäten werden durch Rechtecke dargestellt und sind an den Aufruf eines externen Programms gebunden. Dicke Kanten repräsentieren den Kontrollfluss und dünne Kanten den Datenfluss.

Abbildung 9: Der ‚all vs. all’-Prozess in BioOpera ([AB+99] S.4)

4.2.4 Architektur und Funktionalität

BioOpera wird von den Entwicklern als Prozessunterstützungssystem bezeichnet, das benutzt werden kann, um komplexe Bioinformatik-Berechnungen in einer heterogenen Rechnerumgebung zu definieren, auszuführen, zu kontrollieren und zu verwalten. Es minimiert das nötige manuelle Eingreifen und die Rechenzeit.

Abbildung 10 zeigt die Architektur von BioOpera. Der Navigator kontrolliert die Prozessausführung. Diese Komponente des BioOpera Servers ist vergleichbar mit einer Workflow-Engine und entscheidet, welche(r) Schritt(e) als nächstes ausgeführt werden und sendet die Informationen an den Dispatcher, der der Aktivität einen bestimmten Knoten im Cluster und die Ausführung einer Anwendung zuweist. An jedem Knoten ist ein „Program Execution Client (PEC)“ installiert, der die Auslastung des Knotens überwacht und Fehler an den BioOpera Server meldet. Der PEC ist in Java geschrieben, ist somit plattformunabhängig und erlaubt heterogene Cluster. Nachdem eine Aufgabe beendet ist, werden die Ergebnisse über den PEC an den Server übermittelt. Das „recovery module“ aktualisiert die Datenbank, in der alle aufgetretenen Ereignisse gespeichert werden (entspricht Workflow-Tracking aus 3.3). Dann erhält wieder der Navigator die Kontrolle und sucht nach der nächsten auszuführenden Aufgabe.

Der größte Teil der prozessbezogenen Informationen wird persistent in der Datenbank gespeichert. Dazu gehören zum Beispiel Start- und Endzeiten, Knotenkapazitäten, Auslastung jedes Knotens und Knotenausfälle. Die persistente Speicherung ist aus zwei Gründen sehr wichtig. Erstens, um den Nutzern die Möglichkeit zu geben, den Status der Berechnungen zu verfolgen und, wenn nötig, einzugreifen. Zweitens sind die Informationen wichtig, um die Auslastung der Knoten zu bestimmen, dynamische und automatische Scheduling-Entscheidungen treffen zu können und – besonders wichtig – nach einem Ausfall von Hard- oder Software die Prozessausführungen ohne Datenverlust fortzusetzen.

Abbildung 10: Architektur von BioOpera ([AB+99], S.5)

4.2.5 Resultate

Das System wurde mit zwei Ausführungen des all. vs. all Experiments getestet. Das erste Mal mit einem Cluster, der auch von anderen Nutzern stark genutzt wurde. Ziel dieses Tests war es, die Stabilität von BioOpera in einer realen Rechnerumgebung zu untersuchen, in der es unvorhergesehene Ereignisse gibt. Das zweite Experiment wurde auf einem Cluster durchgeführt, der allein dem BioOpera System zur Verfügung stand. In beiden Fällen war nur minimales Eingreifen nötig. Nach Ausfällen der Hardware oder Wartungsarbeiten setzte der BioOpera Server automatisch die Prozesse fort, ohne bereits fertige Berechnungen zu verlieren.

Wie weiter oben schon erwähnt, wurde auch eine erhebliche Verkürzung der Rechenzeit gegenüber vergleichbaren Projekten erzielt: BioOpera benötigte lediglich 38 Tage unter Benutzung von bis zu 40 Prozessoren. Eine grafische Darstellung des ersten Experiments und der aufgetretenen Ereignisse ist in Abbildung 11 zu sehen. Dabei ist es eindrucksvoll, wie viele unvorhergesehene (z.B. Ausfall eines Clusters, Ereignis 3) aber auch geplante (z.B. Wartung des Servers, Ereignis 7) Ereignisse, die den normalen Ablauf stören, von BioOpera fehlerfrei und automatisch behandelt werden.

Abbildung 11: Lebenszyklus der Ausführung von ‘all vs. all’ ([AB+01], S.7)

Verglichen mit den Anforderungen aus Kapitel 3 kann man sagen, dass BioOpera viele der genannten Punkte erfüllt. Aufgrund der Zielstellung der Entwickler wurde für die Punkte Workflow-Ausführung, Performanz und Stabilität mit dem oben beschriebenen Konzept eine vielversprechende Lösung gefunden. Eine grafische Oberfläche für die Workflow-Modellierung soll in Zukunft angeboten werden, momentan müssen die Workflows jedoch noch über eine systemeigene Sprache definiert werden. Den Entwicklern ist bewusst, dass das GUI ein sehr wichtiges Element ist, da Biologen kaum mit Programmiersprachen vertraut sind und eine grafische Oberfläche die Benutzbarkeit stark verbessert. Ebenso ist die Bereitstellung einer Workflow-Bibliothek geplant, um die komponentenartige Entwicklung von Workflow-Definitionen zu ermöglichen.

Die einzigen Anforderungen aus Kapitel 3, auf die [AB+99] bei der Beschreibung von BioOpera kaum eingehen, sind die Unterstützung komplexer Datenstrukturen (3.1) und die Behandlung der Problematik des Datenbankdesigns, die durch den raschen Fortschritt mit vielen Prozessänderungen entsteht (3.7). Es bleibt unklar, ob diese Herausforderungen bei dem jetzigen Entwicklungsstand von BioOpera, das noch ein Prototyp ist, bereits berücksichtigt wurden.

4.3 METEOR

METEOR ist ein WfMS, das am ‚Large Scale Distributed Information Systems (LSDIS)’ Labor der Universität Georgia entwickelt wurde. Es richtet sich an Anwendungsgebiete, bei denen verteiltes Workflow-Management benötigt wird. In [HM+99] wird ein Prototyp beschrieben, der für ein Bioinformatik-Projekt (Genom-Sequenzierung) entwickelt wurde.

4.3.1 Geografisch verteiltes Workflow-Management

Bei Genom-Sequenzierungs-Projekten fallen hohe Kosten an, z.B. für Laborausstattung und spezialisiertes Personal. Deshalb arbeiten häufig mehrere Forschungsinstitute zusammen, um die Kosten zu verteilen und ihre Expertise zu bündeln. Es kann zum Beispiel sein, dass sich mehrere Forschungsinstitute zusammenschließen und eines davon das Klonen von DNA für alle Partner übernimmt. Da also einzelne Aktivitäten von Workflows von verschiedenen Instituten ausgeführt werden, kann die Ausführung eines Workflows mehrere Forschungszentren einbeziehen.

Daraus ergeben sich besondere Anforderungen an ein WfMS:

- die Ausführung von Anwendungen auf verschiedenen Systemen muss koordiniert werden,

- die Daten müssen zwischen den Systemen ausgetauscht werden,

- andere Anwendungen müssen integriert werden (z.B. ein BLAST-Programm für Sequenz-Alignment),

- Bereitstellung von Recovery-Mechanismen (z.B.: Aufgrund des Ausfalls einer Wf-Engine wird ein Teil-Workflow nicht ausgeführt. Trotzdem muss die korrekte Weiterausführung des Workflows garantiert werden.).

4.3.2 Funktionalitäten des Prototyps

METEOR erfüllt viele Anforderungen aus Kapitel 3. So enthält es grafische Werkzeuge, um die Definition von Workflows zu ermöglichen, Arbeitslisten anzuzeigen usw. Aus der grafischen Spezifikation eines Workflows kann auch automatisch Code generiert werden, somit ist es möglich, dass auch Anwender Workflows definieren, die keine Programmiersprache kennen. Interaktion mit Anwendungen ist zum Beispiel über Formulare möglich. Subworkflows und hierarchische Modellierung werden unterstützt. Die semi-automatisierte Arbeitsweise der Labore wird ebenso unterstützt wie die Einbindung von Analyse-Programmen wie z.B. BLAST. Grafische Interaktion mit Anwendungsprogrammen auf einem Server ist mittels des X-Windows-Systems möglich, einzige Voraussetzung ist ein X-Server auf dem Client.

Der Ansatz der Datenrepräsentation ist anders als in LabBase. Im METEOR-Prototypen sind alle relevanten Attribute mit dem Datenobjekt assoziiert und während das Objekt Schritt für Schritt vom Workflow verarbeitet wird, werden diese Attribute ausgefüllt. Die Menge der Daten, die auf diese Weise mit einem Objekt assoziiert werden, liegen in der Größenordnung von 500 kB bis 200 MB. Wenn diese Daten von nachfolgenden Workflow-Schritten, deren Verarbeitung in anderen Instituten erfolgt, gebraucht werden, müssen sie über das Netzwerk transportiert werden. Dies stellt eine der größten Herausforderungen dar. Die Performanz wird von den Entwicklern als gut beschrieben, solange sich Client und Server im selben Netzwerk befinden. Ansonsten könnten Probleme auftreten und eine sehr hohe Bandbreite erforderlich machen.

5. Zusammenfassung

Es wurde gezeigt, dass die Bioinformatik besondere Anforderungen an Workflow-Management-Systeme stellt, die von den meisten kommerziellen Systemen noch nicht erfüllt werden. Dies betrifft sowohl Punkte, die allgemein für Production-Workflows gelten (z.B. Performanz, Verfügbarkeit) als auch Punkte, die spezifisch für die Bioinformatik sind. Dabei ist zum einen die Konzentration auf DNA-Strukturen zu nennen, da sie sich stark von Formularstrukturen, wie sie in administrativen Systemen gebraucht werden, unterscheiden. Zum anderen spielt die Flexibilität der Workflows eine große Rolle, da sie sich auf nahezu alle Komponenten eines WfMS auswirkt und bei deren Entwicklung beachtet werden muss.

Die Vorstellung der drei Systeme hat demonstriert, dass es vielversprechende Prototypen gibt. Allerdings löst jedes System zwar gewisse Probleme, hatte aber auch noch beträchtliche Mängel. Ein System, dass so flexibel wie LabBase ist, so performant wie BioOpera arbeitet und dazu noch Mechanismen für verteiltes Workflow-Management bietet, hätte die wichtigsten Anforderungen erfüllt.

Literaturverzeichnis

AB+99 Alonso, G.; Bausch, W.; Hallett, M.; Kahn, A.; Pautasso, C. (1999): BioOpera: Managing Large-Scale Computations in Bioinformatics. [ETH Zürich]

AB+01 Alonso, G.; Bausch, W.; Pautasso, C.; Kahn, A. (2001): Dependable Computing in Virtual Laboratories. Proc. of the 17^th International Conference on Data Engineering (ICDE2001), Heidelberg, Germany, April 2001.

BSR96 Bonner, A.J.; Shrufi, A.; Rozen, S. (1996): LabFlow-1: a Database Benchmark for High-Throughput Workflow Management. Proceedings of the 5^th Int. Conference on Extending Database Technology (EDBT96), Avignon, France, März 1996.

http://www.db.toronto.edu:8020/people/bonner/bonner.html

Al00 Allen, R.: Workflow: An Introduction. Workflow Handbook 2001, Fischer, L. (Hrsg.),Workflow Management Coalition (WfMC), 15-38, 2000.

GHS95 Georgakopoulos, D.; Hornick, M.; Sheth, A.: An overview of workflow management: From process modelling to infrastructure for automation. Jounral on Distributed and Parallel Database Systems, 3(2):119-153, April 1995

GRS95 Goodman, N.; Rozen, S.; Stein, L.(1995): Workflow Management Software for Genome-Laboratory Informatics. From a proposal to the National Institutes of Health.

HM+99 Hall, D.; Miller, J.; Arnold J.; Kochut, K.; Sheth, A.; Weise, M. (1999): Using Workflow to Build an Information Management System for a Geographically Distributed Genome Sequencing Initiative.

LGG01 Luscombe, NM; Greenbaum D.; Gerstein M: What is bioinformatics? An introduction and overview. IMIA 2001 Yearbook.

http://bioinfo.mbb.yale.edu/~nick/bioinformatics/

RM00 Rahm, E.; Müller, R. (2000): Vorlesung Workflow-Management-Systeme. Universtität Leipzig, Wintersemester 2000/2001.

SP02 Swiss-Prot: http://www.expasy.ch/sprot/relnotes/relstat.html (02.01.2002)

SRG95 Stein,L.; Rozen, S.; Goodman, N. (1995): Managing Laboratory Workflow with LabBase. Proc. of the 1994 Conference on Computers in Medicine (CompMed94). World Scientific Publishing Company, 1995.