Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Wissensmanagement in der Bioinformatik

Neue Entwicklungen im Datenbankbereich und in der Bioinformatik

• wann? Dienstag, 11-13 c.t.
• wo? RUD 25, 4.112

Dieses Seminar wird von den Mitgliedern der beiden Arbeitsgruppen als Forum der Diskussion und des Austauschs genutzt. Studenten und Gäste sind herzlich eingeladen.

Folgende Termine und Vorträge sind bisher vorgesehen:

Zusammenfassungen

Executing SPARQL Queries over the Web of Linked Data (Olaf Hartig)

The Web of Linked Data forms a single, globally distributed dataspace. Due to the openness of this dataspace, it is not possible to know in advance all data sources that might be relevant for query answering. This openness poses a new challenge that is not addressed by traditional research on federated query processing. In this paper we present an approach to execute SPARQL queries over the Web of Linked Data. The main idea of our approach is to discover data that might be relevant for answering a query during the query execution itself. This discovery is driven by following RDF links between data sources based on URIs in the query and in partial results. The URIs are resolved over the HTTP protocol into RDF data which is continuously added to the queried dataset. This paper describes concepts and algorithms to implement our approach using an iterator-based pipeline. We introduce a formalization of the pipelining approach and show that classical iterators may cause blocking due to the latency of HTTP requests. To avoid blocking, we propose an extension of the iterator paradigm. The evaluation of our approach shows its strengths as well as the still existing challenges.

Graph-Based Ontology Construction from Heterogeneous Evidences (Christoph Böhm)

Ontologies are tools for describing and structuring knowledge, with many applications in searching and analyzing complex knowledge bases. Since building them manually is a costly process, there are various approaches for bootstrapping ontologies automatically through the analysis of appropriate documents. Such an analysis needs to find the concepts and the relationships that should form the ontology. However, the initial set of relationships is usually inconsistent and rather imbalanced - a problem which was mostly ignored so far. In the paper, we define the problem of extracting a consistent as well as properly structured ontology from a set of inconsistent and heterogeneous relationships. Moreover, we propose three graph-based methods for solving the ontology extraction problem and evaluate them on a large data set of >325K documents against a gold standard ontology comprising >12K relationships. Our study shows that an algorithm based on a modified formulation of the dominating set problem outperforms greedy methods. The talk presents the original paper and will soon be held at ISWC 2009.

Chemical Structure Search for Text Corpora (Marc Bux)

Legacy data in life sciences is often available as text-only. In many cases it would be desirable to find out which particular chemical moieties have been discussed and used in earlier projects. Therefore we want to establish a chemistry search with extended functionality and combine it with a keyword search. This involves testing several available chemical extractors against a pre-defined set of annotated documents. The best-performing application is then used to identify chemical entities in a rich set of documents. The chemical names are converted to a machinereadable representation (InChI) and fed into an index where each molecule is linked back to the appropriate document records. Then, a basic search interface is set up which can be used to draw structures and specify keywords in order to run a combined search. The structure search can ultimately be enhanced to work with major document databases in order to deduce new scientific evidence by formulating intelligent queries.

Zitationsanalyse mit Nutch und Lucene (Hagen Zahn)

Um eine relevante Auswahl aus einem Bestand wissenschaftlicher Dokumente treffen zu können, ist ein Informationssystem notwendig, dass die Reputation eines Dokumentes anhand seiner Zitationen korrekt bestimmen kann. Sind keine Zitationsinformationen verfügbar, müssen diese aus dem Datenbestand extrahiert werden. Diesen Prozess nennt man Zitationsanalyse. Er stellt die zentrale Komponente vieler Suchmaschinen für wissenschaftliche Dokumente dar. Die vorliegende Arbeit gibt einen kurzen Überblick über Grundlagen der Zitationsanalyse. Darüber hinaus wird ein System vorgestellt, welches eine maschinelle Zitationsanalyse für einen beliebigen Bestand an wissenschaftlichen Dokumenten realisiert. Die gewonnenen Zitationsinformationen sollen für das Ranking einer Suchanfrage eines bestehendes Nutch Systems nutzbar sein. Das System wurde für das Nutch System für wissenschaftliche Dokumente des DBIS Lehrstuhls der HU Berlin entwickelt und wurde darauf getestet.

