Complexity Analysis of Tries and Spanning Tree Problems
| Autor: | Eckhardt, Bernd Stefan |
|---|---|
| Přispěvatelé: | Mayr, Ernst W. (Prof. Dr.), Kemper, Alfons (Prof., Ph.D.) |
| Jazyk: | angličtina |
| Rok vydání: | 2010 |
| Předmět: |
Tries
Retrieval Trees Smoothed Analysis Mealy-type perturbation functions edit perturbations star-like perturbation functions Additive Tree Spanners NP hardness Graph approximating spanning Trees Centrality Approximating spanning Trees ddc:000 Informatik Wissen Systeme Tries Retrieval Trees Smoothed Analysis Mealy-type perturbation functions Edit-Pertrubationen stern-ähnliche Stringperturbationsfunktionen Additive Baumspanner NP Vollständigkeit Zentralitäten Approximierende Spannbäume |
| Popis: | In this thesis, we consider two combinatorial problems which are fundamental for many computational tasks, for example in contemporary bioinformatics: in the first part, we investigate how well a given network can be abstracted by its spanning trees. Networks are an important tool for modeling relational data such as metabolic networks and finding good network abstractions is a key ingredient for algorithmic analysis of such networks; in the second part, we perform a smoothed analysis of trie height in order to give a sound mathematical explanation for the good practical performance of tries in string matching tasks. String matching operations on DNA or protein sequences are among the most important kind of operations in bioinformatics applications. The importance of those operations is based on the assumption that the function of a gene or protein and its sequence encoding are strongly related. In dieser Arbeit werden zwei kombinatorische Probleme analysiert, die insbesondere durch Fragen aus dem Bereich der Bioinformatik motiviert sind. Im ersten Teil der Arbeit wird untersucht, inwieweit ein gegebenes Netzwerk durch einen seiner Spannbäume abstrahiert werden kann. Netzwerke treten im Bereich der Bioinformatik immer dann auf, wenn relationale Daten modelliert werden müssen. Ein Beispiel sind metabolische Netzwerke. Das Finden von guten Netzwerkabstraktionen stellt einen wichtigen Schritt für die algorithmische Analyse solcher Netze dar. Im zweiten Teil der Arbeit wird das Paradigma der Smoothed Analysis auf die Höhe von Tries angewandt, um deren gutes Laufzeitverhalten in praktischen Anwendungen besser zu erklären. Tries werden in String Matching Operationen verwendet, die deshalb so wichtig für die Bioinformatik sind, weil ein enger Zusammenhang zwischen der Funktion und der Sequenzdarstellung von Genen und Proteinen angenommen werden kann. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|