Backtracing
aus Wikipedia, der freien Enzyklopädie
| Dieser Artikel oder Abschnitt ist unverständlich formuliert. Eine konkrete Begründung findet sich auf der Diskussionsseite des Artikels oder in der Versionsgeschichte. |
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.
