Parts | Days | Selection | Search | Downloads | Help

CP: Chemische Physik

CP 14: Biologische Systeme

CP 14.2: Talk

Wednesday, March 11, 1998, 14:20–14:40, H19

Das Skalierungsverhalten von Algortihmen zur Globalen Optimierung für das Protein-Faltungsproblem — •W. Wenzel und Kay Hamacher — Theoretische Physik I, Universität Dortmund

An einem einfachen Modell untersuchen wir das Skalierungsverhalten des numerischen Aufwandes verschiedener Algorithmen, die zur ab-initio Vorhersage der Molekülstruktur von Proteinen vorgeschlagen wurden, in Abängigkeit von der Systemgröße sowohl im Kontinuum wie auf dem Gitter. Unsere Untersuchungen dieses NP-harten Modells im Kontinnuum zeigen, daß die weithin verfolgte Strategie der “thermodynamischen” Optimierungsverfahren, wie z.B.in Monte-Carlo Methoden, den gleichen Skalierungsexponenten hat wie die lokale Minimierung zufällig gewählter Anfangsbedingungen. Auf dem Gitter hingegen unterscheiden sich die Ergebnisse der verschiedenen Verfahren erheblich, insbesondere zeigt der “triviale” Zugang hier das erwartete exponentialle Wachstum des numerischen Aufwands mit der Systemgröße. Die Implikationen dieser Ergebnisse auf das realistische Problem werden diskutiert.