Digital Trivia

UPDATE: Ab sofort ist eine neuere Version verlinkt. Vielen Dank Martin für die Korrekturen und Verbesserungsvorschläge!

Früher oder später wird jeder Informatik Student im Laufe seines Studiums einmal mit dem Thema Sequence Alignment in Berührung kommen. Insbesondere für den Fachbereich Bioinformatik sind diese Algorithmen von Bedeutung. Sie werden dort für Sequenzvergleiche (z.B von Proteinsequenzen oder DNA) eingesetzt.

Im Rahmen eines Projekts sind Beschreibungen zu vier wichtigen Algorithmen des Sequence Alignments entstanden. Wenn sie dem ein oder anderen weiterhelfen hätten sie bereits ihren Zweck erfüllt.

Der Needleman-Wunsch-Algorithmus
Der Algorithmus ist von Needleman und Wunsch enthält einen grundlegenden, vielseitig erweiteraberen Ansatz um die Editier-Voerschrift zwischen zwei Zeichenketten zu berechnen. Viele, auf das Sequenz-Alignment spezialisierte Algorithmen beruhen auf der Idee des Needleman-Wunsch-Algorihtmus (alle der hier veröffentlichten). Er ist deshalb, trotz seiner Betagtheit auch heute noch von zentraler Bedeutung auf dem Gebiet.

Der Waterman-Smith-Beyer-Algorithmus
Der Algorithmus von Waterman, Smith und Beyer erlaubt es mit Hilfe von Gap-Penalty-Funktionen Gap-Bildungen in Alignments zu bevorzugen. Er macht außerdem keine genaueren Angaben zu der Penalty-Funktion und bietet somit viel Freiheit bei der Wahl der Funktion. Jedoch steht dem Flexibiliätsgewinn eine signifikant erhöhte Laufzeit gegenüber. Letzteres ist auch der Grund weshalb der Waterman-Smith-Beyer Algorithmus für die Praxis ungeeignet ist und kaum Einsatz findet. Schränkt man an die Gap-Penalty-Funktion auf affine Funktionen ein, lässt sich der Gotoh-Algorithmus (siehe unten) verwenden und die Laufzeit auf O(nm) absenken.

Der Gotoh-Algorithmus
Der Gotoh-Algorithmus erlaubt es Gap-Bildungen mittels affinen Gap-Panelty-Funktionen zu bevorzugen. Dabei bietet er die Laufzeitkomplexiät des Needleman-Wunsch-Algorithmus. Nachteile können zum einen im erhöhten Speicherverbrauch gesehen werden und zum Anderen darin, dass er in der Wahl der Gap-Panelty-Funktion nicht die Flexibilität des Waterman-Smith-Beyer-Algorithmus bieten kann sondern auf affine Funktionen begrenzt ist. Seine Stärke kann deshalb in dem Kompromiss aus beiden Ansätzen gesehen werden.

Der Smith-Waterman-Algorithmus
Der Smith-Waterman-Algorithmus stellt eine einfache Erweiterung des Needleman-Wunsch- Algorithmus dar um lokale Alignments zu finden. Es ergibt sich auch eine vergleichbare Laufzeit was durchaus überraschend erscheinen mag unter Anbetracht der Vielzahl von möglichen Teilsequenz-Paaren.