Relationsextraktion durch Frequent Pattern in Dependency Graphen (Stefan Pietschmann)

Biomedizinische Forschungsergebnisse werden größtenteils in Textform veröffentlicht. Um aus den Publikationen automatisch relevante Informationen zu extrahieren, bietet sich deshalb der Einsatz von (computer-)linguistischen Verfahren an, welche zum Beispiel die grammatische Struktur des Textes analysieren. In diesem Vortrag wird ein System vorgestellt, welches aus einem vorliegenden Text automatisch Protein-Protein-Interaktionen extrahiert, indem der Text nach Syntaxgraph-Pattern (genauer: Dependency Graph Pattern) durchsucht wird. Hauptanliegen bei der Entwicklung des Systems war, die benötigten Pattern weitestgehend automatisch zu erstellen. Zu diesem Zweck wurden Verfahren entwickelt und getestet, um die Pattern zum einen aus einem (ebenfalls automatisch erstellten) Lernkorpus zu extrahieren und zum anderen durch verschiedene Patternfilter und -generalisierer qualitativ zu verbessern. Darüber hinaus wurde das Konzept des Frequent Subgraph Mining angewandt und getestet, um die These zu untersuchen, ob im Lernkorpus häufig vorkommende Syntaxsubgraphen als Pattern geeignet sind. Die einzelnen Verfahren werden im Vortrag erläutert und evaluiert.

Mayday - Visual Analytics for Expression Data (Florian Battke)

DNA Microarrays have become the standard method for large scale analyses of gene expression and epigenomics. The increasing complexity and inherent noisiness of the generated data makes visual data exploration ever more important. Fast deployment of new methods as well as a combination of predefined, easy to apply methods with programmer’s access to the data are important requirements for any analysis framework. Mayday is an open source platform with emphasis on visual data exploration and analysis. Many built-in methods for clustering, machine learning and classification are provided for dissecting complex datasets. Plug-ins can easily be written to extend Mayday’s functionality in a large number of ways. As Java program, Mayday is platform- independent and can be used as Java WebStart application without any installation. The presentation will show Mayday's functionality from the users' as well as the programmers' points of view.

Knowledge Management and Discovery for Genotype/Phenotype Data (Philip Groth)

Phenotypes often visibly reflect the health state of organisms. Especially in diseases with a genetic component, examination of the phenotype can aid understanding the underlying genetics. Many technologies to generate phenotypes systematically and in a high-throughput manner have been developed to decipher functions for genes. It is still a major challenge, however, to interpret the results of large-scale functional screens, even more so if heterogeneous data sets are to be combined. I present methods for knowledge discovery in phenotypes across species and screening technologies. PhenomicDB version 2, a multi-species genotype/phenotype database, is an approach to integrate and show genotype and phenotype data on a large scale, using orthologies to show phenotypes across species. I focus on the incorporation of quantitative and descriptive RNAi screening data with the usage of phenotype ontology terms and by providing information on assays and cell lines. I present the results of a study in which phenotype data from PhenomicDB is taken to predict gene annotation utilizing text clustering. The resulting clusters correlate well with several indicators for biological coherence in gene groups, such as functional annotations from the Gene Ontology (GO) and protein-protein interactions. Finally, I give an outlook on PhenomicDB version 3 in which the phenotype clusters as well as measures for gene similarity are combined to enable systematic discovery and prediction of novel genes functions.

Bewertung und Intergration von Pathways (Oliver Arnold)

Um den Ablauf von komplexen biologischen Prozessen zu verstehen werden mittels DNA-Microarrays Expressionslevel von Genen ermittelt. Es gibt unterschiedliche Ansätze um die von Microarrays generierten Daten zu analysieren - eine einheitliche Vorgehensweise existiert jedoch nicht. Im Rahmen dieser Arbeit wurde eine Methode entwickelt um Genexpressionsveränderungen zu bewerten. Dabei werden Genexpressionsdaten Molekülen (Proteinen, Enzyme, etc.) in Pathways zuordnet und über Interaktionen zwischen den Molekülen propagiert. Die Propagierung von Genexpressionen soll regulatorische Faktoren beim zweiten Schritt der Proteinsynthese - die Translation - vereinfacht simulieren. Pathays bestehen aus einer Menge von molekularen Interaktionen, die eine bestimmte Funktion innerhalb einer Zelle erfüllen. Es wurden Pathways aus unterschiedlichen Datenbanken in eine lokale Datenbank importiert. Des Weiteren wurden gemeinsame Subgraphen zwischen Pathways verschiedener Datenbanken ermittelt, um identische Expressionsveränderungen für eine Gruppe von Molekülen in unterschiedlichen Pathways leichter identifzieren zu können.

