Eine Bewertung von Hardwaresystemen, die sich am besten für die Suche in der Bioinformatik eignen Forschungspapier

Words: 7361
Topic: Computerwissenschaft

Einführung

Nach der Definition des Merriam-Webster-Wörterbuchs ist Bioinformatik die Sammlung, Klassifizierung, Speicherung und Analyse biochemischer und biologischer Informationen mit Hilfe von Computern, insbesondere in der Molekulargenetik und Genomik. Neben Innovationen in der Hardware-Architektur können auch Innovationen im Bereich der Vernetzung eingesetzt werden, um die bioinformatische Suche zu erleichtern.

BLAST steht für “Basic Local Alignment Search Tool”, ein vom National Center for Biotechnology Information (NCBI) entwickeltes Tool, das Wissenschaftlern bei der Analyse von DNA- und Proteinsequenzen helfen soll (Chattopadhyay A. et.al.). Eine öffentliche Version dieses Tools kann über das Internet oder als Download genutzt werden. Die hohe Nachfrage, die umfassende Verfügbarkeit und die allgemeine Beliebtheit von BLAST haben zu einer uneinheitlichen Leistung der Benutzer geführt.

Um die Leistung zu verbessern, bauten Studenten der Computer Science Bioinformatics Group an der University of South Dakota einen BLAST-Cluster aus überzähligen Desktop-PCs zusammen, die zur Implementierung einer parallelen Version des BLAST-Tools auf einem Linux-Cluster verwendet wurden. Dies führte zu einer spürbaren Verbesserung der Suchleistung für eine viel kleinere Gruppe von Forschern. BLAST kann auf einem Linux-Rechner installiert werden, auf dem ein Apache-Webserver läuft. Wenn Benutzer Abfragen an BLAST stellen, wird ein Perl-Skript aufgerufen, das auf der Grundlage der in das Abfrageformular eingegebenen Parameter den entsprechenden Job erstellt. Dieser Job wird an Open PBS weitergeleitet, um ausgeführt zu werden, je nach der verwendeten Planungsrichtlinie und der Verfügbarkeit der Knoten.

Die Bioinformatik hat sich aufgrund ihrer Bedeutung für die Wissenschaft zu einem wichtigen Fachgebiet entwickelt. Wissenschaftler verlassen sich auf diese Disziplin, um eine effiziente und zuverlässige Methode für die Analyse von DNA- und Proteinsequenzen zu erhalten. Das wichtigste Suchwerkzeug in diesem Bereich ist BLAST, für das viele andere Software- und Hardwarelösungen entwickelt wurden, um seine Funktionen besser zu nutzen und zu optimieren.

Zu den verfügbaren Lösungen für die optimierte Suche in Bioinformatik-Datenbanken über das Internet gehören beispielsweise die Optionen von CLC Bio, einschließlich Bioinformatics Cell und Cube, und der Systolic Accelerator for Molecular Biological Applications (SAMBA), die beide den Smith-Waterman-Algorithmus optimal nutzen, sowie die European Molecular Biology Open Software Suite (EMBOSS). Bei den EMBOSS-Dienstprogrammen handelt es sich um ein kostenloses Open-Source-Softwarepaket, das speziell für die Bedürfnisse von Molekularbiologen entwickelt wurde, da es für die Verarbeitung und Formatierung einer Vielzahl von Daten ausgelegt ist und auch den Abruf von Sequenzdaten über das Internet ermöglicht. Zu den weiteren Optionen, die im Thin-Bereich erforscht wurden, gehören Storage Area Networks, Grid Computing, Multi-Core-CPUs und sogar Cluster aus veralteten Computern.

BLAST Sequenzanalyse & Suchwerkzeug

Die beispiellose Entwicklung auf dem Gebiet der modernen biologischen Forschung hat zu einer Beschleunigung der intensiven biologischen Sequenzvergleichs- und Analyseaufgaben geführt. Der Vergleich von Nukleotid- oder Proteinsequenzen aus demselben oder aus verschiedenen Organismen ist eine sehr wichtige Anforderung in der modernen Molekularbiologie. (Madden T., 2003). Die Identifizierung und Verfolgung der Funktion neu sequenzierter Gene, die Vorhersage genetischer Entwicklungen und die Erforschung evolutionärer genetischer Beziehungen und Funktionen sind im Bannkreis des biologischen Sequenzvergleichs und der Analyse keine Wunder mehr.

Das gesamte Genom kann nun sequenziert und die Ähnlichkeiten zwischen den Sequenzen können gesucht und festgestellt werden, was schließlich dazu beitragen kann, die Funktion von proteinkodierenden und transkriptionsregulierenden Regionen in der genomischen DNA vorherzusagen (Korf et.al., 2006). Ein solches Suchwerkzeug, das von biomedizinischen Forschern am häufigsten verwendet wird, ist das Basic Local Alignment Search Tool (BLAST), das für die Verwendung mit verschiedenen Abfragesequenzen gegen unterschiedliche Datenbanken angepasst werden kann (Altschul et.al., 1990).

Dieses benutzerfreundliche Tool wurde vom NCBI (National Center for Biotechnology Information) entwickelt und erstmals 1990 veröffentlicht. Das NCBI ist eine Abteilung des National Institute of Health in Maryland und wurde 1988 per Gesetz gegründet. Dieses Institut fungiert als nationales Ressourcenzentrum für Molekularbiologie, zu dessen Hauptaufgaben die Einrichtung öffentlicher Datenbanken, die Durchführung von Forschungsarbeiten im Bereich der Computerbiologie, die Entwicklung von Instrumenten zur Analyse von Genomdaten und die Verbreitung biomedizinischer Informationen gehören. Das NCBI ist der autorisierte Verwalter der Genomsequenzdatenbank, der biomedizinischen Forschungsdatenbanken und -artikel sowie anderer biotechnologischer Informationen.

Dieses Institut speichert die Genomsequenzdaten in der bekannten Computerdatenbank GenBank, während andere Forschungsdaten und -artikel in zwei netzbasierten Informationsbibliotheken gespeichert werden, die als PubMed Central und Pubmed bekannt sind (siehe Madden T., 2003). Es gibt eine beliebte Suchmaschine, die Entrez-Suchmaschine, die die Suche nach Informationen und Datenbanken effizienter gestalten kann. Dieses Tool hilft bei der Suche nach hochrangigen Sequenzalignments zwischen der Abfragesequenz und Sequenzen in der Datenbank, indem es einen heuristischen Ansatz verwendet, der dem Smith-Waterman-Algorithmus entspricht (siehe Robert R. et al., 2006).

Große Genomdatenbanken wie die GenBank können mit dem Smith-Waterman-Verfahren nicht effizient durchsucht werden, da es nicht schnell genug ist, um solch große Datenbanken zu durchsuchen. Dies kann jedoch mit dem BLAST-Algorithmus erreicht werden, der 50-mal schneller sein kann als der Smith-Waterman-Ansatz, sofern ein heuristischer Ansatz verwendet wird. BLAST-Programme sind für ihre Schnelligkeit, Genauigkeit und ständige Innovation bekannt.

BLAST – Funktionsweise und Ausführung

BLAST ist die beliebteste und am häufigsten verwendete Suchmaschine im Bereich der modernen Bioinformatik. Seine einfachen Anwendungsprotokolle und seine Anpassungsfähigkeit an eine Vielzahl von Datenbanken machen es zu einer automatischen Wahl für die Fachleute der Biotechnologie (NCBI, 2003). Dieses Tool wurde seit seiner Veröffentlichung im Jahr 1990 kontinuierlich weiterentwickelt und entwickelte sich allmählich zum am häufigsten verwendeten Bioinformatik-Tool für die Sequenzsuche. Unter Verwendung einer Abfragesequenz und einer Sequenzdatenbank als Eingaben durchsucht BLAST alle Entitäten in der Datenbank nach jenen mit einer hohen Punktzahl für die Ausrichtung auf die Abfrage, wobei die Deletion, Insertion und Substitution beim Sequenzvergleich erlaubt sind und die Ausrichtungswerte statistisch und heuristisch auf der Grundlage einer von Experten festgelegten Bewertungsmatrix bestimmt werden (Archuleta J. et.al., 2007).

