Obwohl der EXAKTE Musterabgleich mit Suffixbäumen schnell ist, ist nicht klar, wie man Suffixbäume für den GENAUEN Musterabgleich verwenden kann. Im Jahr 1994 erfanden Michael Burrows und David Wheeler einen genialen Algorithmus zur Textkomprimierung, der heute als Burrows-Wheeler-Transformation bekannt ist. Sie wussten nichts über Genomik und konnten sich nicht vorstellen, dass ihr Algorithmus 15 Jahre später zum Arbeitspferd von Biologen werden würde, die nach genomischen Mutationen suchen. Aber was hat die Textkomprimierung mit dem Musterabgleich zu tun? In dieser Lektion lernen Sie, dass das Schicksal eines Algorithmus oft schwer vorherzusagen ist - seine Anwendungen können in einem Bereich auftauchen, der nichts mit dem ursprünglichen Plan seiner Erfinder zu tun hat.

Herzlichen Glückwunsch, Sie haben jetzt die wichtigsten Konzepte des Mustervergleichs gelernt: Versuche, Suffixbäume, Suffix-Arrays und sogar die Burrows-Wheeler-Transformation! Einige der von Pavel erwähnten Ergebnisse bleiben jedoch rätselhaft: Wie können wir z.B. einen exakten Musterabgleich in O(|Text|)-Zeit durchführen und nicht in O(|Text|*|Muster|)-Zeit wie bei dem naiven Brute-Force-Algorithmus? Wie kann es sein, dass der Abgleich eines 1000-Nukleotid-Musters mit dem menschlichen Genom fast so schnell ist wie der Abgleich eines 3-Nukleotid-Musters? Und obwohl Pavel gezeigt hat, wie man mit dem Suffixbaum schnell ein Suffix-Array konstruieren kann, hat er die Magie hinter den schnellen Algorithmen für die Konstruktion des Suffixbaums nicht enthüllt... In diesem Modul wird Miсhael einige algorithmische Herausforderungen ansprechen, die Pavel versucht hat, vor Ihnen zu verbergen :) wie z.B. den Knuth-Morris-Pratt-Algorithmus für den exakten Musterabgleich und effizientere Algorithmen für die Konstruktion von Suffixbäumen und Suffix-Arrays.

In diesem Modul setzen wir die Untersuchung der algorithmischen Herausforderungen der String-Algorithmen fort. Sie werden einen O(n log n)-Algorithmus für die Konstruktion von Suffix-Arrays und einen Algorithmus mit linearer Zeit für die Konstruktion eines Suffix-Baums aus einem Suffix-Array kennenlernen. Außerdem werden Sie diese Algorithmen und den Knuth-Morris-Pratt-Algorithmus in der letzten Programmieraufgabe dieses Kurses implementieren.