Robin: An intuitive wizard application for R-based microarray quality assessment and analysis (Marc Lohse)

The wide application of high-throughput transcriptomic analysis using microarrays has generated a plethora of different technical platforms, data repositories and sophisticated statistical analysis methods, leaving the individual scientist with the problem of choosing the appropriate approach to successfully address his biological question. Several software applications that provide a rich environment for microarray analysis and data storage are available (e.g. GeneSpring, EMMA2), but these are mostly commercial or require an advanced informatics infrastructure. What has been lacking, is a non-commercial, easy-to-use graphical application that aids the lab researcher in finding the proper method to analyze microarray data without requiring expert understanding of the complex underlying statistics. We have developed Robin, a Java-based graphical wizard application that harnesses the power of the advanced statistical analysis functions provided by the R/BioConductor project. To aid inexperienced users, Robin implements a streamlined workflow guiding through all steps of two-color, generic single color and Affymetrix microarray analysis, providing in-line help and documentation. Being more than just a graphical user interface to BioConductor functions, Robin also assesses the data and automatically generates warnings to notify the user of potential outliers, low quality chips and low statistical power.

From classical Probabilistic Graphical Models to Conditional Random Fields: Feature Modelling and Applications in Named Entity Recognition (Roman Klinger)

Conditional Random Fields (CRF) are a class of probabilistic models related to well-established methods like Maximum Entropy, Hidden Markov Models or Bayesian Networks. I will explain how these methods can be compared to CRFs and what typical application areas are. An an example, the common task of gene/protein recognition and detection of chemical names will be explained. The task of selecting the most important parameters, i.e, the features representing the text, will be discussed in more detail. Evaluation issues of NER-systems based on CRFs are briefly mentioned.

Multitask Learning with a Hidden Markov Perceptron (Fabian Moessner)

The Natural Language Processing (NLP), which deals with problems like Information Extraction or Automatic Summarization, is based on several subtasks as Part Of Speech tagging or Named Entity Recognition. Often these subtasks are separately processed, using sequential classifiers, such as Hidden Markov Models or Conditional Random Fields. But when the learned features of one subtask are simply passed on to another subtask of the NLP, the errors are propagated. Thus the presented Studienarbeit shows a sequential multitask learner which is able to train with two subtasks jointly at a time, thereby including the dependencies of the different subtasks. This discriminative learning technique is based on a Graphical Model, whose parameters are iteratively trained through a Perceptron and which is able to integrate kernel functions.

Anwendungsintegration mit Oracle am konkreten Beispiel (Dr. Hilmar Schuschel)

An einem Beispiel, das an ein reales Kundenszenario angelehnt ist, werden die notwendigen Schritte zur Anwendungsintegration auf Basis der Oracle Application Integration Architecture (AIA) gezeigt. Eine Demonstration der beteiligten Werkzeugkette vermittelt einen Eindruck von der Arbeitsweise bei Umsetzung und Validierung. Der Fokus auf ein konkretes Szenario macht die Konzepte und technischen Bestandteile von AIA deutlich und zeigt, wie mithilfe von vorgefertigten Komponenten die Anwendungsintegration beschleunigt und vereinfacht werden kann.

BioSeqDB: Analyse großer DNA Datenbestände mittels deklarativer Anfragebearbeitung (Uwe Röhm)

