Backtracing

aus Wikipedia, der freien Enzyklopädie

Unter dem am häufigsten in der Bioinformatik (und speziell Sequenzanalyse) angewandten Begriff Backtracing (engl. Rückverfolgung) versteht man den Vorgang der Suche nach einem/allen optimalen Lösungswegen, wenn die optimale Lösung (also nur ihr Zahlenwert) bereits bekannt ist.

[Bearbeiten] Vorgehensweise

Hierzu müssen bei der Berechnung der numerischen Lösung die optimalen Lösungsknoten markiert werden, um sie später im Backtracing-Verfahren durchzuarbeiten. Als Technik dient dabei oft das Backtracking. (die beiden Begriffe werden oft verwechselt, bedeuten aber nicht das gleiche!)

[Bearbeiten] Beispiel

Ein Anwendungsbeispiel ist z.B. die Suche nach allen optimalen Alignments mit Hilfe der Edit-Distanz. Die Edit-Distanz lässt sich mit Hilfe der allgemeinen DP-Technicken (dynamic programming) errechnen. Um aber die optimalen Alignments herauszufinden, muss man anschließend Backtracing anwenden.

[Bearbeiten] Quelle

• Skript SequenzanalyseI von Dr. Sven Rahmann