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

Neue Entwicklungen im Datenbankbereich und in der Bioinformatik

• wann? Donnerstag, 15-17 c.t.
• wo? RUD 25, 3.101

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

Provenance Information in the Web of Data (Olaf Hartig)

The openness of the Web and the ease to combine linked data from different sources creates new challenges. Systems that consume linked data must evaluate quality and trustworthiness of the data. A common approach for data quality assessment is the analysis of provenance information. For this reason, we discuss provenance of data on the Web and propose a suitable provenance model. While traditional provenance research usually addresses the creation of data, our provenance model also represents data access, a dimension of provenance that is particularly relevant in the context of Web data. Based on our model we identify options to obtain provenance information and we raise open questions concerning the publication of provenance-related metadata for linked data on the Web.

Identifizieren und Extrahieren von Musikveranstaltungen aus dem Web (Hung Le)

Web Wrapper sind spezialisierte Programme, die automatisch Daten von Webseiten extrahieren. In diesem Vortrag werden die Möglichkeiten zur Erstellung von Web Wrapper präsentiert, um Musikveranstaltungsinformationen aus den Webseiten zu extrahieren.

Integrating protein-protein interactions and text mining for protein function prediction (Samira Jaeger)

Functional annotation of proteins remains a challenging task. Currently the scientific literature serves as the main source for yet uncurated functional annotations, but curation work is slow and expensive. Automatic techniques that support this work are still lacking reliability. We developed a method to identify conserved protein interaction graphs and to predict missing protein functions from orthologs in these graphs. To enhance the precision of the results, we furthermore implemented a procedure that validates all predictions based on findings reported in the literature. Using this procedure, more than 80% of the GO annotations for proteins with highly conserved orthologs that are available in UniProtKb/Swiss-Prot could be verified automatically. For a subset of proteins we predicted new GO annotations that were not available in UniProtKb/Swiss-Prot. All predictions were correct according to the verifications from a trained curator. Our method of integrating CCSs and literature mining is thus a highly reliable approach to predict GO annotations for weakly characterized proteins with orthologs.

Extracting Relations from Biomedical Texts Using Syntactic Information (Peter Palaga)

Relationsextraktion ist ein Verfahren, mit dem Informationen gezielt aus Fließtext in einer strukturierten Form gewonnen werden. Eine heutzutage sehr häufig untersuchte Anwendung der Relationsexktraktion ist die Extraktion von Protein-Protein Interaktionen (PPI) aus biomedizinischen Texten. Wir haben mehrere automatische kernelbasierte Methoden für die Relationextraktion auf dem PPI-Extraktion Problem evaluiert. Einerseits haben wir Experimente mit in der Fachliteratur beschriebenen Kernelfunkionen durchgeführt und andererseits haben wir einige Kernels selbst entworfen. Wir haben Methoden und Metriken für die Evaluierung benutzt, die einen direkten Vergleich mit den PPI-Extraktionsmethoden erlauben, die "auf dem neusten Stand der Kunst" sind. Ein von uns entworfener Kernel hat höhere Genauigkeit und deutlich kürzere Laufzeiten gezeigt als die Kernels aus der Literatur gezeigt haben. Im Vergleich mit den modernsten Methoden hat jedoch unsere Methode schlechtere Ergebnisse erreicht.

Ermittlung und Berücksichtigung der Vertrauenswürdigkeit von gemeinschaftlich erzeugten Aussagen in Semantic Web Anwendungen (Heiko Müller)