Moderne DNA Sequenzierungstechnologien ermöglichen es, indivuelle Genome innerhalb weniger Wochen und für einen Bruchteil der Kosten des ursprünglichen Human Genome Projekts zu sequenzieren. Die beteiligten Labore sehen sich dabei einer ungeahnten Datenflut in der Größenordnung mehrerer Terrabytes pro Woche gegenüber, die zeitnah verarbeitet und analysiert werden soll. Die derzeit eingesetzten Informationstechniken stossen bei einem solchen Datenvolumen jedoch an ihre Grenzen. In dem BioSeqDB Projekt der Universität Sydney untersuchen wir das Potential und die Anwendbarkeit erweiterbarer Datenbanksystemen als Plattform für die genomische Datenanalyse. Die Hauptaugenmerke liegen dabei auf der effizienten Speicherung grosser DNA Datenbestände, sowie der Verwendung deklarativer Anfragen und benutzer-definierter Operatoren für die Analyse der DNA Daten innerhalb der Datenbankplattform. Der Vortrag gibt einen Überblick einer ersten Machbarkeitsstudie anhand des 1000 Genome Projekts, die in Zusammenarbeit mit Microsoft und dem Wellcome Trust Sanger Institute durchgeführt wurde. Diese Studie bediente sich erstmals der CLR Integration des SQL Server 2008 für die Verwaltung und Verarbeitung der Sequenzierungsdaten. Im nächsten Schritt untersuchen wir, wie verschiedene DNA Datenbestände mittels SQL effizient zueinander in Beziehung gesetzt und auf Unterschiede und Gemeinsamkeiten analysiert werden können.

Caching für verweisbasierte Anfragebearbeitung im Web of Linked Data (Jan Wehrs)

Verweisbasierte Anfragebearbeitung im Web of Linked Data ist eine Methode, SPARQL-Anfragen auf den global verteilten RDF-Daten im Web auszuführen. Während der Berechnung der Ergebnismenge werden Verweise (repräsentiert durch URIs) in der Anfrage und in bereits berechneten Teilergebnissen verfolgt, um neue Datenquellen zu entdecken. Da URIs während der Bearbeitung von aufeinander folgenden Anfragen wiederholt auftreten können, ermöglicht der Einsatz des Cachings eine Reduktion der Kosten, die durch das Herunterladen derselben Datenquellen aus dem Web entstehen. Für das Anfragen einer RDF- Datenquelle müssen keine expliziten Schemainformationen bekannt sein. Deshalb kann im Prinzip jede beliebige Datenquelle durch das Vorhandensein in der lokalen Datenmenge zu einem vollständigeren Ergebnis beitragen. In dieser Arbeit wird eine spezielle Cache-Architektur vorgeschlagen und evaluiert, die eine performante Anfragebearbeitung und eine möglichst vollständige Ergebnismenge gewährleistet.

Generating profiles of genes and drugs from literature; with an application to drug-target interaction prediction (Conrad Plake)

In my talk, I will give an overview on research activities in the area of text mining in our group. Our work is focused on 1) biomedical ontology generation, 2) entity identification in biomedical literature, and 3) their automated annotation with ontological concepts. In particular, I will present approaches to gene identification and gene profiling in the context of cancers. Ontologies have been recently applied to link distantly related genes, phenotypes, and diseases. In the second part of my talk, I will show how ontologies can help to predict drug-target interactions and thus support experimental drug discovery. I will introduce ontological profiles consisting of function, process, location, and disease terminology that co-occur with drugs and proteins in the literature. From the similarity of these ontological profiles, we can associate drugs with potential targets. We independently evaluated our method on over 5,150 drugs and 14,380 targets in the databases DrugBank and Matador, and achieved high sensitivity and specificity. We conclude that a high-throughput, co-occurrence based text-mining technique applied to PubMed enables reasonably accurate prediction of drug-target interactions.

Pufferungsverfahren in Webbasierten Informationssystemen (Jan Engelsberg)

Webbasierte Informationssysteme bieten ihren Benutzern immer umfangreichere Möglichkeiten Daten anzufragen. Damit einher gehen zum Teil stark variierende Antwortmengen und deren Benutzer spezifische Aufbereitung. Herkömmliche Schlüssel/Wert basierte Cachekonzepte sind für derartige Systeme nicht mehr bzw. nur noch bedingt geeignet. Abhilfe schaffen semantische Caches, Prototypen Caches und als Cache genutzte lokale Datenbanken. Bei großen Datenmengen müssen aber auch bei ihnen Einschränkungen der Datenmenge vorgenommen werden. In dieser Arbeit wird ein zweistufiges Cachekonzept vorgestellt, das die vorzuhaltende Datenmenge reduziert. Durch eine Analyse des zugrunde liegenden Datenmodells werden diejenigen Daten identifiziert, die zur Beantwortung der Erstanfragen der Benutzer benötigt werden. Nach der Beantwortung einer Erstanfrage werden die Ergebnisdaten in einen Benutzer spezifischen Zwischenspeicher abgelegt und durch den Cache zur vollen Antwortmenge erweitert.

