Powered by MyCoRe


Titel:Fixed-parameter algorithms for some combinatorial problems in bioinformatics
Autor:Dr. rer. nat. Bui, Quang Bao Anh [Autor]
Dateien:
[Dateien anzeigen]ASCII Text, Adobe PDF
[Details]10,79 MB in 2 Dateien
[ZIP-Datei erzeugen][PlugIn/Viewer Download]
Dateien vom 12.05.2011 / geändert 12.05.2011
URL für Lesezeichen:http://www.db-thueringen.de/servlets/DocumentServlet?id=18295
URN (NBN):urn:nbn:de:gbv:27-20110512-120736-3
Kollektion:Dissertationen/Habilitationen
Status:Dokument veröffentlicht
Sprache:Deutsch
Dokumententyp:Dissertation
Medientyp:Text
Beitragende:Prof. Dr. Böcker, Sebastian [Gutachter]
Dr. Hildebrandt, Andreas [Gutachter]
Stichwörter:NP-hartes Problem, Algorithmus
Dewey Decimal Classification:000 Informatik, Informationswissenschaft, allgemeine Werke » 000 Informatik, Wissen, Systeme » 006 Spezielle Methoden der Informatik
Andere Dokumente dieser Kategorie
Evaluationstyp:Für die Langzeitarchivierung vorgesehen
Beschreibung:Fixed-parameterized algorithmics has been developed in 1990s as an approach to solve NP-hard problem optimally in a guaranteed running time. It offers a new opportunity to solve NP-hard problems exactly even on large problem instances.

In this thesis, we apply fixed-parameter algorithms to cope with three NP-hard problems in bioinformatics:

Flip Consensus Tree Problem is a combinatorial problem arising in computational phylogenetics. Using the formulation of the Flip Consensus Tree Problem as a graph-modification problem, we present a set of data reduction rules and two fixed-parameter algorithms with respect to the number of modifications. Additionally, we discuss several heuristic improvements to accelerate the running time of our algorithms in practice. We also report computational results on phylogenetic data.

Weighted Cluster Editing Problem is a graph-modification problem, that arises in computational biology when clustering objects with respect to a given similarity or distance measure. We present one of our fixed-parameter algorithms with respect to the minimum modification cost and describe the idea of our fastest algorithm for this problem and its unweighted counterpart.

Bond Order Assignment Problem asks for a bond order assignment of a molecule graph that minimizes a penalty function. We prove several complexity results on this problem and give two exact fixed-parameter algorithms for the problem. Our algorithms base on the dynamic programming approach on a tree decomposition of the molecule graph. Our algorithms are fixed-parameter with respect to the treewidth of the molecule graph and the maximum atom valence. We implemented one of our algorithms with several heuristic improvements and evaluate our algorithm on a set of real molecule graphs. It turns out that our algorithm is very fast on this dataset and even outperforms a heuristic algorithm that is usually used in practice.
Hochschule/Fachbereich:Friedrich-Schiller-Universität Jena » Fakultät für Mathematik und Informatik
Dokument erstellt am: 12.05.2011
Dateien geändert am: 12.05.2011
Datum der Promotion: 11.01.2011