In vielen Web-basierten Anwendungen werden Inhalte gemeinschaftlich durch die Nutzer der jeweiligen Anwendung erzeugt. In Semantic-Web-Anwendungen handelt  es sich bei diesen Inhalten hauptsächlich um Aussagen, welche in  maschinenverarbeitbarer Form beschrieben werden. Jedes Mitglied des Nutzerkreises ist in der Lage Aussagen zu erzeugen, wobei diese Aussagen unter Umständen auch fehlerhaft oder bewusst falsch sein können. Deshalb dürfen diese Aussagen nicht als Fakten wahrgenommen werden, sondern müssen als Behauptungen betrachtet werden. Die Vertrauenswürdigkeit dieser Behauptungen wird durch verschiedene Nutzer unterschiedlich eingeschätzt. Das Ziel der Diplomarbeit ist die Entwicklung und Implementierung eines Vertrauensmodells auf dessen Basis die Vertrauenswürdigkeit jeder einzelnen Aussage berechnet wird, die durch die Gemeinschaft erzeugt wurde.

Querying Trust in RDF Data with tSPARQL (Olaf Hartig)

Today a large amount of RDF data is published on the Web. However, the openness of the Web and the ease to combine RDF data from different sources creates new challenges. The Web of data is missing a uniform way to assess and to query the trustworthiness of information. In this paper we present tSPARQL, a trust-aware extension to SPARQL. Two additional keywords enable users to describe trust requirements and to query the trustworthiness of RDF data. Hence, tSPARQL allows adding trust to RDF-based applications in an easy manner. As the foundation we propose a trust model that associates RDF statements with trust values and we extend the SPARQL semantics to access these trust values in tSPARQL. Furthermore, we discuss opportunities to optimize the execution of tSPARQL queries.

Query Processing on Multi-Core Architectures (Frank Huber)

The upcoming generation of computer hardware poses several new challenges for database developers and engineers. This paper outlines our approach for query processing on multi-core CPU architectures. We present an abstract architecture view for multi-core CPUs, meta operators to control and to interact with the hardware, and a new query operator model that makes use of the meta operators to control the parallel execution of a query over different cores. We illustrate how each of these parts fits in our framework for query processing on multi-core architectures.

SOA-based Integration of Text Mining Services (Johannes Starlinger)

Text Mining has established itself as a valuable tool for knowledge extraction in many commercial and scientific areas. Accordingly, a large number of different methods have been developed focusing on a broad range of different tasks. We report on a novel system architecture that is fundamentally service-based, i.e., it models and implements text mining and knowledge extraction routines as independent, yet federated services. The system has several layers: (1) Base services perform various fundamental extraction tasks. They all implement a fixed interface but keep their particular algorithms and functionality. (2) A metaservice acting as a central access point to those base services, thus providing a homogeneous interface to different algorithms. (3) An aggregation service on top of the metaservice which implements functionality to graphically show, compare, and aggregate the results of different base services. Each layer is accessible as a Web Service and thus ready to be integrated in applications that are higher up in the value chain, such as authoring tools or systems for the automatic construction of knowledge bases. We developed our system with a focus on the mining of Life Science text collections. It is available from http://www.bc-viscon.net.

Processing Multiple Aggregation Queries in Dynamic Wireless Sensor Networks (Björn Schümann)

Wireless Sensor Netzwerke bestehen aus einer großen Anzahl kleiner unabhängiger Sensor-Knoten. Man kann ein solches Netzwerke als eine große verteilte Datenbank betrachten in der jeder Knoten einen Teil der Daten liefert. In meiner Diplomarbeit habe ich nun untersucht, wie mehrere parallele Aggregationsanfrage an ein solches Netzwerk auch unter dynamischen Funkbedingungen möglichst effizient beantwortet werden können. Das Ergebnis kombiniert bekannte Methoden der MQO für Aggregations-Anfragen auf Sensornetzen mit robusten dynamischen Routing-Protokollen.

Some things about disease genes (Samira Jaeger)

In meinem Vortrag möchte ich über Fortschritte und den aktuellen Stand meiner Dissertation sprechen. In erster Linie wird es dabei um Krankheitsgene und deren Eigenschaften, Methoden zur Priorisierung und Vorhersage von Krankheitsgenen und daraus resultierende Fragestellungen gehen.

Optimization of Regular Path Queries on Large Graphs (Andre Koschmieder)