Analysis of T-cell processes using network reconstruction methods (Stefan Kröger)

In my talk I will give an introduction into my work on network reconstruction methods to elucidate T-cell processes during immune system responds. Dysfunction, hypo-function and hyper-function of the immune system lead to diseases like Rheumatoid arthritis and others, so called auto immune diseases. Understanding and controlling the mechanisms of the immune system enable medical efforts for different fields like disease prevention, drug treatment and organ transplantation. The goal of my work will be the application of such computational methods, to identify unknown transcription factor activities, that occur during T-cell activation or T-cell differentiation, which are essential parts of the cell-mediated immune responds. The increasing amount of public available micro-array data and specific knowledge from databases, literature and experts will be used to apply network reconstruction methods, like NCA and MNI. The resulting regulatory models will help to investigate regulatory function of unknown transcription factor activities.

Modellierung und Evaluierung einer Datenbankumgebung  zur online Sequenzierung von Polypeptiden (Emre Kutbay)

Die De-Novo Sequenzierung von Proteinen ist ein Verfahren zur Bestimmung der Aminosäuresequenz eines Proteins, wenn keine Vorkenntnisse hinsichtlich der Proteinsequenz vorliegen. Dabei kommt ein Massenspektrometer zum Einsatz der ein Protein in mehreren Stufen in Fragmente zerlegt und ihre Massen ermittelt. Der De-Novo-Algorithmus erfordert, dass diese Fragmentmassen auf mögliche Aminosäurekombinationen abgebildet werden. In diesem Szenario ergeben sich zwei Herausforderungen. Einerseits ermittelt ein Massenspektrometer aufgrund seiner Messungenauigkeit keine konkreten Massen sondern Massenintervalle. Andererseits muss die Abbildung gemessener Masseintervalle auf Aminosäurekombinationen, aufgrund des Aufbaus einer massenspektrometrischen Messung, möglichst schnell erfolgen. Es  wird der Aufbau und die Evaluierung einer Datenbankumgebung vorgestellt in dem verschiedene Ansätze gezeigt werden um diese Abbildung mit Hilfe von Lookup-Tabellen zu bewerkstelligen. Insbesondere die Häufigkeitsverteilung der Massen von Aminosäurekombinationen ermöglichen Strategien, mit deren Hilfe sich Anfragen an Lookup-Tabellen vermeiden lassen.

Prefix Tree Indexing for Similarity Search and Similarity Joins on Genomic Data (Astrid Rheinländer)

Similarity search and similarity join on strings are important operations for the comparison of biological sequences. Especially DNA sequencing produces large collections of erreneous strings which need to be searched, compared, and merged. In my talk, I will present PETER, a prefix tree based indexing algorithm supporting approximate search and approximate joins. PETER supports Hamming and edit distance as similarity measure and it combines an efficient implementation of compressed prefix trees with advanced pre-filtering techniques that exclude many candidate strings early. PETER was evaluated on several collections of long EST strings containing up to 5,000,000 entries. I compared its performance to Unix command line tools and user-defined functions inside a relational database. The experiments revealed that the achieved speed-ups are dramatic, especially for DNA with its small alphabet.

Weiterentwicklung des Algorithmus zur Auswahl kompatibler Komponenten in DESWAP (Mathias Peters)

