Die Editierdistanz ist ein Maß für die Ähnlichkeit von Wörtern - je kleiner die Editierdistanz, desto größer die Ähnlichkeit.
Wie ähnlich sind sich Proteine?
In der Molekularbiologie geht es darum, die Ähnlichkeit zwischen einem Protein und einem durch Mutation veränderten Protein zu bestimmen. Proteine bestehen aus einer Abfolge von Aminosäuren. Es gibt 20 Aminosäuren, die jeweils mit einem Großbuchstaben abgekürzt werden (https://de.wikipedia.org/wiki/Aminosäuren).
Ein interessantes Protein besteht aus der Abfolge der Aminosäuren Tryptophan, Isoleucin, Asparagin, Threonin, Glutaminsäure und Arginin, kurz WINTER. Durch Mutation hat sich das Protein in die Abfolge der Aminosäuren Tryptophan, Glutaminsäure, Isoleucin, Histidin, Asparagin, Alanin, Cystein, Histidin, Threonin, Glutaminsäure und Asparagin, kurz WEIHNACHTEN, geändert. Wie ähnlich sind sich diese Proteine?
Ähnlichkeit messen
Eine erste Annäherung, um die Ähnlichkeit zu bestimmen, ist die Berechnung der Editierdistanz. Die Editierdistanz ist ein Maß dafür, wie viele Buchstaben du in WINTER
ändern,
einfügen oder
löschen
musst, um WEIHNACHTEN zu erhalten. Je kleiner die Editierdistanz, desto größer die Ähnlichkeit.
Editierdistanz und Alignment
Die Editierdistanz zwischen WINTER und WEIHNACHTEN beträgt 6. Denn du musst in WINTER fünf Buchstaben einfügen und einen Buchstaben ändern, um WEIHNACHTEN zu erhalten:
W_I_N___TER
| | | ||X
WEIHNACHTENWas du hier siehst, ist ein Alignment, eine Ausrichtung der beiden Wörter aneinander, sodass gleiche Buchstaben übereinander stehen. Du siehst, wo Buchstaben übereinstimmen (|), wo Buchstaben eingefügt werden (_) und wo Buchstaben nicht übereinstimmen (X).
Distanz-Matrix ausfüllen
Du berechnest die Editierdistanz, indem du die folgende Matrix ausfüllst.
Du gehst dabei folgendermaßen vor:
Zu Beginn füllst du die Felder in der ersten Zeile und der ersten Spalte mit den Zahlen 0, 1, 2, 3, … aus.
Die restlichen Felder füllst du aus, indem du jeweils das linke, das schräg-links-obere und das obere Nachbarfeld betrachtest.
Zu den Werten des linken und des oberen Nachbarfeldes addierst du jeweils 1.
Zu dem Wert des schräg-links-oberen Nachbarfeldes addierst du auch 1, aber nur dann, wenn die Buchstaben der Zeile und der Spalte des Feldes, in welchem du bist, nicht übereinstimmen, ansonsten addierst du nichts.
Und von diesen drei Werten bildest du das Minimum und trägst dies in das aktuelle Feld ein.
Die ersten Einträge sind hier bereits eingetragen. Schaue dir diese Einträge an und überlege, wie sie zustande gekommen sind. Und fülle die restlichen Einträge aus.
Zum Schluss findest du die Editierdistanz im rechten unteren Feld der Matrix.
Alignment berechnen
Um ein optimales Alignment zu berechnen, kennzeichnest du zunächst in jedem Feld der Distanz-Matrix durch einen kleinen Pfeil zu dem entsprechenden Nachbarfeld, woher das Minimum stammt.
Wenn du alle Pfeile eingetragen hast, gehst du vom Feld unten rechts in der Ecke aus und wanderst in Pfeilrichtung, bis du im oberen linken Feld ankommst.
Das Alignment bestimmst du dabei folgendermaßen, hier am Beispiel von WINTER und WEIHNACHTEN:
wenn du nach links gehst, fügst du eine Lücke (_) in WINTER ein,
wenn du nach oben gehst, fügst du eine Lücke (_) in WEIHNACHTEN ein,
wenn du diagonal gehst, liegt eine Übereinstimmung (|) oder eine Nicht-Übereinstimmung (X) der jeweiligen Buchstaben in WINTER und in WEIHNACHTEN vor.
Überprüfe einmal, ob du das gleiche Alignment erhältst, das weiter oben angegeben ist, wenn du deine Distanz-Matrix vollständig ausgefüllt und mit Richtungspfeilen versehen hast. Es kann sein, dass du ein anderes Alignment erhältst, denn du hast gelegentlich die Wahl, ausgehend von welchem Nachbarfeld du ein Feld der Distanz-Matrix ausfüllst. Aber auch dein Alignment ist optimal, und deine Editierdistanz ist auf jeden Fall auch 6.
Aufgaben
Bestimme die Editierdistanz zwischen WINTER und SILVESTER. Du wirst feststellen, dass Silvester sogar noch WINTERlicher ist als Weihnachten.
Wenn du dich mit einem Tabellenkalkulationsprogramm wie Excel auskennst, erstelle eine Tabelle, die automatisch die Distanz-Matrix ausfüllt, wenn du Wörter buchstabenweise in die erste Zeile und die erste Spalte einträgst.
Ist es dir auch schon passiert, dass du "Dschungel" gelesen hast, obwohl dort "Duschgel" stand? Oder "Babylonier" statt "Babyboomer"? Oder "Amokläufer" statt "Autokäufer"? Bestimme die Editierdistanz zwischen diesen Wörtern.
Die Editierdistanz wird auch verwendet, wenn du in dein Handy das Wort EDITIERDISTANZ eintippst – du erhältst dann Vorschläge von Wörtern, die eine geringe Editierdistanz zu diesem Wort aufweisen, zum Beispiel WEITGEREIST oder EIERTANZ. Bestimme die Editierdistanz.
Der Kabarettist Horst Evers wollte einmal seinen Namen googeln: "horst evers". Daraufhin fragte Google: "Meinten Sie: worst ever?" Bestimme die Editierdistanz ohne den Algorithmus zu bemühen durch scharfes Hinsehen.