Eine zentrale Herausforderung bei der Arbeit mit Graphen ist die Beantwortung von Suchanfragen. In der Biologie werden Graphen mit vielen Millionen Knoten und Kanten verwendet, um Beziehungen zwischen Genen oder Zusammenhänge biologischer Vorgänge darzustellen. Suchanfragen sind häufig komplexe Anfragen nach Pfaden, deren Knoten und Kanten bestimmten Kriterien genügen. Zur Formulierung solcher Anfragen können reguläre Ausdrücke verwendet werden. Im Rahmen meiner Diplomarbeit habe ich untersucht, wie sich reguläre Pfadanfragen an große Graphen effizient im Hauptspeicher beantworten lassen. Es wurde untersucht, wie die Bearbeitungsgeschwindigkeit mit der Größe der Graphen skaliert, sowie bis zu welcher Größe Graphen im Hauptspeicher gehandhabt werden können. Weiter wurde für Graphen mit einer Zipf-Verteilung der Kantenlabels, wie sie in der Biologie häufig vorkommt, eine Optimierung vorgestellt und deren Effektivität untersucht.

Transaktionssteuerung für das Java-basierte Hauptspeicher-DBMS JOPAQ (Leonid Snurnikov)

JOPAQ ist ein Java-basiertes hauptspeicherresidentes Datenbanksystem, das von Sebastian Bacher entwickelt wurde. Durch die starke Anpassung an Java, die Beseitigung von Indirektionen beim Datenzugriff sowie das permanente Vorhalten aller Daten im Hauptspeicher verspricht es ein besonders hohes Leistungsvermögen. In der vorliegenden Diplomarbeit wird JOPAQ um die Funktionalität einer Transaktionssteuerung erweitert, sodass mehrere Transaktionen gleichzeitig ausgefürt werden können. Dazu wird ein entsprechendes Transaktionsprotokoll und eine Architektur der Transaktionssteuerung vorgestellt, die auf die besonderen Leistungsbedürfnisse einer hauptspeicherresidenten Datenbank eingeht. Leistungstests, die unter anderem den Vergleich mit einer seriellen Ausführung von Transaktionen einschließen, konnten verbesserte Antwortzeiten und einen höheren Transaktionsdurchsatz nachweisen.

Methode zur Assoziation von Termen der Gene Ontology und MeSH auf Basis der verknüpften Life Science-Datenquellen Entrez Gene, PubMed und OMIM (Andrej Masula)

Die große Menge an Daten verfügbar in Life Science-Datenquellen birgt enormes Potential zur Entdeckung neuer Zusammenhänge, die erst durch Auswertung von Ketten von Verknüpfungen möglich ist. Dies ist längst Gegenstand wissenschaftlicher Forschungen. Die einzelnen Datensätze bzw. die sie repräsentierenden Entitäten sind jedoch zusätzlich durch deskripitive Annotationen angereichert. Diese Beschreibungen enthalten wertvolle Informationen, deren Auswertung das Verständnis um die Entitäten erhöhen. Textuelle Beschreibungen liefern komplexe Erläuterungen, die jedoch am besten durch den Menschen interpretierbar sind. Die Entwicklung von Ontologien als deskriptive Modelle   bestimmter Fachdomänen ermöglichen es, ein gesteuertes und verlässliches Vokabular und Regeln zur Bildung von Aussagen über dem Vokabular zur Verfügung zu stellen. Die Datensätze der hier verwendeten Datenquellen "Entrez Gene", "PubMed" sind mit Termen der Ontologien "Gene Ontology (GO)" und "Medical Subject Headings (MeSH)" angereichert. In diesem Projekt werden Assoziationen von GO- und MeSH-Termen untersucht, die sich auf Basis von Pfaden "Entrez Gene -> PubMed" und "Entrez Gene -> OMIM -> PubMed" ergeben. Wir entwickelten das Verfahren "Weighted Path - LSLink" zur Bewertung der Sinnhaftigkeit von Term-Term-Assoziationen, das das viel benutzte Information Retrieval-Maß TF-IDF verwendet. Ein sich aus den Bewertungen ergebendes Ranking soll dem Nutzer Unterstützung bieten, nur noch die Top-Positionen genauer untersuchen zu müssen, um bedeutsame und gegebenenfalls noch unbekannte Term-Term-Assoziationen zu entdecken. Die Evaluation erfolgte durch ein halbautomatisches Verfahren, das einen Quasi-Standard für nachgewiesene Term-Term-Assoziation auf Basis von Artikeln der PubMed-Datenbank bereitstellte. Die Performance unseres "WP-LSLink-Verfahrens" hinsichtlich des Evaluations-Standards wurde mit der Performance der originalen LSLink Methode verglichen. Diese Methode wurde im Rahmen eines vorangegangenen Forschungsprojekt an der Universität von Maryland (University of Maryland - UMD) entwickelt.