BLAST führt nur lokale Angleichungen durch und verwendet ein heuristisches Programm als Algorithmus, der es ermöglicht, eine Abkürzung zu nehmen, um den Suchvorgang schneller durchzuführen. Durch lokales Alignment kann eine mRNA mit einer genomischen DNA abgeglichen werden, die für die Genomzusammensetzung und -analyse benötigt wird. Für die Ausführung eines Suchvorgangs muss der Benutzer bestimmte Eingabeinformationen wie Sequenzen, bevorzugte Datenbank, Wortgröße, Erwartungswert und andere angeben.

Sobald die Eingaben vorliegen, beginnt BLAST mit dem Aufbau einer Nachschlagetabelle aller Wörter, in der diese in Kurzformen oder kurzen Teilsequenzen zusammen mit den ähnlichen oder benachbarten Wörtern in der Abfragesequenz eingeordnet werden (siehe Lipman & Pearson, 1985; Lin Qi, 2005). Die Sequenzdatenbank wird dann nach den spezifischen Suchwörtern durchsucht, die bei Feststellung einer Übereinstimmung verwendet werden, um lückenlose und lückenhafte Erweiterungen dieses Wortes zu initiieren. Es sei darauf hingewiesen, dass BLAST die Datenbankdateien (GenBank-Dateien) nicht direkt selbst durchsucht, sondern Sequenzen in die BLAST-Datenbank einstellt.

Auf diese Weise wird jeder Eintrag in zwei Dateien aufgeteilt, von denen die eine nur die Header-Informationen und die andere nur die Sequenzinformationen enthält, die schließlich vom Algorithmus verwendet werden. Wenn BLAST im Standalone-Modus läuft, kann die Datendatei lokale Daten, private Daten und die NCBI-Datenbanken enthalten, die leicht heruntergeladen werden können. Es kann auch eine Kombination aus lokalen und privaten Daten vorliegen. Nach der Nachschlageoperation stellt der Algorithmus das beste Alignment für jedes Abfrage-Sequenz-Paar zusammen und übergibt diese Information an eine SeqAlign-Datenstruktur (ASN.1), wie in Abbildung 1 unten dargestellt.

Nachdem eine ähnliche Sequenz wie die Abfrage gefunden wurde, prüft BLAST, ob das Alignment gut ist und ob es ausreicht, um eine mögliche biologische Beziehung herzustellen. BLAST verwendet statistische Verfahren, um für jedes Alignment-Paar einen Bitscore und einen Exped-Wert (E-Wert) zu ermitteln. Der Bitscore gibt einen Hinweis darauf, wie gut das Alignment ist. Je höher die Punktzahl, desto besser ist das Alignment (Lipman & Pearson, 1985; Lin Qi, 2005).

Die Bit-Scores aus verschiedenen statistischen Alignments, die mit unterschiedlichen Scoring-Matrizen abgeleitet wurden, können auch durch Normalisierung verglichen werden. Darüber hinaus stellt der E-Wert die statistische Signifikanz eines gegebenen paarweisen Alignments, die Größe der verwendeten Datenbank und das verwendete Scoring-System dar. Ein Treffer mit einem niedrigeren E-Wert zeigt an, dass der Treffer signifikanter ist. Beträgt der E-Wert eines Sequenzalignments beispielsweise 0,05, so hat diese Ähnlichkeit eine Chance von 5 zu 100 (d. h. 1 zu 20), allein durch Zufall aufzutreten. Statistisch gesehen mag dies ein guter Wert sein, biologisch gesehen ist er jedoch nicht unbedingt aussagekräftig, weshalb bei der Sequenzanalyse die “biologische Signifikanz” bestimmt werden muss (Casey R.M., 2005).

Das vollständige BLAST-Suchwerkzeug ist ein Paket von fünf Programmen, das blastn, blastp, blastx, tblastn und tblastx umfasst. blastn und blastp. Diese fünf Programme helfen bei der Durchführung einer Nukleotid- oder Peptidsequenzsuche in einer Sequenzdatenbank. Vor allem blastx und tblastn können eine Sequenzsuche des einen Typs mit einer Datenbank des anderen Typs durchführen. Dies ist möglich, da Nukleotid- und Peptidsequenzen in lebenden Zellen ineinander übersetzt werden können. Das heißt, eine Nukleotidsequenz kann in eine Peptidsequenz übersetzt und dann mit einer Datenbank von Peptidsequenzen verglichen werden und umgekehrt. Interessanterweise hebt sich tblastx von allen vier oben genannten Programmen ab.

Tblastx veranlasst die Übersetzung von sechs Frames sowohl für die Abfrage als auch für die Datenbankentitäten, bevor die eigentliche Vergleichsaufgabe gestartet wird. Alle diese fünf Programme sind in eine einzige Schnittstelle integriert und werden als eine Einheit angeboten. Das NCBI hat diese fünf Programme in eine einzige Schnittstelle integriert, die allgemein als Blastall bekannt ist und dem Benutzer den Zugang zu allen fünf verschiedenen Vergleichsprogrammen erleichtert (Mount D.W., 2004).

BLAST ist das am weitesten verbreitete Bioinformatik-Tool zum Vergleich unbekannter genomischer oder aminosäurehaltiger biologischer Sequenzen (Abfrage) mit bekannten Sequenzen, die bereits in der entsprechenden Datenbank enthalten sind. Dieses Tool bezieht sich in etwa auf den Smith-Waterman-Algorithmus speziell für die lokale Sequenzausrichtung, was zu einem Geschwindigkeitszuwachs von 10100x führt. Dieser Geschwindigkeitszuwachs geht auf Kosten einer gewissen Empfindlichkeit des BLAST-Tools. Es gibt verschiedene Möglichkeiten, wie das Problem der BLAST-Geschwindigkeit angegangen werden kann (Archuleta J. et.al., 2007). Es gibt bereits einige aufkommende Computer-Hardware- und Software-Lösungen, um dieses Problem zu lösen.

BLAST- Arbeitsablauf & Cluster

BLAST ist ein Sequenzabgleichsverfahren, mit dem eine Proteinsequenz “seq” in einer Datenbank mit bekannten Proteinen auf Ähnlichkeiten überprüft werden kann. Es wird erwartet, dass Proteine mit ähnlichen Sequenzen auch ähnliche Eigenschaften haben. Schließlich werden die Ergebnisse in ein CSV- und ein binäres Format konvertiert, um sie mit Javawrap weiterzuverarbeiten (siehe Aleksander et al., 2007).

Das vom National Center for Biotechnology Information (NCBI) entwickelte Basic Local Alignment Search Tool (BLAST) ist das am weitesten verbreitete bioinformatische Sequenzsuch- und Analysewerkzeug. Da BLAST eine große Anzahl von Nutzern hat, die sich über die Website des NCBI verbinden, und es wahllos verwendet wird, besteht die Gefahr, dass es früher oder später zu Leistungsschwankungen kommt. Um dieses Risiko auszuschalten, hat die University of South Dakota (USD) eine parallele Version des BLAST-Tools mit einem Linux-Cluster implementiert, dessen Schnittstelle aus einer Kombination von frei verfügbarer Software besteht. Dieser BLAST-Cluster, der alte oder überzählige PCs verwendet und sich an eine kleine Gruppe von Forschern wendet, hat den Suchprozess verbessert (Mark Schreiber, 2007).

Hier wurden die von der Open Cluster Group entwickelten Open Source Cluster Application Resources (OSCAR) implementiert. Dieses OSCAR verbessert die Clusterberechnung, indem es die gesamte für die Erstellung eines Linux-Clusters erforderliche Software in einem Paket bereitstellt. Dadurch lassen sich die Installation, die Wartung und sogar die Nutzung der Cluster-Software automatisieren. Der BLAST-Cluster verwendet WWW BLAST mit einer Webschnittstelle, die die Benutzerfreundlichkeit des Clusters insgesamt verbessert hat.