Das Problem der Auswahl kompatibler Komponenten ist in der Entwicklung weit verbreitet und nicht trivial zu lösen. Die Web-Applikation DESWAP bietet hierfür einen Algorithmus auf der Basis von Technologien des Semantic Web. Ziel der Arbeit “Weiterentwicklung des Algorithmus zur Auswahl kompatibler Komponenten in DESWAP” ist die formale Beschreibung von DESWAPs Auswahlproblem als Constraint Satisfaction Problem. Dieses Ziel wird erreicht, indem die Eigenschaften von in DESWAP verwalteter Software sowie die Nutzeranforderungen an diese auf eine Menge von Variablen, Domänen und Constraints abgebildet werden. Das so formulierte CSP wird anschließend mithilfe eines Problem-Solvers gelöst und bezüglich der Laufzeiteigenschaften mit einem prozeduralen Algorithmus verglichen. Es zeigt sich, dass die Lösung als CSP bei kleinen Domänen und einfachen Anwendungsfällen schneller ist, bei Anwendungsfällen mit vielen potenziell möglichen Software-Kombinationen jedoch deutlich mehr Zeit zur Lösungsbestimmung benötigt. Zur Optimierung des deklarativen, CSP-basierten Algorithmus liefert der Autor mögliche Ansätze wie die Anpassung des verwendeten Problem-Solvers oder die Umsetzung von Verfahren zur Lösungssynthese.

Analyse von Genexpressionsdaten für die Erforschung von Arzneistoffen (Johannes Kozakiewicz)

Aufgabe: Klassifikation, Präprozessierung und Analyse von Genexpressionsdaten aus öffentlichen Repositorien sowie Entwurf eines Metaanalyse-Verfahrens für die vergleichende Genexpressionsanalyse. Thema dieser Arbeit ist die Erschließung, Aufbereitung und Analyse von Microarray-Experimentdatensätze aus öffentlichen Datenquellen. Dazu wurde ein Verfahren entwickelt, mit dessen Hilfe Microarray-Datensätze aus öffentlichen Repositorien klassifiziert und normalisiert werden können, mit dem Ziel sie untereinander vergleichbar zu machen. Als Datenrepositorien wurden Gene Expression Omnibus, ArrayExpress, Diabetes Genome Anatomy Project und Connectivity Map ausgewählt. Alle notwendigen und verfügbaren Metainformationen zu zuvor ausgewählten Experimenten vorselektierter Microarray-Chipsätze wurden für diesen Zweck in eine Projektdatenbank importiert und anschließend nach den 11 Indikationsgebieten Alzheimer, Parkinson, Chronischer Schmerz, Asthma, COPD, Entzündungen, Arteriosklerose, Kardiovaskuläre Erkrankungen, Diabetes Mellitus Typ II, Hyperlipidämie, Onkologie sowie in Gewebe und / oder Zelllinien klassifiziert. Die klassifizierten Metainformationen von insgesamt 3475 Primär-Experimenten wurden verwendet, um Datensätze, die mindestens einem Indikationsgebiet zugeordnet werden konnten, auszuwählen, aufzubereiten und in eine Projektdatenbank zu importieren. Die Aufbereitung der Datensätze beinhaltete den Export der Rohdatensätze aus den vorgestellten Repositorien, die Normalisierung der Daten mittels der bereits implementierten Normalisierungsalgorithmen MAS 5.0 und RSN sowie die Identifikation differentiell exprimierter Gene mittels eines gemäßigten T-Tests. Die mittels dieses Aufbereitungsverfahrens identifizierten differentiell exprimiereten Gene wurden anschließend in mehreren vergleichenden Metaanalysen, hinsichtlich ihrer Konfidenz für ein Indikationsgebiet relevant zu sein, bewertet.

HepatoBase – knowledgebase for evidence based network reconstruction/modeling for human hepatocytes – Chances and Challenges (Michael Weidlich)

Network reconstruction if done systematically is a time-consuming and often tedious labor for curators. And though the review of literature (i.e. in search of evidence for certain network components) might be too complex to be fully automated, there are various starting-points to ease curational efforts. To address these points I will shortly introduce our data model (infrastructure) able of capturing different levels of detail in metabolic networks, focusing on evidence and assertion management being the major difference to other pathway knowledge bases like i.e. Reactome. In the second part I will discuss current challenges in network reconstruction and where I expect that text mining, data integration and (social) network analysis might help to simplify/speed up curation or even provide new insights about metabolic relationships.

Cache Conscious Data Layouting for In-Memory Databases (Holger Pirk)

