Erweiterte
Suche ›

Multivariate Algorithmics in Biological Data Analysis

Buch
13,90 € Preisreferenz Lieferbar in 2-3 Tagen

Kurzbeschreibung

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.

Details
Schlagworte

Titel: Multivariate Algorithmics in Biological Data Analysis
Autoren/Herausgeber: Johannes Uhlmann
Ausgabe: Neuausgabe

ISBN/EAN: 9783798323513

Seitenzahl: 186
Format: 24 x 17 cm
Produktform: Taschenbuch/Softcover
Gewicht: 335 g
Sprache: Englisch

buchhandel.de - Newsletter
Möchten Sie sich für den Newsletter anmelden?


Bitte geben Sie eine gültige E-Mail-Adresse ein.
Lieber nicht