Es wurde jedoch eine Verbesserung der Gesamtleistung festgestellt, wenn mpiBLAST verwendet wurde (Bowers & Ludascher, 2005). Dieses mpiBLAST kann Abfragen parallel ausführen und dadurch die Leistung von BLAST verbessern. Dieses Tool basiert auf dem Message Passing Interface (MPI), einem weit verbreiteten Softwaretool, das für die Entwicklung paralleler Programme verwendet wird. mpiBLAST bietet die gesamte Software, die für parallele BLAST-Abfragen erforderlich ist.

Die BLAST-Suche beginnt mit einem webbasierten Abfrageformular. Stapelverarbeitung und Auftragsplanung werden von WWWBLAST nicht unterstützt. Diese Aufgaben werden von OpenPBS und Maui übernommen, die in der OSCAR-Software-Suite enthalten sind. OpenPBS ist ein flexibles Batch-Queuing-System, das ursprünglich für die NASA entwickelt wurde, und Maui ist das Add-on, das die Fähigkeiten von OpenPBS erweitert, indem es eine umfassendere Auftragskontrolle und Zeitplanungspolitik ermöglicht (Oinn, et.al., 2005).

Nach der Übermittlung einer Anfrage durch den Benutzer erscheint ein Perl-Skript, das einen einmaligen Auftrag mit den Parametern aus dem Anfrageformular erstellt. Das OpenPBS-Programm ist für die Ermittlung der Verfügbarkeit des Knotens und die anschließende Ausführung des Auftrags zuständig. Danach wird eine Local Area Multicomputer (LAM)-Software gestartet, die über eine Daemon-basierte Laufzeitumgebung auf Benutzerebene verfügt. Der LAM ist im OSCAR-Installationspaket enthalten und stellt die meisten der vom MPI-Programm benötigten Dienste bereit. Ein mpirun-Befehl führt die Abfrage aus und sammelt die Ergebnisse für jeden Knoten, und derselbe Befehl wird auch von OpenPBS ausgeführt (siehe Mount D.W., 2004). Schließlich werden alle Ergebnisse von WWWBLAST an den Browser zurückübertragen und den Nutzern präsentiert.

Abbildung 3 zeigt die verschiedenen Phasen, die eine Abfrage durchläuft, sobald sie über das Internet übermittelt wird. Nachdem WWWBLAST eine Anfrage aus dem Internet erhalten hat, sendet es einen Auftrag an OpenPBS. OpenPBS startet den Auftrag mit mpirun und schließlich werden die Ergebnisse von WWWBLAST formatiert. Für die Durchführung paralleler BLAST-Suchen wird die Implementierung der Cluster-Technologie notwendig. Ein paralleler BLAST-Cluster beginnt nach einer anfänglichen Konfiguration zu arbeiten, im Gegensatz zu anderen gängigen Tools, die mit Standardinstallationen arbeiten.

Die Einrichtung des Clusters wird durch eine Anwendung namens “OSCAR” (Open Source Cluster Application Resources) erleichtert, die mit allen notwendigen Programmen und Protokollen für die Inbetriebnahme des Clusters ausgestattet ist (siehe Zhang H., 2003). Im Folgenden wird ein kurzer Überblick über die verschiedenen Plattformen und Komponenten gegeben, die den parallelen BLAST-Cluster bilden:

Smith-Waterman-Algorithmus

Einer der am häufigsten verwendeten Algorithmen für den lokalen Sequenzabgleich ist der Smith-Waterman-Algorithmus. Beim Sequenzalignment geht es darum, ähnliche Regionen zwischen zwei Nukleotid- oder Proteinsequenzen zu ermitteln. Bei diesem Algorithmus wird nicht die gesamte Sequenz betrachtet, sondern es werden Segmente aller möglichen Längen verglichen und schließlich das Ähnlichkeitsmaß optimiert.

Das Hauptziel des Smith-Waterman-Algorithmus ist die Berechnung der Editierdistanz zwischen zwei Sequenzen (entweder DNA oder Protein) nach einem dynamischen Programmierungsansatz (Smith & Waterman, 1981), und dies wird durch die Erstellung einer speziellen Matrix für die Zellen erreicht, um die Kosten für die Änderung einer Teilsequenz der einen in die Teilsequenz der anderen anzugeben. Dieser Algorithmus schreitet unter Berücksichtigung der Editierabstände der Teilsequenzen voran und erweist sich damit als effiziente Methode zum Vergleich von Sequenzen. Der ursprüngliche Algorithmus, wie er von Smith und Waterman konzipiert wurde, hat einige inhärente Komplexitäten, die das Erreichen des Ziels erschweren können.

Die Hauptfunktion dieses Algorithmus ist die Ähnlichkeitssuche zwischen einer Nukleotid- oder Proteinsequenz von Interesse und Sequenzen in einer Datenbank. Es gibt mehrere Gründe für die Aufnahme dieser Suchaktivität, darunter einige (siehe Pearson, 1991)

Die Identifizierung guter Alignments zwischen Sequenzen, die nur entfernt miteinander verwandt sind, kann schwierig sein. Es gibt Bereiche mit geringer Ähnlichkeit, in denen es schwierig sein kann, gute Alignments zu identifizieren, und daher ist es am klügsten, sich auf die Suche nach lokalen Alignments zu konzentrieren, anstatt auf die globalen. Die gezielte Suche nach lokalen Alignments bietet die Möglichkeit, auch zwischen Sequenzen, die Regionen mit genetischen Variationen enthalten, nach Homologie zu suchen (Smith & Waterman, 1981). Dieser Algorithmus sucht nach Homologie durch den Vergleich von Sequenzen. Der Vergleich von Sequenzen mit Hilfe lokaler Alignments hat Vorrang vor der Schätzung der Gesamtzahl der Alignments und der Identifizierung der besten Alignments, die schließlich die Zuverlässigkeit und Relevanz der erhaltenen Daten beeinflussen (Pearson & Lipman, 1988). Der Smith-Waterman-Algorithmus verfolgt denselben Weg.

Der Smith-Waterman-Algorithmus verwendet dynamische Programmierung. Die dynamische Programmierung ist eine Technik, die dazu dient, Probleme in Teilprobleme zu unterteilen und diese Teilprobleme zu lösen, bevor die Lösungen für jeden kleinen Teil des Problems zu einer Gesamtlösung für das gesamte Problem zusammengefügt werden (siehe Altschul et al., 1997). Der Smith-Waterman-Algorithmus identifiziert also die optimalen lokalen Ausrichtungen nach dem Ansatz der dynamischen Programmierung. Auf dem Weg zu den optimalen lokalen Zuordnungen durchläuft dieser Algorithmus Zuordnungen jeder möglichen Länge, die an einer beliebigen Position in den beiden zu vergleichenden Sequenzen beginnen und enden.

Die Grundlage einer Smith-Waterman-Suche ist der Vergleich zweier Sequenzen A = (a1a2a3…an) und B = (b1b2b3…bn).

Der Smith-Waterman-Algorithmus verwendet individuelle paarweise Vergleiche zwischen Zeichen als:

In der obigen Gleichung ist Hij die maximale Ähnlichkeit von zwei Segmenten, die auf ai bzw. bj enden. Die Ähnlichkeit der Reste ai und bj wird durch eine Gewichtsmatrix dargestellt, wobei entweder eine Substitution oder eine Einfügung/Löschung berücksichtigt wird. Der erste Term berücksichtigt eine Erweiterung des Alignments, indem die beiden verglichenen Sequenzen um jeweils einen Rest erweitert werden. Der zweite und dritte Term behandeln eine Erweiterung des Alignments durch Einfügen einer Lücke der Länge k in Sequenz A bzw. Sequenz B. Der vierte Term schließlich ignoriert einen möglichen negativen Alignment-Score, indem er eine Null in die Rekursion einfügt. Die vorangegangenen Berechnungen laufen neutral ab, wobei die Zulässigkeit des Ähnlichkeitswertes Null im Ausdruck für Hij beibehalten wird, was bedeutet, dass ein lokales Alignment im Falle eines Zeichen-zu-Zeichen-Vergleichs an jeder beliebigen Position neu beginnen kann (Smith & Waterman, 1981).

