Bitte verwenden Sie diesen Link, wenn Sie dieses Dokument zitieren oder verlinken wollen: https://nbn-resolving.org/urn:nbn:de:gbv:9-002610-2

Optimization Problems on Geometric Graphs and their Application to Visualizing Data

  • Today the process of improving technology and software allows to create, save and explore massive data sets in little time. "Big Data" are everywhere such as in social networks, meteorology, customers’ behaviour – and in biology. The Omics research field, standing for the organism-wide data exploration and analysis, is an example of biological research that has to deal with "Big Data" challenges. Possible challenges are for instance effcient storage and cataloguing of the data sets and finally the qualitative analysis and exploration of the information. In the last decade largescale genome-wide association studies and high-throughput techniques became more effcient, more profitable and less expensive. As a consequence of this rapid development, it is easier to gather massive amounts of genomic and proteomic data. However, these data need to get evaluated, analysed and explored. Typical questions that arise in this context include: which genes are active under sever al physical states, which proteins and metabolites are available, which organisms or cell types are similar or different in their enzymes’or genes’ behaviour. For this reason and because a scientist of any "Big Data" research field wants to see the data, there is an increasing need of clear, intuitively understandable and recognizable visualization to explore the data and confirm thesis. One way to get an overview of the data sets is to cluster it. Taxonomic trees and functional classification schemes are hierarchical structures used by biologists to organize the available biological knowledge in a systematic and computer readable way (such as KEGG, GO and FUNCAT). For example, proteins and genes could be clustered according to their function in an organism. These hierarchies tend to be rather complex, and many comprise thousands of biological entities. One approach for a space-filling visualization of these hierarchical structured data sets is a treemap. Existing algorithms for producing treemaps struggle with large data sets and have several other problems. This thesis addresses some of these problems and is structured as follows. After a short review of the basic concepts from graph theory some commonly used types of treemaps and a classification of treemaps according to information visualization aspects is presented in the first chapter of this thesis. The second chapter of this thesis provides several methods to improve treemap constructions. In certain applications the researcher wants to know, how the entities in a hierarchical structure are related to each other (such as enzymes in a metabolic pathway). Therefore in the 3 third chapter of this thesis, the focus is on the construction of a suitable layout overlaying an existing treemap. This gives rise to optimization problems on geometric graphs. In addition, from a practical point of view, options for enhancing the display of the computed layout are explored to help the user perform typical tasks in this context more effciently. One important aspect of the problems on geometric graphs considered in the third chapter of the thesis is that crossings of edges in a network structure are to be minimized while certain other properties such as connectedness are maintained. Motivated by this, in the fourth chapter of this thesis, related combinatorial and computational problems are explored from a more theoretical point of view. In particular some light is shed on properties of crossing-free spanning trees in geometric graphs.
  • Heutzutage erlauben neue Forschungsansätze und Technologien riesige Datenmengen schon in kurzer Zeit zu generieren und zu erkunden. Besonders im letzten Jahrzehnt sind die Methoden zur Generierung und Auswertung immer effizienter und damit auch kostengünstiger geworden. Die Endung -omics wird in der modernen Biologie für Teilgebiete verwandt, welche sich mit der Analyse einer größeren Gesamtheit beschäftigen (z.B. Genomics für die das ganze Genom eines Organismus umfassende Forschung) und lässt sich als ein gutes Beispiel für die Forschung an riesigen Datensätzen heranziehen. Typische Fragen der Omics-Forschungsgebiete sind: • Welche Gene sind unter verschiedenen Zuständen (z.B exponentielles Wachstum und Hitzestress) aktiv? • Welche Proteine und Metabolite sind während dieser Zustände für den Organismus verfügbar? • Welche Organismen haben ähnliche Reaktionen auf die verschiedenen Zustände, welche unterscheiden sich? Intuitiv verständliche Visualisierungen großer Datenmenge können zu möglichen Antworten dieser Fragen verhelfen und erfüllen dabei natürlich zusätzlich den Wunsch vieler Forscher, ihre Daten auch einmal in einer verständlichen Form ansehen zu können. Eine Möglichkeit große Datenmengen überblicken zu können, ist diese zu gruppieren. Hierarchische Strukturen wie Taxonomien und funktionelle Klassifizierungen können eine Möglichkeit hierfür sein. Beispielsweise können Enzyme anhand ihrer Funktion im Organismus gruppiert werden. Diese Hierarchien sind sehr komplex und können tausende von Instanzen enthalten. Treemaps sind eine Möglichkeit die großen und komplexen Hierarchien zu visualisieren, jedoch sind die Konstruktionsalgorithmen für Treemaps hinsichtlich der Komplexität und der Größe der Hierarchie begrenzt. In dieser Doktorarbeit werden Methoden vorgestellt um diese Grenzen zu verschieben. Nach einer kurzen Einführung in Graphentheorie und die Verwendung von Informationsvisualisierungen in der Biologie widmet sich die Doktorarbeit der Verbesserung der Treemap-Konstruktionsalgorithmen. Mit Hilfe eines Divide-and-Conquer Ansatzes können noch größere Treemaps erstellt werden. Dieser Ansatz kann für alle gängigen Konstruktionsalgorithmen verwendet werden. Desweiteren wird gezeigt, wie verbesserte Initialisierungsmethoden die Übersichtlichkeit und die Vergleichbarkeit von Treemaps deutlich verbessern können. Um einen besseren Überblick auf die zugrunde liegenden Daten und ihre Verknüpfungen zu erhalten, wird im mittleren Teil der Arbeit eine neue Visualisierungsmethode entwickelt, welche es erlaubt, eine spezielle Netzwerkvisualisierung über eine Treemap zu legen. So kann zum Beispiel eine Treemap, welche Enzyme anhand ihrer Funktionen gruppiert, um Informationen über Stoffwechselwege erweitert werden. Dies ermöglicht es einen ganz neuen und inspirierenden Blick auf diese Daten zu werfen. Die Optimierung dieser Netzwerke in Bezug auf ihre überkreuzungsfreien, geometrischen Darstellungen führt zu vertieften Forschungen an weiteren Problemstellungen zu geometrischen Graphen1 vor allem zu überkreuzungsfreien Spannbäumen. Alles in allem ist und bleibt die Analyse und Untersuchung von großen Datensätzen ein interessantes Forschungsfeld mit vielen Herausforderungen. Jedoch könnten die in der Doktorarbeit vorgestellten Methoden und Algorithmen dazu beitragen, die typischen Fragestellungen der Omics-Forschungsfelder besser zu verstehen und einige Antworten darauf abzuleiten.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author: Julia Schüler
URN:urn:nbn:de:gbv:9-002610-2
Title Additional (German):Geometrische Graphen und deren Anwendung auf Treemaps
Advisor:Prof. Dr. Andreas Spillner
Document Type:Doctoral Thesis
Language:English
Date of Publication (online):2016/08/29
Granting Institution:Ernst-Moritz-Arndt-Universität, Mathematisch-Naturwissenschaftliche Fakultät (bis 31.05.2018)
Date of final exam:2016/04/01
Release Date:2016/08/29
Tag:Informationsvisualisierung, Treemap
GND Keyword:Algorithmus, Darstellung, Enzym, Graph, Graphentheorie, Hierarchie, Netzwerk, Spannender Baum, Stoffwechselweg, Taxonomie, Visualisierung
Faculties:Mathematisch-Naturwissenschaftliche Fakultät / Institut für Mathematik und Informatik
DDC class:500 Naturwissenschaften und Mathematik / 510 Mathematik