Relationship Extraction From Text (Ulf Brefeld)

Semantic processing of natural language is one of the oldest problems in machine learning and still far from being solved. By now, low-level tasks including part-of-speech tagging and named entity recognition are well understood while complex tasks such as parsing, machine translation, and sentiment prediction are still lively subjects of ongoing research. The talk focuses on the identification of relationships in sentences for two reasons. Firsty, detecting relationships is indispensible for a semantic representation and secondly, we can apply state-of-the-art methods to identify them. Starting from classical (pipelined) approaches we'll derive these state-of-the-art techniques by addressing complex tasks in a single optimization problem. We'll also learn about two naturally arising problems: Firstly, the trade-off between performance and execution time and secondly, the quest for annotated data.

Administrationsumgebung für DESWAP (Martin Schmidt)

Gegenstand der Arbeit war die Entwicklung einer Administrationsumgebung. Mit dieser Administrationsumgebung ist es möglich, administrative Prozesse für DESWAP zu vereinfachen und zu automatisieren. DESWAP ist eine Anwendung, die Entwicklern hilft, Semantic-Web-Anwendungen zu entwickeln. Das dafür benötigte Wissen befindet sich in Wissensbasen. Um diese Wissensbasen zu erweitern war es bisher nötig, die Änderungen mit externen Anwendungen, wie z.B. einem Texteditor vorzunehmen. Bei einer solchen Vorgehensweise kann es passieren, dass die Regeln der Wissensbasen verletzt werden oder unerwünschte Nebeneffekte auftreten. Mit der auf die Administration von DESWAP zugeschnittenen Administrationsumgebung werden solche Fehlerquellen ausgeschlossen. Ungültige oder regelverletzende Angaben sind nicht möglich. Dies wird z.B. durch vorgegebene Auswahlmöglichkeiten, in denen nur gültige Angaben ausgewählt werden können, realisiert. Dadurch wird die Administration von DESWAP erleichtert und die Gültigkeit und Widerspruchsfreiheit der Wissensbasen garantiert.

Effiziente Verwaltung von Vertrauensinformationen zu Webdaten (Robert Nagel)

Bei der Verarbeitung von Daten aus dem Web spielt die Beurteilung der Vertrauenswürdigkeit dieser Daten eine wichtige Rolle. Da die Berechnung der Vertrauenswerte ressourcenintensiv ist, ist es notwendig berechnete Vertrauenswerte zu speichern. Im Rahmen der Studienarbeit wurde ein entsprechender Zwischenspeicher entwickelt. Hierfür wurden verschiedene Verdrängungsstrategien und Partitionierungsvarianten evaluiert und implementiert. Im Vortrag werden die Ergebnisse dieser Arbeit präsentiert.

A Hierarchical Approach to Model Web Query Interfaces for Web Source Integration (Thomas Kabisch)