Jedem der zu vergleichenden Reste zwischen den beiden Sequenzen wird vom Algorithmus eine Punktzahl zugewiesen. Der Vergleich jedes Zeichenpaares wird in einer Matrix gewichtet, die jeden möglichen Pfad berücksichtigt, der für eine bestimmte Zelle berechnet wurde. Wie bei einer typischen Matrixzelle wird die Punktzahl der optimalen Ausrichtung, die an den Koordinaten endet, durch den Wert der Matrixzelle dargestellt. Diese Matrix identifiziert die Ausrichtung mit der höchsten Punktzahl als die optimale Ausrichtung, wie in Abbildung 4 dargestellt.

Die Matrixzelle mit der höchsten Punktzahl, die für die optimale lokale Ausrichtung in Frage kommt, dient als Ausgangspunkt für den Algorithmus. Der Weg der höchsten Matrixzelle, der zum optimalen lokalen Alignment führt, wird dann durch das Array zurückverfolgt, bis eine Zelle mit der Punktzahl Null gefunden wird. Die Punktzahl in jeder Zelle spiegelt die maximal mögliche Punktzahl für eine Ausrichtung beliebiger Länge wider, die an den Koordinaten dieser spezifischen Zelle endet (Smith & Waterman, 1981).

Beispiel

Der Smith-Waterman-Algorithmus kann durch den Vergleich zweier Sequenzen veranschaulicht werden:

Sequenz A: CAGCCUCGCUUAG.

Sequenz B: AAUGCCAUUGACGG.

Hardwarebasierte Bioinformatik-Optimierungslösungen

Die Wachstumsrate der biologischen Sequenzdaten, die analysiert werden müssen, steigt exponentiell an, wodurch der Bedarf an einer Vergrößerung der Computerinfrastrukturen und die Dringlichkeit einer Sequenzanalyse mit höherem Durchsatz die Standardverbesserungsrate der zugrunde liegenden Computerinfrastruktur übersteigt. Im Falle einer Sequenzanalyse mit höherem Durchsatz besteht die Wahl zwischen spezieller, dedizierter Hardware und handelsüblichem Cluster-Computing. In diesem Abschnitt werden einige innovative Optionen in diesem Bereich vorgestellt und die Vor- und Nachteile jeder Option untersucht, um schließlich einen allgemeinen Rahmen für die Bewertung von Alternativen zu skizzieren.

CLC Bioinformatik-Würfel

Der CLC Cube ist ein kleines Hardware-Gerät, das für Hochleistungs-Datenbanksuchen verwendet wird, die mit sehr hoher Geschwindigkeit durchgeführt werden sollen, ohne die Qualität der Suchergebnisse zu beeinträchtigen (CLC Bio., 2006). Dieses Gerät unterscheidet sich deutlich von den bekannten BLAST-Suchen, bei denen es mehr auf Geschwindigkeit als auf die Qualität der Suchergebnisse ankommt. Der CLC Bioinformatics Cube basiert auf Spitzentechnologie und innovativem Design, das den Nutzen der hardwarebeschleunigten Bioinformatik neu definiert.

Dieser Würfel bietet eine leistungsstarke, flexible und integrierte hardwarebeschleunigte Bioinformatiklösung und beseitigt damit die Probleme des Hochleistungsrechnens. Der Zugang zu diesem Gerät ist mit FPGA-Chips über den USB-Anschluss einfach und wird durch eine grafische Benutzeroberfläche (GUI) erleichtert. Es handelt sich um einen 12 x 12 x 12 cm großen Würfel mit Stahlrahmen, der zwei FPGA-Chips (Field Programmable Gate Array) enthält, die auf Platinen montiert und über einen USB-Anschluss mit einem Computer verbunden sind. Das Gerät verfügt über einen externen Speicher und ist so konzipiert, dass es mehrere Merkmale aufweist, wie z. B. Schnelligkeit, Benutzerfreundlichkeit, Kompatibilität mit bestehenden IT-Einrichtungen usw. (CLC Bio. White Paper, 2006).

Der CLC-Würfel verfügt über FPGA-Chips, mit deren Hilfe Berechnungen in einer hochgradig parallelisierten Umgebung durchgeführt werden können und die ihn außerdem rekonfigurierbar machen, was einen großen Vorteil gegenüber normalen Computern darstellt. Ein Nachteil der FPGA-Chips besteht jedoch darin, dass die Programmierung dieser Chips schwierig ist, was die Implementierung von Algorithmen zu einer sehr zeitaufwändigen Angelegenheit machen kann. Die Software ist die wichtigste Komponente, die zur Benutzerfreundlichkeit beiträgt.

Für den Zugriff auf diesen Würfel stehen zwei Optionen zur Verfügung: entweder über die Befehlszeile oder über die grafische Benutzeroberfläche der anderen Bioinformatik-Softwareanwendungen von CLC bio wie CLC Gene Workbench, CLC Protein Workbench und CLC Combined Workbench. Die kompatibelste Zugriffsoption ist die Kommandozeilenversion, die auf NCBI BLAST basiert und ähnliche Eingabe- und Ausgabeformate hat (Haibe & Bontempi, 2006).

Dank des innovativen FPGA-basierten Chipdesigns und des Smith-Waterman-Algorithmus erreicht dieser Würfel eine Leistung pro Beschleunigereinheit, die mindestens 50-mal so hoch ist wie die eines schnellen Desktop-Computers mit 3 GHz/4 GB RAM. Der Würfel kann leicht von jeder CLC-Workbench aus bedient werden – CLC Free Workbench, CLC Protein Workbench, CLC Gene Workbench – oder von der CLC Combined Workbench aus, die alle Funktionen der verschiedenen Workbenches zusammenfasst (CLC Bio. White paper, 2006). Die andere Option ist die Verwendung einer Befehlszeilenschnittstelle, die jederzeit und überall verwendet werden kann, indem zwei Kabel an eine kleine externe Box angeschlossen werden – ein Kabel für die Stromversorgung und eines für eine USB-Verbindung. Die wichtigsten Punkte, die sich in Bezug auf den CLC-Würfel ergeben, sind also

Dieser Würfel kann die Leistung erheblich verbessern, indem er die Datenbanksuche auf einem hohen Qualitätsniveau innerhalb einer angemessenen Zeitspanne ermöglicht.

Arbeitsabläufe und Datenbanken

Eine Cube-Smith-Waterman-BLAST-Suche hat den folgenden Arbeitsablauf (siehe CLC Bio. Whitepaper, 2006):

Bei niedrigeren e-Werten erzielt der Cube eine bessere Leistung, was auch daran liegt, dass der Alignment-Teil des Smith Waterman BLAST in der Software durchgeführt wird, was im Cube naturgemäß nicht beschleunigt wird.

Es gibt verschiedene Arten von Datenbanksuchen, wie in Tabelle 1 unten aufgeführt. Die auf Smith Waterman basierende BLAST-Suche kann auf diesem Würfel ausgeführt werden.

Es wurden einfache Vergleiche unter Berücksichtigung dieser Plattformen durchgeführt – CLC Bioinformatics Cube, clcblast_0.2.0 und ein DELL Desktop mit einem 3.0 GHz Pentium 4 CPU und 2 GB RAM. Zu diesem Zweck wurde das Smith Waterman BLASTn an einem Datensatz getestet, der aus allen EST-Sequenzen von Pferden in GenBank besteht (36.914 Sequenzen mit einer Gesamtzahl von 19.762.562 Resten). Im Falle von BLASTp umfasste der Testdatensatz 50.000 zufällig ausgewählte Proteinsequenzen aus SwissProt (mit insgesamt 18.396.764 Resten).

