Approximative Stringsuche

Hallo,

ich hab einen sehr großen String (~5 bis 6 Millionen Zeichen DNA-Sequenz) und möchte dort alle Vorkommen von vielen sehr viel kleineren Pattern (~ 30 bis 40 Zeichen) mit bis zu k Fehlern finden (nur Substitutionen, keine Insertionen/Deletionen).
Ich habe bereits ein paar Sachen ausprobiert, bin von der Perfomance aber noch nicht überzeugt. Einmal ein abgeänderter Boyer-Moore-Horspool mit Fehlertoleranz und einmal eine Suche mit regulären Ausdrücken (Sprache ist Python, ist aber unerheblich für die Frage). 12 Pattern brauchen mit Horspool bei mir 40 Sekunden, mit regulären Ausdrücken 17 Sekunden, das hätte ich aber gern noch ein bisschen besser. Herumexperimentieren mit Levenshtein/Hamming war noch sehr viel langsamer.

Google hat leider bei dem Thema nicht so viel geholfen (Schlagworte fuzzy und approximate matching), exakte Suche in sehr viel schnellerer Zeit ist kein Problem, aber bei der Fehlertoleranz hörts dann auf. Ich hatte gehofft, dass man auch hier mit Suffixtrees o.ä. arbeiten kann, habe aber noch nichts konkretes gefunden (bis auf ein paar für mich unverständliche Papers). Hätte da vielleicht jemand spontan einen konkreteren Tipp/Link?

Was noch vielversprechend aussieht ist das Backward Oracle Matching, das ist wie Horspool für eine exakte Suche gedacht, aber für mein kleines Alphabet und meine Patternlänge deutlich(!) effektiver (Implementierung liegt vor). Leider schaffe ich es nicht, den Algo für Fehlertoleranz abzuändern. Habe bis jetzt auch noch nicht rausgefunden, ob das überhaupt möglich ist. Auch hier die Frage: Weiß jemand mehr bei diesem Algo?