Much data in the Web is hidden behind Web query interfaces. In most cases the only means to surface the content of a Web database is by formulating complex queries on such interfaces. Applications such as Deep Web crawling and Web database integration require an automatic usage of these interfaces. Therefore, an important problem to be addressed is the automatic extraction of query interfaces into an appropriate model. We hypothesize the existence of a set of domain-independent commonsense design rules that guides the creation of Web query interfaces. These rules transform query interfaces into schema trees. We describe a Web query interface extraction algorithm, which combines HTML tokens and the geometric layout of these tokens within a Web page. Tokens are classified into several classes out of which the most significant ones are text tokens and field tokens. A tree structure is derived for text tokens using their geometric layout. Another tree structure is derived for the field tokens. The hierarchical representation of a query interface is obtained by iteratively merging these two trees. Thus, we convert the extraction problem into an integration problem. Our experiments show the promise of our algorithm: it outperforms the previous approaches on extracting query interfaces on about 6.5% in accuracy as evaluated over three corpora with more than 500 Deep Web interfaces from 15 different domains.

Implementation einer ontologiebasierten Suchmaschine unter Nutzung von Lucene und Nutch (Rico Bergmann)

Im Rahmen dieser Arbeit wird zunächst der Begriff "semantische Suche" näher betrachtet. Es wird eine eigene Definition der semantischen Suche gegeben. Dabei interessiert vor allem die Ähnlichkeitssuche als ein wesentlicher Aspekt der semantischen Suche. Neben der bekannten Technik der ontologiebasierten Anfrageerweiterung wird ein Ansatz präsentiert, bei dem bereits der Index der zu durchsuchenden Dokumente um semantisch ähnliche Begriffe erweitert wird. Es wird ein eigener Algorithmus zur Anfrageerweiterung vorgestellt. Dieser Algorithmus wird gleichermassen für die Anfrage- und Indexerweiterung eingesetzt. Die hier entwickelte semantische Suchmaschine wird in einer Beispielanwendung implementiert und getestet. Im Test sollen dabei verschiedene Kombinationsmöglichkeiten der ontologiebasierten Anfrage- und Indexerweiterung betrachtet werden. Das Beispiel beinhaltet die Indizierung und das Durchsuchen von Webseiten aus einem englischsprachigen Medizinforum. Für die Ontologie bildet UMLS (Unified Medical Language System) die Basis.

Entwicklung eines webbasierten Informationssystems mit geografischer Visualisierung für das Projekt "Stolpersteine" (Magdalena Soyka)

Die Stolpersteine sind das Projekt des Künstlers Gunter Demnig, das an Menschen, die Opfer des nationalsozialistischen Regimes wurden, erinnern soll. Viele werden sie kennen aus dem städtischen Alltag: Ein bündig in den Gehweg eingelassener Stein, der Stolperstein,erinnert mit Namen, Jahrgang und dem Datum der Deportation als auch des Todes an einen von den Nazis ermordeten Menschen vor dessen letztem Wohnort. Das Erinnerungsprojekt hat eine besondere dezentrale Struktur. Diese spiegelt sich auch auf organisatorischer Seite wieder: Über 300 Initiativen sind für das Projekt tätig. Daher ist die Dokumentation der Verlegungen und der recherchierten Information zu den Personen in unterschiedlichen Formaten und an verschiedenen Orten vorhanden. Im Rahmen der Studienarbeit wurde eine webbasierte Anwendung konzeptioniert und prototypisch implementiert. Diese bündelt zum einen die an diversen Standorten existierenden Daten von Stolpersteinprojekten und hält sie wartbar als auch recherchierbar vor. Zum anderen werden Hintergrundinformationen über die Personen der Öffentlichkeit zugänglich gemacht. Ein zentraler Aspekt dafür war die technische Umsetzung der automatischen geografischen Visualisierung verlegter Stolpersteine mittels des GoogleMaps-API.

