Forschungsseminar WBI
Arbeitsgruppe Wissensmanagement in der Bioinformatik
Neue Entwicklungen im Datenbankbereich und in der Bioinformatik
- wann? Dienstag, 13 Uhr c.t.
- wo? RUD 25, Humboldt-Kabinett
Dieses Seminar wird von den Mitgliedern der Arbeitsgruppe als Forum der Diskussion und des Austauschs genutzt. Studierende und Gäste sind herzlich eingeladen.
Folgende Vorträge sind bisher vorgesehen:
Zusammenfassungen
Introduction to integrative -omics (Liam Childs)
Biological processes are highly dynamic and heterogenous systems. Current technologies are able to analyse them on several different levels, including the genome, transciptome, proteome and metabolome (to name a few), each of which require very different technologies and expertise to produce and analyse. Due to this, most biological analyses focus on a single -omics approach to understand the problem at hand, potentially ignoring key aspects that can only be analysed using other -omics approaches. However, as technologies improve and ever more user-friendly tools for -omics analysis are produced, opportunities are arising to integrate heterogenous -omics analyses leading to a more complete picture of the biological systems they are designed to investigate.
Cuneiform - A Functional, Aspect-oriented Workflow Language (Jörgen Brandt)
The scientific community employs a variety of scientific workflow systems to perform computational tasks that are often data-driven, explorative, and greatly profit from parallelization. In this setting, the workflow system plays the role of an orchestration platform that organizes chains of loosely coupled software tools and libraries. Each workflow system comes with its own specification language, that can take the form of graphical or textual languages as well as web-driven APIs. Cuneiform is a textual workflow language that is designed with the main goals of clear notation, focus on the workflow execution model, and abstractness. To this end, Cuneiform leverages the well-established concepts of Functional Programming and Aspect Orientation and, in spite of its domain-specific focus, is Turing-complete. We present the basic Cuneiform language concepts and demonstrate its usefulness by the example of a use case from Next-Generation Sequencing (NGS). The example showcases the effect of data-, pipeline- and task-parallelism and Cuneiform's support for various scripting languages. Eventually, implications of the provided control structures, recursion, and higher-order functions for (i) the requirements regarding the execution engine and (ii) Cuniform's expressiveness are given.
Waste Not, Want Not - Efficient Co-Processing of Relational Data (Holger Pirk)
The variety of memory devices in modern computer systems holds opportunities as well as challenges for data management systems. In particular, the exploitation of Graphics Processing Units (GPUs) and their fast memory has been studied quite intensively. However, current approaches treat GPUs as systems in their own right and fail to provide a generic strategy for efficient CPU/GPU cooperation. We propose such a strategy for relational query processing: calculating an approximate result based on lossily compressed, GPU-resident data and refining the result using residuals, i.e., the lost data, on the CPU. To assess the potential of the approach, we developed a prototypical implementation for spatial range selections. We found multiple orders of magnitude performance improvement over a CPU-only implementation even if the data size exceeds the available GPU memory. Encouraged by these results, we developed the required algorithms and techniques to implemented the strategy in an existing in-memory DBMS and found up to 7 times performance improvement for selected TPC-H queries.
Supporting Agile Workflow Management with Case-Based Reasoning (Ralph Bergmann)
Today, workflows are an established means for modeling business processes and to automatically control their execution. Recently, workflows are more widely used for many additional purposes. Workflows are used as executable descriptions of automatable scientific processes (scientific workflows), to represent project plans, or to describe information gathering strategies. Such new applications of workflows typically deal with a number of new difficulties, particularly due to an increasing number of potentially relevant workflows, an increasing complexity of the individual workflows, and an increased demand for more flexibility (agile workflows). To deal with those new challenges in workflow management, reasoning methods for semantically enriched workflow representations have a high potential to support workflow modeling, composition, adaptation, analysis, and optimization. In this talk I will present several innovative workflow applications from recent projects and I will describe how process-oriented case-based reasoning can support workflow management. In particular, a new framework for similarity-based retrieval and clustering of semantic workflows will be described.
Identifikation von Erdbebenmeldungen über Focused Crawling und Textsegmentierung (Mario Lehmann)
Die automatisierte Analyse von Webtexten gewinnt in vielen Bereichen zunehmend an Bedeutung. Ein wichtiges Anwendungsfeld ist der Bereich der Katastrophenbekämpfung und -prävention, in welchem IE-Verfahren verstärkt eingesetzt werden könnten, um die helfenden Stellen zeitnah mit relevanten Informationen zu versorgen. In der vorliegenden Arbeit wird untersucht, wie effizient erdbebenrelevante Texte bzw. Textsegmente aus dem Web extrahiert und raumzeitlich verortet werden können. Der Ausgangspunkt ist der Webcrawler Apache Nutch, welcher um die Fähigkeit der Fokussierung erweitert wurde. Wichtiger Bestandteil der Fokussierung ist das Scoring-Verfahren, mit dessen Hilfe die Relevanz eines ausgehenden Links anhand spezifischer Merkmale bewertet wird. Ein weiterer Bestandteil ist die Klassifikation eines eingehenden Webdokuments, welche über drei Klassifikatoren realisiert wird. Das erste Klassifikationsmodell ist TF-IDF-basiert. Es bildet die Grundlage für das Segmentermodell, welches die thematische Relevanz auftretender N-Gramme innerhalb eines Textes einschätzen soll. Das Modell wird auf Grundlage eines Trainingscrawls angelernt. Anschließend wird es für den Vektorisierungsschritt des zweiten Klassifikators verwendet. Der dritte Klassifikator ist ein Ensemble-Modell, welches die Klassenkonfidenzen der beiden anderen Klassifikatoren als Eingangsdaten nutzt. Alle Klassifikatoren sind Support-Vektor-Maschinen, die auf einem Goldstandard trainiert werden. Im zweiten Teil der Arbeit wird das Segmentermodell verwendet, um innerhalb eines positiven Textes die relevanten Textstellen zu detektieren. Für die raumzeitliche Verortung einer Textstelle werden raumzeitliche Attribute verwendet, die mit Hilfe eines GeoNames-DB-basierten Geotaggers und dem Werkzeug HeidelTime aus einem Text extrahiert werden. Die Ereignissegmentierung erfolgt über ein mehrstufiges Analyseverfahren auf Satzebene. Bei der Evaluation zeigt sich u.a., dass das verwendete Scoring-Verfahren die harvest rate (HR) eines Crawls um bis zu 48.22% (HR = 0.2673) signifikant steigern kann. Als besonders geeignet erweisen sich als Linkmerkmale der Text eines Outlinks (Anchortext), der Textabstand eines Links zum Wort „earthquake“ sowie der Domainname der URL. Bei der Dokumentklassifikation zeigt sich, dass sich die Leistung eines bestehenden Klassifikators mit Hilfe des Focused Crawling verbessern lässt. Besonders gut schneidet das Ensemble-Modell ab. Bei mehrmals durchgeführten Kreuzvalidierungen auf dem Goldstandard erreicht dieses einen mittleren F-Score von 84.96% (P = 91.04%, R = 82.00%). Im Vergleich dazu scheidet das TF-IDF-basierte Modell mit einem F-Score von 80.94% (P = 98.39%, R = 71.23%) signifikant schlechter ab. Auf den real gecrawlten Texten ist die Klassifikationsleistung des Ensemble-Modells ebenfalls besser. Auf einer zufällig gezogenen Menge von 100 positiv klassifizierten Dokumenten, dem Evaluationskorpus der Ereignissegmentierung, erreicht das Ensemble-Modell eine Precision von 95%. Zusätzlich dazu verbessert das Modell signifikant die harvest rate (im Vergleich zum Basismodell um 37.12%). Bei der Ereignissegmentierung können 50.94% aller Sätze des Evaluationskorpus mit einer zulässigen Toleranz von 1000 km und 20 Tagen korrekt annotiert werden. Räumlich werden 73.95% aller Sätze korrekt annotiert, zeitlich 62.21% und thematisch 81.19%. Die Irrtumswahrscheinlichkeit Pk beträgt 34.52%. Zusammenfassend lassen sich mit Hilfe des umgesetzten fokussierten Webcrawlers effizient große domänenspezifische Textkorpora generieren. Sowohl das Scoring-Verfahren als auch die Verbesserung der Dokumentklassifikation führt zu einer Steigerung der harvest rate. Die Ereignissegmentierung auf Basis der raumzeitlichen Attribute und dem Segmentermodell hat im Wesentlichen funktioniert. Dennoch ist das verwendete Verfahren in vielerlei Hinsicht noch ausbaufähig z.B. bezüglich der Detektion von räumlich oder zeitlich undefinierten Textbereichen.
High-Performance In-memory Genome Project: A Platform for Integrated Genome Data Analysis (Matthieu Schapranow)
Next-Generation Sequencing (NGS) technologies have reduced costs and time for whole genome sequencing within the last decade. However, interpretation and analysis of generated genome data is still a time- and resource-intensive task that may take weeks. The In-Memory Database (IMDB) technology has demonstrated major improvements in analyzing big enterprise data. We present our findings of applying IMDB technology to enable real-time analysis of NGS genome data in course of our High-performance In-memory Genome (HIG) research project. Based on the feedback of researchers and clinicians, we designed a completely new IT architecture based on IMDB technology that enables processing and real-time analysis of genome data in a single system. The HIG system is optimized to run on commodity hardware instead of highly specialized hardware. Thus, it is a) more cost-efficient and b) can make use of existing hardware infrastructures. Our findings show that IMDB technology provides an integration platform for genome data processing and its analysis while significantly reducing time and costs to obtain relevant results, e.g. in the course of personalized medicine. We share insights about selected IMDB extensions for genome data processing, such as scheduling, worker or updater framework. Furthermore, we outline details about selected IMDB technology building blocks, such as data partitioning, multi-core parallelization, and lightweight data compression. Our obtained benchmark results prove that the HIG system improves overall pipeline execution time by at least 25 percent on a single computing node and up to 89 percent involving 25 computing nodes. The performance boost is achieved by substituting file-based operations in genome data processing pipelines, such as sorting, merging, and indexing, by native in-memory database operations. Our future work will investigate the performance impact of optimized alignment and variant calling algorithms directly incorporating the IMDB technology. We expect them to eliminate media breaks due to improved data proximity.
Evolution of Ontology-Based Mappings in the Life Sciences (Anika Groß)
In the life sciences, there is an increasing number of heterogeneous data sources that need to be integrated and combined in comprehensive analysis tasks. Often ontologies and other structured vocabularies are used to provide a formal representation of knowledge and to facilitate data exchange between different applications. Ontologies are used in different domains like molecular biology or chemistry. One of their most important applications is the annotation of real-world objects like genes or publications. Since different ontologies can contain overlapping knowledge it is necessary to determine mappings between them (ontology mappings). A manual mapping creation can be very time-consuming or even infeasible such that (semi-) automatic ontology matching methods are typically applied. Ontologies are not static but underlie continuous modifications due to new research insights and changing user requirements. The evolution of ontologies can have impact on dependent data like annotation or ontology mappings. This thesis presents novel methods and algorithms to deal with the evolution of ontology-based mappings. Thereby the generic infrastructure GOMMA is used and extended to manage and analyze the evolution of ontologies and mappings. First, a comparative evolution analysis for ontologies and mappings from three life science domains shows heavy changes in ontologies and mappings as well as an impact of ontology changes on the mappings. Hence, existing ontology mappings can become invalid and need to be migrated to current ontology versions. Thereby an expensive redetermination of the mappings should be avoided. This thesis introduces two generic algorithms to (semi-) automatically adapt ontology mappings: (1) a composition-based adaptation relies on the principle of mapping composition, and (2) a diff-based adaptation algorithm allows for individually handling change operations to update mappings. Both approaches reuse unaffected mapping parts, and adapt only affected parts of the mappings. An evaluation for very large biomedical ontologies and mappings shows that both approaches produce ontology mappings of high quality. Similarly, ontology changes may also affect ontology-based annotation mappings. The thesis introduces a generic evaluation approach to assess the quality of annotation mappings based on their evolution. Different quality measures allow for the identification of reliable annotations, e.g., based on their stability or provenance information. A comprehensive analysis of large annotation data sources shows numerous instabilities, e.g., due to the temporary absence of annotations. Such modifications may influence results of dependent applications such as functional enrichment analyses that describe experimental data in terms of ontological groupings. The question arises to what degree ontology and annotation changes may affect such analyses. Based on different stability measures the evaluation assesses change intensities of application results and gives insights whether users need to expect significant changes of their analysis results. Moreover, GOMMA is extended by large-scale ontology matching techniques. Such techniques are useful, a.o., to match new concepts during ontology mapping adaptation. Many existing match systems do not scale for aligning very large ontologies, e.g., from the life science domain. One efficient composition-based approach indirectly computes ontology mappings by reusing and combining existing mappings to intermediate ontologies. Intermediate ontologies can contain useful background knowledge such that the mapping quality can be improved compared to a direct match approach. Moreover, the thesis introduces general strategies for matching ontologies in parallel using several computing nodes. A size-based partitioning of the input ontologies enables good load balancing and scalability since smaller match tasks can be processed in parallel. The evaluation of the Ontology Alignment Evaluation Initiative (OAEI) compares GOMMA and other systems in terms of matching ontologies from different domains. Using the parallel and composition-based matching, GOMMA can achieve very good results w.r.t. efficiency and effectiveness, especially for ontologies from the life science domain.
Syntaktische Identifizierung von Lobbyeinflüssen auf die EU-Datenschutz-Grundverordnung (Frank Bicking)
Auf der Ebene der Europäischen Union entsteht derzeit eine neue Datenschutz-Grundverordnung. Von 2009 bis 2011 folgten dem Aufruf der EU-Kommission zur Stellungnahme über 500 Einsendungen von Stakeholdern. Motiviert durch zahlreiche Änderungen am Gesetzestext durch EU-Parlamentarier, die sich wortgetreu auf Lobbypapiere zurückführen ließen, richtete sich der Fokus dieser Studienarbeit auf die ursprünglichen Konsultationstexte. Um deren Einfluss zu bestimmen, wurden die Dokumente in einem auf Apache Lucene basierenden invertierten Index zur Volltextsuche erfasst und anhand von N-Grammen mit dem Kommissionsentwurf verglichen. Auf Basis von TF-IDF wurden Fundstellen bewertet und ein Ähnlichkeitsmaß definiert, um ein Relevanzranking der Dokumente zu ermitteln und diese mit UPGMA in ein Clustering einzuordnen. In einer graphischen Benutzeroberfläche wurden Texte gegenübergestellt, Fundstellen hervorgehoben und nachverfolgbar gemacht.
Vergleich von Open-Source und kommerziellen Programmen zur Durchführung eines ETL-Prozesses (Sascha Qualitz)
Daten sind in Firmen das höchste Gut. Diese zumeist heterogenen Informationen konsistent zusammenzuführen stellt eine wichtige und häufig kostenintensive Aufgabe dar. Für solche ETL-Projekte existieren aber auch Open-Source-Produkte, welche im Allgemeinen kostenfrei erhältlich sind und viele Funktionen für die Durchführung solcher Projekte besitzen. In diesem Vortrag wird die zu diesem Thema erstellte Diplomarbeit, in der drei Programme exemplarisch untersucht und verglichen wurden, beschrieben. Hierbei wird erläutert, welche Programme betrachtet, sowie welche Kriterien und Techniken für die Untersuchung verwendet wurden.
Extracting and Aggregating Temporal Events from Text (Lars Döhling)
Finding reliable information about a given event from large and dynamic text collections is a topic of great interest. For instance, rescue teams and insurances are interested in concise facts about damages after disasters, which can be found in numerous blogs, newspaper articles, social networks etc. However, finding, extracting and condensing specific facts is a highly complex undertaking: It requires identifying appropriate textual sources, recognizing relevant facts within the sources, and aggregating extracted facts into a condensed answer despite inconsistencies, uncertainty and changes over time. In this talk, we present a three-step framework providing techniques and solutions for each of these problems. We tested the feasibility of extracting time-associated event facts using our framework in a comprehensive case study: Gathering data on particular earthquakes from web data sources. Our results show that it is, under certain circumstances, possible to automatically obtain reliable and timely data on natural disasters from the web.
Kontakt: Astrid Rheinländer; rheinlae(at)informatik.hu-berlin.de