Die als “Beschleunigung” dargestellte Ausführungszeit bezeichnet die Ausführungszeit des Algorithmus ohne Verwendung des Würfels im Vergleich zur Ausführungszeit des Algorithmus, wenn der Würfel angeschlossen ist. Ein ähnlicher Ansatz wurde bereits früher verfolgt, wie in (CLC Bio. Whitepaper, 2006) beschrieben.

Wie aus Tabelle 3 hervorgeht, ist der 3-GHz-Desktop im Vergleich zur Geschwindigkeit des Würfels bei kleinen Mengen von Abfragesequenzen und kleinen Datensätzen recht langsam, und die Geschwindigkeit nimmt bei größeren Mengen von Abfragesequenzen, insbesondere bei größeren Datensätzen, weiter zu.

Bei kleinen Sequenzmengen und kleinen Datensätzen kann der Cube eine 4-8 mal höhere Geschwindigkeit als der 3 GHz Desktop erreichen. Wie aus Tabelle 2 hervorgeht, ist der Cube bei Datenbanken mit mehr als 500.000 Nukleotiden 35 bis 128 Mal schneller als der 3-GHz-Desktop. Wenn die e-Werte bei 1 oder darunter liegen, beträgt der Geschwindigkeitszuwachs immer mehr als 78-mal. Der Würfel läuft mit einer Geschwindigkeit von bis zu 5 Giga-Cell-Updates pro Sekunde (GCUPS) im Vergleich zu einer Geschwindigkeit von bis zu 0,05 GCUPS, die der 3-GHz-Desktop erreicht. Bei kleinen Datenbanken ist der Geschwindigkeitszuwachs bei höheren e-Werten jedoch gering, was auf den Zeitaufwand für die in der Software durchgeführten Suchvorgänge zurückzuführen ist (Haibe & Bontempi, 2006).

In Anbetracht der Tatsache, dass es nur 4 verschiedene Nukleotide, aber 20 verschiedene Aminosäuren gibt, ist die Geschwindigkeit des Würfels bei der Suche nach Aminosäuren natürlich geringer als bei der Suche nach Nukleotiden. Wie aus Tabelle 5 hervorgeht, ist die Würfelgeschwindigkeit in Verbindung mit einer geringeren Anzahl von Sequenzen und kleineren Datensätzen etwa 3 bis 9 Mal schneller als die des 3-GHz-Desktops. Die Beschleunigung nimmt bei einer höheren Anzahl von Sequenzen und größeren Datensätzen zu. Bei Datenbanken mit mehr als 350.000 Aminosäuren erreicht der Cube eine Geschwindigkeit von 1,55 GCUPS, während der 3 GHz Desktop nur 0,046 GCUPS erreicht. In diesem Fall kann die Anzahl der abgefragten Sequenzen die Ergebnisse beeinflussen, aber es wird angenommen, dass der Effekt nicht sehr signifikant ist (siehe Altschul et.al., 1997).

Die Smith-Waterman-Versionen von tBLASTn, BLASTx und tBLASTx haben fast den gleichen Geschwindigkeitszuwachs wie die Smith-Waterman-Version von BLASTp. Alle diese Algorithmusversionen sind auch in der Lage, Protein-Protein-Vergleiche durchzuführen (siehe CLC Bio. Whitepaper, 2006).

Bei herkömmlichen integrierten Schaltkreisen ist ein großes Gitter mit verschiedenen Gattern, Invertern usw. angeschlossen, das schließlich das System steuert und die gewünschten Funktionen ausführt. Die CPUs von Computern sind mit den integrierten Schaltungen verwandt, verfügen jedoch über erweiterte Funktionen. Die CPUs müssen mehrere Funktionen ausführen, z. B. das Addieren ganzer Zahlen, das Multiplizieren reeller Zahlen, das Lesen und Schreiben in den Speicher usw. Der CLC-Würfel verwendet eine innovative Technologie, die sogenannte FPGA-Technologie, die eine große Anzahl von Gattern in einem integrierten Schaltkreis beherbergt, um die Funktion zu simulieren, wie ein integrierter Schaltkreis funktioniert (Smith & Waterman, 1981).

So kann eine integrierte Schaltung, wenn sie in einem FPGA aufgerüstet wird, die Schaltungsarbeiten simulieren und dadurch wie ein speziell entwickelter Chip funktionieren. Ein einzigartiger Vorteil in diesem Fall ist, dass viele Schaltungen aufgerüstet und in FPGA hochgeladen werden können, wodurch das Gerät mehrere Funktionen ausführen kann. Die FPGA-Programmierung ist jedoch nicht so einfach und kann nicht mit den typischen Gattern mit zwei Eingangsleitungen durchgeführt werden.

Die FPGI-Technologie verwendet Lookup-Tabellen mit vier Eingängen und ist damit fortschrittlicher als normale Gatter. Die Ausgänge der Lookup-Tabellen können integriert werden, indem sie mit den Eingangsleitungen einschließlich anderer Tabellen verbunden werden und so ein großes Netzwerk bilden. Die FPGA-Chips verfügen wie die normalen integrierten Schaltungen über einen kleinen internen Speicher, der zum Speichern verschiedener Zustände und einiger Daten verwendet werden kann.

Der Ausgang dieser Nachschlagetabellen kann dann mit den Eingangsleitungen für andere Tabellen in einem großen Netzwerk verbunden werden, genau wie normale integrierte Schaltungen. Darüber hinaus verfügen die FPGA-Chips über einen kleinen internen Speicher, der zur Speicherung verschiedener Zustände und einiger Daten verwendet werden kann. Es ist zu beachten, dass ein FPGA keine feste Taktrate hat. Der spezifische Schaltkreisentwurf, der in den FPGA geladen wird, bestimmt die tatsächliche Taktgeschwindigkeit. FPGA hat eine programmierbare Taktgeschwindigkeit, die an die spezifischen Berechnungen, die durchgeführt werden sollen, angepasst wird.

Der CLC-Würfel hat zwei FPGA-Chips, die auf Platinen mit externem Speicher montiert sind, und das Hinzufügen eines zusätzlichen externen Speichers zu den Platinen erleichtert die Speicherung großer Datenmengen. Diese Option hilft, den Nachteil des üblicherweise verwendeten begrenzten internen Speichers eines Chips auszugleichen. Ein USB-Anschluss verbindet die Karten mit dem Computer. Die aktuellen Versionen der USB-Verbindungen haben eine sehr hohe Kapazität, jedoch stellt die sehr hohe Rechenleistung der FPGAs eine Herausforderung dar, um die Algorithmen passend zur USB-Bandbreite zu entwerfen (CLC Bio. Whitepaper, 2006).

SAMBA – Algorithmus und Architektur

SAMBA wurde am IRISA für bestimmte Spezialanwendungen wie den Vergleich biologischer Sequenzen, Bildkompression, Datenkompression, Kodierung und Kryptographie entwickelt (Lavenier Dominique, 1996). Es handelt sich um einen vollständig kundenspezifischen, auf einem systolischen Array basierenden Hardware-Beschleuniger, der in der Lage ist, Vergleiche von biologischen Sequenzen mit gutem Erfolg durchzuführen. Dieser Hardware-Beschleuniger implementiert eine parametrisierte Version des Smith- und Waterman-Algorithmus, der die Berechnung lokaler oder globaler Alignments mit oder ohne Gap Penalty ermöglicht (Smith & Waterman, 1981). Der Geschwindigkeitszuwachs, den Samba gegenüber Standard-Workstations bietet, liegt je nach Anwendung zwischen 50 und 500. Im Grunde handelt es sich um einen Hardware-Beschleuniger, der für die Beschleunigung der Algorithmen beim biologischen Sequenzvergleich entwickelt wurde (Guerdoux & Lavenier, 1995).

