Multivariate Algorithmics in Biological Data Analysis

Johannes Uhlmann (Autor)

Buch | Softcover

X, 186 Seiten

2011
Universitätsverlag der TU Berlin
978-3-7983-2351-3 (ISBN)

Infos

The focus of the thesis is on the development of fixed-parameter algorithms for NP-hard problems arising in computational biology. The considered problems model tasks in data clustering, construction of phylogenetic trees, predicting information on the three-dimensional structure of proteins, and haplotype inference. Many combinatorial problems in the field of computational biology have turned out to be NP-hard. It is commonly believed that there exist no efficient, that is, polynomial-time algorithms for NP-hard problems. Parameterized algorithmics provides an approach to tackle NP-hard problems that has already proven to be successful in bioinformatics. The basic idea is to consider besides the input size a secondary measurement capturing an additional aspect of the input instance, the parameter. Then, the goal is to find algorithms such that the nonpolynomial part of the running time depends only on the parameter. For small parameter values such a parameterized algorithm might constitute an efficient solving strategy. Multivariate algorithmics extends a parameterized algorithm analysis in the sense that it investigates the influence of several parameters on the computational complexity of a problem. The main contributions of the thesis to the known algorithmic results are twofold. First, parameterized algorithms with better running times as known parameterized algorithms are developed for some of the considered problems. Second, the parameterized complexity investigations are extended by considering new parameterizations leading to new solving strategies for some of the considered problems. In particular, this thesis initiates a multivariate complexity study for some of the considered problems. An important algorithmic technique employed in the thesis is kernelization. Here the goal is to transform a given instance in polynomial time into an equivalent instance whose size is bounded by a function only depending on the parameter value. In this sense, kernelization can be seen as polynomial-time preprocessing with provable performance guarantee. Hence, the kernelizations developed in this thesis are not only relevant in the field of parameterized algorithmics but constitute a general contribution to solving the considered problems. Die Arbeit beschäftigt sich mit der Entwicklung parametrisierter Algorithmen zum Lösen NP-schwerer Probleme, die ihren Ursprung in der algorithmischen Bioinformatik haben. Die betrachteten Probleme modellieren Aufgaben in der Clusteranalyse, in der Konstruktion phylogenetischer Bäume, in der Vorhersage der räumliche Anordnung der Aminosäuren eines Proteins, sowie in der Bestimmung von Haplotypen. Viele kombinatorische Probleme aus dem Bereich der algorithmischen Bioinformatik haben sich als NP-schwer herausgestellt. Dies bedeutet, dass diese Probleme im Allgemeinen wahrscheinlich nicht effizient, das heißt in Polynomzeit, gelöst werden können. In diesem Kontext bietet die parametrisierte Algorithmik einen Ansatz zum Lösen NP-schwerer Probleme, der sich bereits als erfolgreich erwiesen hat. Die Idee hierbei ist, neben der Eingabegröße einen Parameter zu betrachten, welcher eine zusätzliche Charakteristik der Eingabe misst. Das Ziel ist dann einen Algorithmus anzugeben, dessen nichtpolynomieller Laufzeitanteil nur vom Parameter abhängt. Für Instanzen, bei welchen der betrachtete Parameter kleine Werte annimmt, kann ein solcher parametrisierter Algorithmus ein effizientes Lösungsverfahren liefern. Die Multivariate Algorithmik erweitert die Parametrisierte Algorithmik dahingehend, dass hier der Einfluss mehrerer Parameter auf die Berechnungskomplexität eines Problems untersucht wird. Die Arbeit erweitert die bestehenden Ergebnisse für die betrachteten Probleme in zweierlei Hinsicht. Erstens werden parametrisierte Algorithmen angegeben, welche schneller sind als bisher bekannte parametrisierte Algorithmen. Zweitens werden die parametrisierten Untersuchungen der betrachteten Probleme ergänzt, indem neue Parametrisierungen betrachtet werden, was teilweise zu neuen Lösungsansätzen führt. Insbesondere initiiert die Arbeit für einige der betrachteten Probleme eine multivariate Komplexitätsanalyse. Ein technischer Schwerpunkt der Arbeit liegt auf der Entwicklung effizienter Verfahren zur Datenreduktion bzw. Polynonmzeitvorverarbeitung und deren theoretischer Analyse. In der parametrisierten Algorithmik spricht man von einer Kernelisierung, wenn sich eine Probleminstanz in Polynomzeit dergestalt reduzieren bzw. vorverarbeiten lässt, dass die Größe der entstehenden, äquivalenten Instanz (der Problemkern) nur vom Parameterwert abhängt. In diesem Sinne handelt es sich bei einer Kernelisierung um Polynomzeitvorverarbeitung mit beweisbarer Güte. Die in der Arbeit entwickelten Kernelisierungen stellen somit einen allgemeinen Beitrag zum Lösen der betrachteten Probleme dar, dessen Relevanz nicht allein auf das Gebiet der parametrisierten Algorithmik beschränkt ist.

Produkt-Details

• Erscheint lt. Verlag: 4.8.2011
• Verlagsort: Berlin
• Sprache: englisch
• Maße: 170 x 240 mm
• Gewicht: 335 g
• Einbandart: Paperback
• Themenwelt: Informatik ► Theorie / Studium ► Algorithmen
• Themenwelt: Informatik ► Weitere Themen ► Bioinformatik
• Schlagworte: algorithmische Bioinformatik • Bioinformatik • Effizienter Algorithmus • Kernelisierung • Multivariate Analyse • NP-hartes Problem • Parametrisierte Algorithmen
• ISBN-10: 3-7983-2351-8 / 3798323518
• ISBN-13: 978-3-7983-2351-3 / 9783798323513
• Zustand: Neuware