Informatik: Übungs-Testlets für den TestAS

Notaufnahmen können Patienten nicht streng in der Reihenfolge ihres Eintreffens behandeln: Ein Patient mit Herzinfarkt muss vor einem mit verstauchtem Knöchel gesehen werden, auch wenn Letzterer früher kam. Triage-Systeme weisen jedem Patienten anhand einer kurzen, standardisierten Einschätzung eine Dringlichkeitsstufe zu. Viele sind als Algorithmen geschrieben, als genaue Folgen von Entscheidungen, die bei gleicher Eingabe immer zum selben Ergebnis führen. Algorithmen verringern Unterschiede zwischen Mitarbeitenden, machen Entscheidungen nachvollziehbar und lassen sich in Software umsetzen.

Ein Algorithmus besteht aus Schritten und Entscheidungen. In einem Flussdiagramm werden Schritte als Rechtecke und Entscheidungen als Rauten mit zwei Ausgängen, ja und nein, gezeichnet. Die Reihenfolge zählt: Ein Triage-Algorithmus prüft die gefährlichsten Zustände zuerst, damit ein lebensbedrohliches Problem nie übersehen wird, weil vorher eine weniger wichtige Frage gestellt wurde. Jeder Patient folgt einem einzigen Weg durch das Diagramm und verlässt es bei der ersten Stufe, deren Bedingung erfüllt ist.

Der vereinfachte Algorithmus unten weist eine von fünf Stufen zu, von Stufe 1 (sofortige Behandlung) bis Stufe 5 (nicht dringend). Er ist in Pseudocode geschrieben, einer strukturierten Mischung aus natürlicher Sprache und Programmierkonstrukten. Das Schlüsselwort WENN leitet eine Bedingung ein, und SONST WENN wird nur geprüft, wenn alle vorherigen Bedingungen falsch waren. Die erste wahre Bedingung bestimmt das Ergebnis.

WENN der Patient nicht atmet oder keinen Puls hat, DANN Stufe 1. SONST WENN der Patient bewusstlos ist oder die Sauerstoffsättigung unter 90% liegt, DANN Stufe 2. SONST WENN Schmerzwert ≥ 8 (auf einer Skala von 0 bis 10) oder Herzfrequenz > 120 pro Minute, DANN Stufe 3. SONST WENN Temperatur ≥ 39,0 °C oder Schmerzwert ≥ 4, DANN Stufe 4. SONST Stufe 5.

Beim Testen von Algorithmen werden typische Eingaben und Grenzfälle geprüft. Grenzfälle sind Werte genau an einer Schwelle, etwa ein Schmerzwert von genau 8, weil Fehler oft durch die Verwechslung von „größer als“ und „größer oder gleich“ entstehen. Beim Testen wird auch gefragt, ob jede mögliche Eingabe zu genau einem Ergebnis führt; ein Algorithmus mit SONST-WENN-Ketten und einem abschließenden SONST garantiert das. Schließlich wird die Reihenfolge der Bedingungen geprüft, weil das Vertauschen zweier Bedingungen das Ergebnis für Patienten ändern kann, die beide erfüllen.

DNA-Sequenzen werden als Zeichenketten aus den Buchstaben A, C, G und T gespeichert und analysiert, nach Konvention vom 5'- zum 3'-Ende geschrieben. Die Bioinformatik, also die Nutzung von Computern zur Analyse biologischer Daten, stützt sich auf einige grundlegende Operationen an solchen Zeichenketten.

Da die beiden DNA-Stränge komplementär sind und in entgegengesetzte Richtungen verlaufen, findet man die Sequenz des anderen Strangs über das reverse Komplement: Jede Base wird durch ihren Partner ersetzt (A durch T, C durch G), und das Ergebnis wird rückwärts gelesen, damit es ebenfalls von 5' nach 3' verläuft. Das reverse Komplement von 5'-AACG-3' ist daher 5'-CGTT-3'. Manche Sequenzen sind ihr eigenes reverses Komplement; solche palindromischen Sequenzen sind typische Erkennungsstellen von Restriktionsenzymen, die DNA an bestimmten kurzen Motiven schneiden. Das Enzym EcoRI zum Beispiel schneidet an der Sequenz GAATTC.

Der GC-Gehalt, der Prozentsatz der Basen G und C in einer Sequenz, unterscheidet sich zwischen Organismen und zwischen Bereichen eines Genoms. Da G-C-Paare durch drei Wasserstoffbrücken und A-T-Paare durch zwei zusammengehalten werden, braucht DNA mit höherem GC-Gehalt eine höhere Temperatur, um ihre Stränge zu trennen.

Um zwei gleich lange Sequenzen zu vergleichen, ist das einfachste Maß die Hamming-Distanz, die Zahl der Positionen, an denen sich die Buchstaben unterscheiden. Echte Vergleiche müssen auch Einfügungen und Auslassungen berücksichtigen und verwenden Alignment-Algorithmen, die bei Bedarf Lücken einfügen. Programme wie BLAST durchsuchen riesige Datenbanken nach Sequenzen, die einer Anfrage ähneln, was hilft, Gene zu identifizieren und ihre Funktion aus verwandten, besser untersuchten Genen abzuleiten.

Die Suche nach einem kurzen Muster, einem Motiv, in einer langen Sequenz heißt Zeichenkettensuche (String Matching). Die einfachste Methode prüft nacheinander jede mögliche Startposition. In einer Sequenz der Länge n kann ein Motiv der Länge m an n − m + 1 Positionen beginnen. Effizientere Algorithmen überspringen Positionen, die nicht passen können, was bei der Suche in Genomen mit Milliarden von Basen wichtig ist.

Sequenzdaten entstehen in gewaltigem Umfang. Ein einzelnes modernes Sequenziergerät kann an einem Tag Milliarden Basen lesen, und öffentliche Datenbanken enthalten heute Sequenzen von Hunderttausenden Arten. Vor der Analyse müssen die Rohdaten auf ihre Qualität geprüft und zu längeren Sequenzen zusammengesetzt werden, und jeder Schritt beruht auf den hier beschriebenen einfachen Zeichenkettenoperationen.