Many applications with manually implemented data management exhibit a data storage pattern in which semantically related data items are stored closer in memory than unrelated data items. The strong sematic relationship between these data items commonly induces contemporary accesses to them. This is called the principle of data locality and has been recognized by hardware vendors. It is commonly exploited to improve the performance of hardware. General Purpose Database Management Systems (DBMSs), whose main goal is to simplify optimal data storage and processing, generally fall short of this claim because the usage pattern of the stored data cannot be anticipated when designing the system. The current interest in column oriented databases indicates that one strategy does not fit all applications. A DBMS that automatically adapts it’s storage strategy to the workload of the database promises a significant performance increase by maximizing the benefit of hardware optimizations that are based on the principle of data locality. This thesis gives an overview of optimizations that are based on the principle of data locality and the effect they have on the data access performance of applications. Based on the findings, a model is introduced that allows an estimation of the costs of data accesses based on the arrangement of the data in the main memory. This model is evaluated through a series of experiments and incorporated into an automatic layouting component for a DBMS. This layouting component allows the calculation of an analytically optimal storage layout. The performance benefits brought by this componentt are evaluated in an application benchmark.

Identifikation und Extraktion von Musikveranstaltungen aus dem Web (Hung Le)

Dieser Arbeit ist die Fortführung der Studienarbeit zum gleichen Thema. Ziel dieser Arbeit ist es zu zeigen, dass es möglich ist, Veranstaltungsseiten aus dem Web zu identifizieren und die dazugehörigen Veranstaltungsinformationen zu extrahieren. Veranstaltungen liegen meist als Datensätze auf Webseiten von Veranstalter und Künstler zur Verfügung. Um diese Datensätze zu identifizieren, wurde eine Methode namens Mining Data Records angewandt.  Diese Methode versucht ähnliche Strukturen auf den Webseiten zu finden und sie in Datensätze zu fassen. Aus diesen Datensätzen müssen anschließend veranstaltungsspezifische Daten extrahiert werden. Mithilfe von regulären Ausdrücken können Daten wie Datum, Zeit, Preise oder Genre einfach herausgefiltert werden. Dagegen wurden Techniken aus dem Bereich des maschinellen Lernens eingesetzt werden, um Künstlername zu erkennen.

Zugriffsrichtlinen und Authentifizierung für Linked-Data-Systeme (Hannes Mühleisen)

Zusammenfassung: Eine große Menge von Daten wird bereits nach den Prinzipien des Semantic Web als Linked Data dargestellt und zum Austausch angeboten. Ein wichtiger Bereich ist jedoch bisher ausgenommen: Nutzer haben Probleme damit, persönliche Informationen unbeschränkt zugänglich zu machen, da keine Zugriffskontrolle vorgesehen ist. Diese Arbeit stellt einen Ansatz vor, der es möglich macht, sensible Daten innerhalb des Semantic Web nur bestimmten Nutzern zugänglich zu machen.

Finding Gene Ontology Terms in Biomedical Articles (Nikolay Damyanli)

In this thesis several methods for improving the search of GO-terms in biomedical articles were investigated. While using the data corpus from the BioCreAtIvE I Task 2 contest, a sentence-sliding-window approach using bags of words with gene ontology terms as tokens was implemented and then evaluated by the results of the BioCreAtIvE contestants. For finding text passages with GO-term evidence GO-bags-of-words (GO-BoWs) for every GO-term were built, while using external information such as Gene Ontology and abstracts of relevant articles. The words in the GO-BoWs were then weighted by the TFIDF-measure. The text articles were then scanned with a sentence-sliding-window (SSW) approach and every window got a relevance score for every GO-term calculated with the help of its GO-BoW. The highest scored windows were then marked as results and evaluated by comparison to the evaluated BioCreAtIvE data.

Entwicklung eines Workload-Compressing-Index-Wizards für relationale Datenbanken (Benjamin Daeumlich)