Der Hauptalgorithmus, auf dem SAMBA läuft, gehört zur Klasse der dynamischen Programmierung, und die Rekursionsgleichung stammt aus dem Smith- und Waterman-Algorithmus. Die Algorithmen wurden jedoch angepasst und parametrisiert, um einen größeren Bereich abzudecken. In SAMBA wird eine Ähnlichkeitsmatrix rekursiv anhand der folgenden Gleichung berechnet (siehe Lavenier Dominique, 1996):

und die durch gegebenen Initialisierungen:

H(i,0) = E(i,0) = hi(i) H(0,j) = F(0,j) = vi(j)

alpha, beta, delta, hi und vi sind die Parameter für die Einstellung des Algorithmus auf lokale oder globale Suche, mit oder ohne Lückenstrafe.

Der Prozess des Sequenzvergleichs auf einem linearen systolischen Array läuft mit einer Abfragesequenz ab, die in dem Array gespeichert ist und ein Zeichen pro Prozessor umfasst, gefolgt von anderen Sequenzen, die von links nach rechts durch das Array laufen. Jeder Prozessor ist bei jedem systolischen Schritt mit der Berechnung einer Elementarmatrix beschäftigt. Das Ergebnis erscheint auf dem Prozessor ganz rechts, wenn das letzte Zeichen der fließenden Sequenz ausgegeben wird.

Im Vergleich zu einer sequentiellen Maschine ist der Geschwindigkeitszuwachs für die Berechnung einer Abfragesequenz der Größe N gegen eine Datenbank mit M Resten gegeben durch (Lavenier, 1993):

N x M

— = N (unter der Annahme, dass M >> N)

N + M – 1

N = Größe der Abfragefolge (Anzahl der Prozessoren)

M = Größe der Datenbank

Die SAMBA-Workstation enthält eine lokale Festplatte, ein systolisches Array mit 128 VLSI-Vollprozessoren und eine FPGA-Speicherschnittstelle. Der FPGA-Speicher füllt die Lücke zwischen einem kompletten festverdrahteten Array von Prozessoren und einer programmierbaren Von-Neuman-Maschine (Abbildung 8) (Lavenier Dominique, 1996).

Ein Array mit einem Satz von 32 vollständig identischen Chips mit jeweils 4 Prozessoren ergibt ein Array mit 128 Prozessoren, und die von dem Chip erzeugte Rechenleistung beträgt etwa 40 Millionen Matrixzellen pro Sekunde. Diese Rechenleistung ist völlig ausreichend, um das Array auf eine Spitzenleistung von 1,28 Milliarden Matrixzellen pro Sekunde zu bringen.

Im Grunde ist SAMBA ein Hardware-Beschleuniger mit einer Bibliothek von C-Vergleichsprozeduren auf hohem Niveau, die die Wahl zwischen vordefinierten Programmen, wie den klassischen Programmen, die bereits für das Bank-Scanning entwickelt wurden, oder benutzerdefinierten Programmen, die auf eine bestimmte Anwendung abgestimmt sind, ermöglicht. Er wird durch einige wenige Prozeduraufrufe innerhalb eines normalen C-Programms gesteuert, wodurch der Benutzer keine speziellen Kenntnisse über die Struktur des Beschleunigers und seine Funktionsweise haben muss (siehe Pearson, 1991).

Netztechnik

Die Grid-Technologie hat sich als die praktikabelste Option für die Integration großer, verteilter und heterogener Ressourcen erwiesen, und seit kurzem hält sie auch in der Bioinformatik Einzug. In den Bereichen der Bioinformatik bilden Grids das technologische Rückgrat, das die gemeinsame Nutzung von Bioinformatikdaten von verschiedenen Standorten und Datenbanken, die über die ganze Welt verstreut sind, erleichtert und ermöglicht. Im Gegensatz zu zentralisierten Datenbanksystemen hilft die Grid-Technologie bei der gemeinsamen Nutzung von geografisch verteilten Datenbanken und trägt somit dazu bei, die bei zentralisierten Datenbanken üblicherweise auftretenden Fehlerquellen zu beseitigen (Vazhkudai et.al., 2001).

In der Grid-Umgebung kann jeder neue Datensatz, z. B. Versuchsergebnisse, problemlos auf einem lokalen System gespeichert und mit anderen, weltweit verteilten Systemen geteilt werden. Außerdem können die Benutzer auf die Daten zugreifen und mit ihnen arbeiten, ohne den tatsächlichen Standort der Zieldaten oder -informationen zu kennen. Das Grid-System verarbeitet Daten, die aus verschiedenen Quellen und von verschiedenen Orten stammen, und diese Anordnung erfordert kompatible Computerinfrastrukturen, die den freien Datenfluss gewährleisten. Diese unterschiedliche Konfiguration der Zieldaten beeinflusst somit das Design der Grid-Infrastrukturen und erfordert eine Middleware-Schicht, die als Schnittstelle für die Umwandlung der verschiedenen Datensätze in ein einheitliches Standardformat dient (siehe Wasinee et al., 2002).

Die Grid-Infrastruktur eignet sich am besten für parallele und verteilte Anwendungen, und darüber hinaus bieten Grids auch einen nahtlosen Zugriff auf den Datenbestand. Die Grid-Ressourcen können für Aufgaben wie dynamische Simulationen, Netzwerkmodellierung und andere rechenintensive Aufgaben verwendet werden. Darüber hinaus ist das Grid-Netz ein Zusammenschluss von Computerressourcen, und das System ist mit geografisch verteilter Rechenleistung ausgestattet, die bei der gemeinsamen Nutzung von Daten, der wichtigsten Funktion jedes Grid-Systems, enorm hilfreich sein kann (Vazhkudai et al., 2001).

Bei der Einrichtung eines Bioinformatik-Grid ist es wichtig, die verteilten Rechnerkomponenten in der Bioinformatik-Anwendung zu verwalten und zu pflegen, um einen effizienten und barrierefreien Zugriff auf die verteilten Daten von verschiedenen Standorten aus zu gewährleisten. Um dies zu erreichen, muss ein Softwaresystem entworfen und erstellt werden, was eine sehr anspruchsvolle Aufgabe ist. Neben der Verwaltung der verteilten Datenverarbeitungskomponenten sollte dieses System in der Lage sein, die Kommunikationskosten zu minimieren, indem es die beste Option für die Berechnung der Datensätze ermittelt.

Hier muss die Software eine der beiden Berechnungsoptionen wählen – Berechnung durch Senden von Daten an ein spezielles System oder Berechnung durch Verwendung eines Berechnungsobjekts am Ort der Zieldatenbank (Wasinee et.al., 2002). Obwohl es sich um ein komplexes System handelt, ist es aufgrund seiner überragenden Rechenleistung, der riesigen Datenverarbeitungskapazität und der erweiterten geografischen Abdeckung des Grid-Systems die bevorzugte Option im Bereich der modernen Biologie und Bioinformatik.

In Abbildung 9 ist die Architektur eines von mehreren Institutionen betriebenen, verteilten, datenbankabhängigen und heterogenen Grid-Systems dargestellt. Unterhalb des Grid-Datensystems läuft eine Suchmaschine, die die Standorte der Zieldaten einspeist. Nach der Identifizierung der Datenstandorte erfolgt die Auswahl und Verarbeitung der Daten gemäß den Spezifikationen der bevorzugten Berechnungsmethode. Manchmal erfordert die Rechenaufgabe zusätzliche Eingaben, die, falls lokal verfügbar, direkt bereitgestellt werden können.