GeneDistiller (http://www.genedistiller.org/) ist eine web-basierte Kandidatengensuchmaschine (Dominik Seelow)

Um die Ursache einer genetischen bedingten Krankheit ermitteln zu können, muß die krankheitsverursachende Mutation gefunden werden. Hierzu werden unter anderem Kopplungsanalysen in Familien durchgeführt, durch die genetische Regionen identifiziert werden, in denen das Krankheitsgen liegen sollte. Diese Regionen umfassen jedoch häufig mehrere hundert Gene, so daß es aus Zeit- und Kostengründen ungünstig wäre, sie alle klassisch zu sequenzieren. Normalerweise werden deshalb zuerst vielversprechende Kandidatengene bestimmt. In der Regel erfassen die Wissenschaftler(innen) dazu sämtliche Gene innerhalb der Region und versuchen, für diese weitere Informationen aus dem WWW oder der Literatur zu finden. Anhand ihres Hintergrundwissens und ihrer Erwartungen können so Gene bevorzugt analysiert oder ausgeschlossen werden. Dieser Ansatz ist jedoch mit einem hohen manuellen Aufwand verbunden, da die vorhandenen Datenbanken entweder die Suche nach Genen in einem Intervall /oder/ die Ausgabe detaillierter Informationen zu einem einzelnen Gen ermöglichten. Eine Alternative stellen automatische Prioritisierungsmaschinen dar, die aus einem Intervall nach verschiedenen Kriterien Kandidatengene auswählen. Hierbei wird jedoch das Hintergrundwissen der Forscher(innen) meist ignoriert und zudem werden von keiner der Applikationen umfassende genspezifische Informationen ausgegeben, so daß vor der kosten- und zeitintensiven Sequenzierung auch hier eine manuelle Recherche im WWW unerläßlich ist. GeneDistiller verknüpft beide Ansätze. Grundlage von GeneDistiller ist eine umfangreiche Datenbank, in die diverse genspezifische Informationen integriert wurden. Dadurch können neben der genetischen Region auch weitere Kriterien zur Selektion der Gene verwendet werden, wie z.B. die Expression im Zielgewebe. Darüberhinaus erlaubt GeneDistiller den Benutzer(innen), auszuwählen, welche der verschiedenen Daten(quellen) für sie relevant sind und dargestellt werden sollen. Für einen schnellen Überblick können bestimmte Eigenschaften oder Schlüsselwörter hierbei optisch hervorgehoben werden. Die Sortierung der Gene kann über eine benutzergesteuerte Priotisierung erfolgen, so daß zum Beispiel nach Ähnlichkeiten oder Interaktionen mit bekannten Krankheitsgenen sortiert werden kann. Da eine Abfrage meist weniger als eine Sekunde dauert, lassen sich sämtliche Einstellungen interaktiv ändern, wodurch die Suchstrategie ständig anhand der Zwischenergebnisse optimiert werden kann und Hintergrundwissen und spontane Einfälle der Wissenschaftler(innen) ausgenutzt werden können. In meinem Vortrag werde ich kurz auf die genetischen Hintergründe der Entwicklung der Software eingehen. Anhand einiger Beispiele werde ich erläutern, wie die externen Daten in die Datenbank integriert wurden. Schlußendlich werde ich die Benutzung des Programms mit verschiedenen Suchansätzen demonstrieren.

Collaborative filtering for movie recommendation (Domonkos Tikk)

The recently finished Netflix Prize data mining competition with its 1M$ Grand Prize motivated many people for participation. The goal of the competition was to beat the predictive power of Netflix's movie recommender system, Cinematch, by at least 10% in terms of prediction error. Given 100M user rating records on movies for training, the participants should predict user ratings on a withheld test set. The talk surveys two main collaborative filtering approaches that found to be effective for such large scale recommendation problems. Matrix factorization methods cast the task into a lower rank matrix approximation problem, and profile users and movies with lower rank feature vectors. Neighbour based methods apply similarity functions for rating approximation. The talk will analyze their efficiency and scalability on the Netflix Prize dataset. Other recommendation related problems such as recommendation for new users or new items will also be discussed.