In einem modernen Datenbankmanagementsystem werden verschiedene Methoden zur Leistungssteigerung verwendet, sodass die Kosten für die Ausführung von Anfragen gesenkt werden. Eine Möglichkeit der Leistungssteigerung bietet die Benutzung von Indizes. Da dem Prozess der Indexauswahl unter Umständen eine sehr große Menge von Anfragen zugrunde liegt, kann es von Vorteil sein, diese Menge vorher zu komprimieren. Dazu werden ähnliche Anfragen (bzgl. der Nützlichkeit eines Indexes) in Gruppen eingeteilt, wobei jeweils eine Anfrage diese Gruppe repräsentiert. In dieser Diplomarbeit wird ein Index-Wizard für relationale Datenbanken entwickelt, welcher SQLIndexWizard genannt wird. Bevor die Indexauswahl stattfindet, wird die zugrunde liegende Menge von Anfragen bezüglich der Nützlichkeit von Indizes komprimiert (Workload-Compression). Der SQLIndexWizard gibt letztendlich eine Empfehlung ab, welche Indizes erstellt bzw. gelöscht werden müssen, um die Leistung bezüglich der gegebenen Anfragen möglichst optimal zu steigern, ohne eine vorgegebene Speicherplatzbeschränkung zu überschreiten. Als Beispielsystem wird in der Arbeit das Datenbankmanagementsystem DB2 von IBM verwendet. Der SQLIndexWizard basiert auf einem System, welches für das LDAP-DBMS der Firma Siemens (DirX-System) entwickelt wurde. Dieses System (DirXWiz) führt ebenfalls eine Indexauswahl mit vorangegangener Workload-Compression durch. Eine besondere Herausforderung dieser Arbeit ist demnach die Übertragung der Methoden und Konzepte von der LDAP-Anfragesprache auf eine relationale Anfragesprache, wobei in dieser Arbeit die Sprache SQL verwendet wird.

Identifikation von Adressangaben in Texten - ohne Verwendung von Wörterbüchern (Nora Popp)

In der Diplomarbeit wurde untersucht, ob Adressangaben in Texten maschinell ohne die Unterstützung von Wörterbüchern identifiziert werden können. Diese Aufgabe ist in das Problemfeld der Named Entity Recognition einzuordnen, lässt sich jedoch nicht direkt mit der Suche nach Entitäten der klassischen Kategorie Location (Ortsangaben) vergleichen. Adressangaben sind oft komplexer als einfache Ortsangaben. Für die Diplomarbeit wurde ein Korpus mit Adressmarkierungen versehen. Anschließend wurde es auf semantische und syntaktischen Muster und Regelmäßigkeiten hin untersucht, durch die sich Adressangaben von anderen Entitäten unterscheiden ließen. Im Vortrag wird erläutert, wie anhand der gewonnenen Informationen, Features für die Token des Korpus erstellt wurden, anhand derer sie durch eine SVM als Adresstoken (Teil einer Adresse) oder Nicht-Adresstoken klassifiziert werden sollten. Die erzielten Ergebnisse werden präsentiert und diskutiert.

Zuverlässigkeit vs. Energieverbrauch für Geografisches Routing in drahtlosen Sensornetzwerken (Christian Czekay)

Wireless Sensor Networks are ever increasing in size due to falling hardware costs. The efficiency of the routing protocol therefore becomes more and more important. This has made Geographic Routing a popular choice as a routing protocol in recent years. Unfortunately Geographic Routing is unreliable because it cannot guarantee that a packet will be delivered, if a connection exists between the source and the destination. In my diploma thesis, I analyze how Geographic Routing can be made more reliable by augmenting it with Face Routing, how the network lifetime can be increased by letting nodes sleep periodically and how these two extensions interact.

Drahtlos in den Wolken - Sensor Network Simulation mit Hilfe von Cloud-Computing-Architekturen (Erik Dießler)

Die Studienarbeit beschäftigt sich mit den Möglichkeiten, die eine Cloud-Architektur für das verteilte Simulieren von drahtlosen Sensornetzwerken bieten kann. Am Beispiel von JiST/SWANs und den Amazon Web Services wurden ein Ansatz und ein Prototyp entwickelt. Der Ansatz sieht vor, jede Simulation komplett auf einer Maschine zu berechnen, dabei aber theoretisch beliebig viele EC2-Instanzen zu nutzen und somit beliebig viele Simulationen parallel ausführen zu können. Mit Hilfe des Prototypen wurden Messungen durchgeführt, die Auskunft über die Eignung des entwickelten Ansatzes geben sollen. Es sollen weiterhin Aussagen darüber getroffen werden, ob und inwieweit die Amazon Web Services zur Lösung eines derartigen Problems geeignet sind. Im Rahmen des Vortrages werden der Ansatz und die Ergebnisse vorgestellt.