On the reconstruction of optimal solutions in methods of dynamic programming for the sequence analysis (Q2763528)

Aus der Zusammenfassung: Methoden der Dynamischen Programmierung sind ein wichtiges und in der Sequenzanalyse weit verbreitetes Paradigma zum Entwurf effizienter Algorithmen für diskrete Optimierungsprobleme. Eine besondere Ausprägung stellt dabei die sogenannte ``Lichte Dynamische Programmierung'' dar, die unter Ausnutzung zusätzlicher struktureller Eigenschaften der Probleme eine weitere Effizienzsteigerung der Verfahren erlaubt. Neben dem Wert einer optimalen Lösung ist oft die Rekonstruktion einer optimalen Lösung, die in der Regel nicht eindeutig ist, erforderlich. Dies geschieht typischerweise mittels eines für die Dynamische Programmierung üblichen ``Trace-Back-Schrittes''.NEWLINENEWLINENEWLINEEine Rekonstruktion aller optimalen Lösungen stößt bei Verwendung der ``Lichten Dynamischen Programmierung'' allerdings auf erhebliche Schwierigkeiten wie das Beispiel der Berechnung längster gemeinsamer Teilsequenzen (LCS-Problem) zeigt. Viele Probleme der Sequenzanalyse sind jedoch in dem Sinne symmetrisch, daß die Leserichtung der Strings für die Struktur optimaler Lösungen unerheblich ist. Unter Verwendung dieser Symmetrieeigenschaft wurde eine neue Charakterisierung längster gemeinsamer Teilsequenzen gegeben. Diese bildete die Grundlage, um für zwei verschiedene Ansätze der ``Lichten Dynamischen Programmierung'' geeignete Kriterien zu entwickeln, die eine effiziente Berechnung aller optimalen Lösungen ermöglichen. Konkret konnte gezeigt werden, daß die asymptotische Zeitkomplexität bisheriger Algorithmen für das LCS-Problem mit Hilfe der entwickelten Methodik unverändert aufrecht erhalten werden kann. Ferner erlauben die gefundenen Charakterisierungen eine sehr kompakte Beschreibung aller optimalen Lösungen. Diese kann sowohl für eine platzsparende Archivierung verwendet werden als auch bei der Entwicklung von Verfahren hilfreich sein, die Berechnungen auf der Menge aller optimalen Lösungen durchführen.