Dynamische Programmierung (DP) ist eine Methode um Optimisierungsprobleme zu
lösen. Hierbei wird das Problem in sich überlappende Teilprobleme unterteilt und eine
optimale Lösung zu jedem der Teilprobleme berechnet. Diese werden dann wiederrum zur
Gesamtlösung zusammengesetzt. Teillösungen werden in einer Tabelle gespeichert, sodass
jede Teillösung nur einmal berechnet werden muss. So kann ein Suchraum exponentieller
Größe in polynomieller Zeit durchsucht und eine optimale Lösung gefunden werden. Die
dynamische Programmierung wurde 1952 von Bellman entwickelt und eine der ersten
Anwendung war die Detektion von Tippfehlern beim Programmieren.
DP Algorithmen werden oft und sehr vielschichtig in der Bioinformatik angewendet
wie zum Beispiel beim Vergleich von Gensequenzen, Sequenzalignment genannt, oder der
Vorhersage von Molekülstrukturen. Die Menge an Daten und somit auch deren Analyse
steigt stetig an, weshalb neue und komplexere Datenstrukturen immer wichtiger werden.
Ein Ziel ist es deswegen, DP Algorithmen zu entwickeln, die auf komplexeren Daten-
strukturen als Strings angewendet werden können. Durch das Prinzip der algebraischen
dynamischen Programmierung (ADP) können DP Algorithmen in kleinere Bestandteile
zerlegt werden, die dann unabhängig voneinander weiterentwickelt und abgeändert werden
können.
Die Arbeit ist in zwei Teile gegliedert, wobei der erste Teil die theoretische Arbeit
zur Entwicklung von Algorithmen der dynamischen Programmierung beinhaltet. Hierbei
werden zuerst Prinzipien und Definitionen zur dynamischen Programmierung vorgestellt
(Kapitel 2), um ein besseres Verständnis der darauffolgenden Kapitel zu gewährleisten.
Der zweite Teil der Arbeit zeigt unterschiedliche bioinformatische Anwendungen von
DP Algorithmen auf biologische Daten. In einem ersten Kapitel (Kapitel 5) werden
Grundsätze biologischer Daten und Algorithmen vorgestellt, die dann in den weiteren
Kapiteln benutzt werden.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:38685 |
| Date | 11 March 2020 |
| Creators | Berkemer, Sarah Juliane |
| Contributors | Universität Leipzig |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | German |
| Type | info:eu-repo/semantics/updatedVersion, doc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0023 seconds