Falls die zusätzlichen Eingaben nicht lokal gefunden werden, kann der Prozess rekursiv angewendet werden. Die oben gezeigte Architektur ist für generische Grid-Datendienste mit einem Grid-Sicherheitssystem gedacht, das als Gateway für jeden Grid-Standort implementiert werden muss und so einen einheitlichen Zugang zu heterogenen Speichersystemen einschließlich Datenbanken von Anbietern, XML-Dateien und proprietären Bioinformatikdateien ermöglicht. Es gibt eine Anwendungsprogrammierschnittstelle (API) für Speichersysteme, die einen einheitlichen Zugang zu verschiedenen Speichersystemen ermöglicht (Kola et.al., 2005). Um dieses System zu nutzen, müssen die Benutzer nicht die Funktionsweise der einzelnen Speichersysteme kennen.

Es gibt ein offenes Standardprotokoll namens LDAP, auf dem der Metadatenkatalog implementiert ist, in dem alle Informationen des Speichersystems gespeichert sind. Die anwendungsspezifischen Verhaltensweisen, wie z. B. die Datenzugriffsrichtlinien im Cache-Management-Dienst, befinden sich in der obersten Schicht dieser Architektur. Eine solche Anordnung ermöglicht die Wiederverwendbarkeit der grundlegenden Grid-Datenarchitektur und bietet gleichzeitig den Benutzern die Flexibilität, ihre Anwendungen so anzupassen, dass eine hohe Leistung erzielt wird (siehe Wasinee et al., 2002).

Auf dem Gebiet der Bioinformatik sind die Suche nach Sequenzähnlichkeiten und Anwendungen für den Mehrfachabgleich die bevorzugten Ansätze, insbesondere bei großen Datenbanken. Die Suche in großen Datenbanken erfordert im Allgemeinen eine längere Ausführungszeit, die für die Durchführung einer simulatorgestützten Studie zu hoch ist und nicht praktikabel. Die vorliegende Studie zielt darauf ab, Daten mit vernünftigen Eingabegrößen zu sammeln, die die gesamte Ausführungsphase der Bioinformatik-Anwendungen abdecken.

Unter Berücksichtigung dieser Tatsache wurde geplant, die Hardware-Leistungszähler zu verwenden. Die hier verwendeten Hardware-Zähler sind in modernen Mikroprozessoren eingebaut und nicht in einem Simulator. Heutzutage gibt es viele spezielle Zähler, die zum Zählen verschiedener Ereignisse wie Cache-Misses, Verzweigungsfehlprognosen und anderer nützlicher Messgrößen für die Anwendungsleistung verwendet werden können (siehe Kursad et al., 2005). Ihre begrenzte Anzahl ist das einzige Problem oder der einzige Nachteil, der mit den Hardware-Leistungszählern verbunden ist. In dieser Studie werden nur 2 Zähler auf einer Intel Pentium-III CPU verwendet. Diesem Nachteil wurde hier durch Multiplexing entgegengewirkt.

Das Multiplexing nutzt Time-Sharing, um mit den Zählern verschiedene Ereignisse in verschiedenen Zeitabschnitten zu messen, und extrapoliert das Ergebnis. Es hat sich gezeigt, dass diese Methode recht genaue Messungen liefert. Hier wurde die PAPI-Bibliothek für den Zugriff auf Hardware-Leistungszähler eingesetzt, die den Linux-Kernel-Patch perfctr für das Zählermultiplexing verwendet (Brown S. et.al., 2000). Die Datenerfassung und -analyse wurde mit den PerfSuite-Dienstprogrammen durchgeführt. Mit diesem Aufbau konnten unmodifizierte BioBench-Anwendungen mit großen Eingabegrößen ausgeführt werden, die für ihre typische Verwendung charakteristisch sind. Die gesamten Arbeitslasten nahmen bis zu 2,1 Billionen Anweisungen in Anspruch, und die Anzahl der Anweisungen für jede BioBench-Suite ist in Tabelle 6 unten angegeben.

Zur Charakterisierung der BioBench-Suite wurde eine Reihe von Daten gesammelt. Zu den gesammelten Daten gehören Daten zu Befehlsprofilen, Basisblocklängen, IPC, L1- und L2-Datencache-Fehlraten und Verzweigungsvorhersagegenauigkeit. Die gleichen Daten wurden zum Vergleich auch für die SPEC 2000-Benchmarks gesammelt. In der ersten Phase wurden die Hardware-Leistungszähler verwendet, um die Anzahl der Anweisungen zu ermitteln, die zu den verschiedenen Hauptanweisungsklassen der X86-Architektur gehören. Die Befehlsprofile für BioBench-Anwendungen sind in Abbildung 10 dargestellt.

Aus der Abbildung geht hervor, dass der Anteil der Fließkommaoperationen bei fast allen BioBench-Anwendungen vernachlässigbar ist. Dies steht im Einklang mit der Erkenntnis, dass sich Bioinformatik-Anwendungen aufgrund der Darstellung der Daten, mit denen sie arbeiten, von Natur aus von herkömmlichen wissenschaftlichen Codes unterscheiden. Es ist zu beobachten, dass keine der BioBench-Workloads einen Fließkomma-Befehlsanteil von über 0,09 % der insgesamt ausgeführten Befehle aufweist.

Außerdem stimmt der Anteil der Ladeanweisungen in BioBench-Anwendungen nicht mit dem der SPEC-Integer-Benchmarks überein, was darauf hindeutet, dass der Rechenaufwand pro Datenelement relativ gering ist. Der geringe Rechenaufwand ist eine typische Eigenschaft der Suchalgorithmen. Es ist zu erkennen, dass Protpars der Benchmark mit der kleinsten Größe der Eingabedatei ist, und dieser Benchmark unterscheidet sich auch von den übrigen BioBench-Komponenten, da er einen größeren Anteil an Integer-ALU-Befehlen aufweist, die mehr als die Hälfte der Befehlsanzahl ausmachen. BioBench hat einen höheren Anteil an Lade-/Speicheroperationen, was eindeutig darauf hindeutet, dass Bioinformatik-Anwendungen wahrscheinlich von zukünftigen Architekturen mit höherer Speicherbandbreite und Prefetching profitieren werden.

Die IPC-Zahlen für die Anwendungen in der BioBench-Suite sind in Abbildung 11 dargestellt. Die BioBench-Benchmarks weisen eine deutlich höhere durchschnittliche IPC auf, was darauf hindeutet, dass die BioBench-Anwendungen im Vergleich zu den SPEC INT- und FP-Benchmarks ein höheres Maß an “Instruction Level Parallelism” (ILP) aufweisen. Dieser Befund deckt sich gut mit der früheren Feststellung, dass der Fließkommaanteil in BioBench fast vernachlässigbar ist, was schlüssig darauf hindeutet, dass die Bioinformatik-Anwendungen stark von den breiteren Superskalaren der Zukunft mit hoch optimierten schnellen Integer-Kernen profitieren werden. Es ist auch festzustellen, dass die IPC-Werte für alle einzelnen Anwendungen im BioBench-System erheblich variieren.

Die Basisblocklänge für BioBench-Anwendungen ist in Abbildung 12 unten dargestellt. Die Abbildung zeigt, dass die durchschnittliche Basisblocklänge der BioBench-Anwendungen ungefähr zwischen den Durchschnittswerten von SPEC INT und SPEC FP liegt und dass alle einzelnen BioBench-Benchmarks im Vergleich zum SPEC INT-Durchschnitt höhere Basisblocklängen aufweisen. Diese höhere Blocklänge bedeutet, dass Bioinformatik-Anwendungen näher an wissenschaftlichen Workloads liegen als in Bezug auf die Verteilung der Kontrolltransferanweisungen.

Wie aus Abbildung 13 hervorgeht, ist die Genauigkeit der Verzweigungsvorhersage bei den BioBench-Benchmarks relativ geringer als bei den SPEC-Benchmarks. Der Unterschied zwischen der Genauigkeit der Verzweigungsvorhersage bei den beiden Benchmarks scheint angesichts der sehr hohen Vorhersagegenauigkeit moderner Verzweigungsvorhersageprogramme nicht sehr groß zu sein.

