Blatt · Leben
Abgleich — wie ähnlich zwei Folgen sind
Zwei Erbgutstücke, zwei Fassungen einer Datei, zwei Wörter mit Tippfehler — die Frage ist immer dieselbe: welche Teile entsprechen einander, und wo ist etwas eingefügt oder verschwunden? Die Antwort kommt seit 1970 aus derselben Matrix. Sie füllt sich Feld für Feld, und der Rückweg durch sie ist die beste Ausrichtung — von der man beweisen kann, dass keine bessere existiert.
Jedes Feld enthält die beste erreichbare Punktzahl bis dorthin. Es entsteht aus genau drei Möglichkeiten: schräg (beide Zeichen paaren), nach unten oder nach rechts (eine Lücke). Der eingezeichnete Weg ist der Rückweg vom Ende — und weil jedes Feld sein Maximum kennt, ist er beweisbar der beste.
gleich · verschieden · Lücke (eingefügt oder verloren)
Die Matrix hat so viele Felder, wie die beiden Folgen Zeichen haben — mal genommen. Für zwei Erbgutstücke von je 3 Milliarden Zeichen wären das 9·10¹⁸ Felder; deshalb benutzt niemand dieses Verfahren für ganze Genome, sondern nur für Ausschnitte.
Die Matrix behauptet, die beste Ausrichtung zu finden. Das lässt sich nachprüfen, indem man für kurze Folgen alle Ausrichtungen aufzählt — bei zwei Folgen von je sechs Zeichen sind das 8989 Möglichkeiten — und das Maximum vergleicht. Dazu die Eigenschaften, die eine Ähnlichkeit haben muss: Symmetrie, Selbstvergleich, Dreiecks- ungleichung des Änderungsabstands, und ein zweiter, unabhängig geschriebener Rechenweg.
noch nicht geprüft
Warum Lücken teuer sind
Ohne Strafe für Lücken wäre jede Folge zu jeder ähnlich: man schiebt einfach überall Löcher ein, bis die gleichen Zeichen übereinanderstehen. Die Lückenstrafe entscheidet also, was „ähnlich" überhaupt heißt. In der Biologie kostet das Öffnen einer Lücke viel und das Verlängern wenig — eine Einfügung von zehn Bausteinen ist ein Ereignis, nicht zehn.
Derselbe Algorithmus als diff
Nimmt man statt Buchstaben ganze Zeilen als Zeichen, ist dieselbe Matrix das
Werkzeug, das jeder Programmierer täglich benutzt: diff. Der Rückweg heißt
dann „hinzugefügt" und „entfernt". Im Beispiel oben lässt sich das umschalten.
Durchgehend oder stückweise
Needleman-Wunsch richtet die Folgen vollständig aneinander aus — passend, wenn beide ungefähr gleich lang und verwandt sind. Smith-Waterman sucht das ähnlichste Stück und lässt den Rest weg; genau das braucht man, wenn ein kurzes Erbgutstück irgendwo in einem langen gesucht wird. Der Unterschied ist eine einzige Zeile: negative Werte werden auf null gesetzt.
Eine einzelne HTML-Datei. Kein Build, keine Bibliothek, nichts verlässt den Browser. Alle Blätter: ssims437.github.io