Die Abbildungen 14 und 15 zeigen die Daten-Cache-Miss-Raten und verdeutlichen die Unterschiede in den Speichernutzungsmustern der verschiedenen BioBench-Komponenten.

Abbildung 14 zeigt, dass mummer und tigr im Vergleich zu den übrigen Anwendungen in den BioBench-Benchmarks höhere L1-Daten-Cache-Fehlalarmraten aufweisen, was sich auch in ihrem L2-Daten-Cache-Fehlalarmverhalten widerspiegelt (Abbildung 15). Die Daten-Cache-Miss-Raten der Mehrfachausrichtungskomponente clustalw zeigen sehr niedrige L1- und L2-Werte, während clustalw eine hohe IPC und eine ziemlich hohe durchschnittliche Basisblocklänge zusammen mit seinem geringen Speicherbedarf aufweist.

Diese Auswertung bestätigt die weit verbreitete Annahme, dass Bioinformatik-Anwendungen Merkmale aufweisen, die sie von den herkömmlichen, durch die SPEC FP-Benchmarks charakterisierten Anwendungen des wissenschaftlichen Rechnens unterscheiden. Bei den in dieser Studie bewerteten Bioinformatik-Anwendungen wurden keine signifikanten Gleitkomma-Anweisungen beobachtet. Ein höheres ILP und Basisblocklängen, die näher an den SPEC FP-Benchmarks liegen als am SPEC INT-Pendant, deuten auf eine gleichmäßige Verteilung der Verzweigungen hin. Daher kann gesagt werden, dass Bioinformatik-Anwendungen von zukünftigen Architekturmerkmalen wie erhöhter Speicherbandbreite, Memory Prefetching und breiteren Superskalaren profitieren können, um ihr hohes ILP auszunutzen.

Schlussfolgerungen

Dieses Papier bestätigt die Tatsache, dass es eine Reihe von Bioinformatik-Tools und -Techniken gibt, aber es ist nie einfach, die beste Option zu finden. In dieser Studie werden einige Probleme identifiziert, die…

Zusammenfassend kommt diese Studie zu dem Ergebnis, dass Bio-Anwendungen besser für parallele Architekturen geeignet sind, wenn sie von ganzzahligen Operationen dominiert werden und wenn Operationen zur Änderung der Verknüpfungsbäume zwischen Ein und Aus entscheidend sind.

Referenzen

Aleksander Slominski, Dennis Gannon und Geoffrey Fox, ‘Introduction to Workflows and Use of Workflows in Grids and Grid Portals’, Indiana University, 2007.

Archuleta, J.; Tilevich, E.; Wu-chun Feng, ‘A Maintainable Software Architecture for Fast and Modular Bioinformatics Sequence Search, ICSM 2007. IEEE, Ausgabe.

Altschul S.F., Gish W., Miller W. Myers E., ‘ Basic local alignment search tool’, Journal of Molecular Biology, 215:403-410, 1990.

Bowers, S. und Ludascher, B. 2005. Actor-Oriented Design of Scientific Workflows. In 24 th Intl. Conf. on Conceptual Modeling (ER).

Browne S., Dongarra J., Garner N., und Mucci P., ‘A scalable cross-platform infrastructure for application performance tuning using hardware counter’ in Proceedings of the 2000 ACM/IEEE Conference on Supercomputing, 2000.

Casey, RM (2005). “BLAST-Sequenzen helfen bei der Genomik und Proteomik”. Business Intelligence Network.

Chattopadhyay A. et.al., ‘Design and implementation of a library-based information service in molecular biology and genetics at the University of Pittsburgh’, J Med Libr Assoc. 307-313, E192, 2006.

CLC Bio, CLC Bioinformatics Cube, CLC bio LLC, Cambridge, 2006.

Guerdoux J. & Lavenier D., Systolic filter for fast DNA similarity search’, ASAP’95, Strasbourg, 1995.

Haibe-Kains, Bontempi G., ‘Data Analysis and Modeling Techniques, Bioinformatics Tools for Microarray Analysis’, Microarray Unit, Institut Jules Bordet, Machine Learning Group, Universit’e Libre de Bruxelles, 2006.

Kursad A., Jaleel A., Wu Xue, Manoj Franklin, Bruce Jacob, Tseng Chau-Wen und Yeung Donald, ‘BioBench: A Benchmark Suite of Bioinformatics Applications’, University of Maryland, College Park, 2005.

Korf Ian, Yandell Mark & Bedell Joseph, ‘An Essential Guide to the Basic Local Alignment Search Tool- BLAST’, Oreilly, Cambridge, 2006.

Kola G, Kosar T, Livny M. Faults in Large Distributed Systems and What We Can Do About Them. Proceedings of 11th European Conference on Parallel Processing (Euro-Par 2005).

Lavenier Dominique, SAMBA- Systolic Accelerator for Molecular Biological Applications’, IRISA, Campus universitaire de Beaulieu, RENNES Cedex, Frankreich, 1996.

Lavenier D., An Integrated 2D Systolic Array for Spelling Correction & Integration : the VLSI journal, 15:97{111, 1993.

Lin Qi, ‘Parallelisation of the blast algorithm’, Cell Mol Biol Lett. 2005; 10(2):281-5.

Lipman DJ, Pearson WR. (1985) “Schnelle und empfindliche Protein-Ähnlichkeitssuche”. Science 227(4693): 1435-41.

Leong Philip, ‘Hardware Acceleration for Bioinformatics’, Fachbereich Informatik und Ingenieurwesen, The Chinese University of Hong Kong, 2003.

Ligon W. B., ‘Research directions in parallel I/O for clusters’, Keynote speech, in Proceedings of 2002 IEEE International Conference on Cluster Computing. 2002.

Madden T., ‘The BLAST Sequence Analysis Tool’, National Center for Biotechnology Information (NCBI), 2003.

Mark Schreiber, Bioinformatics Research Investigator, ‘Bioinformatics workflow management- Thoughts and case studies from industry’, Novarties Institute of Tropical Diseases, WWWFG, 5-7 2007.

Mount D.W., “Bioinformatik: Sequenz- und Genomanalyse.”. Cold Spring Harbor Press. 2004.

(NCBI)/National Center for Biotechnology Information (NCBI). 2003. Web.

Oinn, T., Greenwood, M., et al. 2005. Taverna: Lektionen bei der Erstellung einer Workflow-Umgebung für die Biowissenschaften. Gleichzeitigkeit und Computation: Praxis und Erfahrung, Band 18, Ausgabe 10.

Pearson W.R., ‘Searching protein sequence libraries: comparison of the sensitivity and selectivity of the Smith-Waterman and FASTA algorithms’, Genomics, 11, 635-50, 1991.

Pearson WR, Lipman DJ: Verbesserte Werkzeuge für den biologischen Sequenzvergleich. Proc Natl Acad Sci U S A 1988, 85(8):2444-2448.

Robert R et,al., ‘A Genetic Algorithm-Based, Hybrid Machine Learning Approach to Model Selection’, Journal of Pharmacokinetics and Pharmacodynamics: 196-221.

Smith T. und Waterman M., ‘Identification of common molecular subsequences’, Journal of Molecular Biology, 147:195-197, 1981.

Vazhkudai S., Tuecke S. und Foster I., ‘In Proceedings of the First IEEE/ACM International Conference on Cluster Computing and the Grid (CCGRID 2001)’, pp. 106-113, IEEE Press, (2001).

Wasinee R., Noppadon K., Chularat T. und Royol C., ‘Grid computing and bioinformatics development- A case study on the Oryza sativa (rice) genome’, Pure Appl. Chem., Vol. 74, No. 6, pp. 891-897, 2002, IUPAC.

Weißbuch über CLC Bioinformatics Cube Version 0.2.0, CLC Bioinformatics Cube, CLC bio LLC, Cambridge, 2006.

Zhang, H. (2003). Alignment of BLAST high-scoring segment pairs based on the longest increasing subsequence algorithm. Bioinformatics 19, 1391-1396.