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

Neue Entwicklungen im Datenbankbereich und in der Bioinformatik

• wann? Donnerstag 13.00 - 14.30 c.t.
• wo? Rud 26, 1'303

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

Rekonstruktion biologischer Pathways aus sehr großen Korpora (Franziska Brosy)

Eine maßgeschneiderte Diagnostik für Krankheiten wie beispielsweise Krebs basiert auf dem Verstehen des Verhaltens von Zellen, Gewebe oder Organismen. Funktionsbezogene Ausschnitte der biologischen Prozesse sind Pathways. Diese repräsentieren Beziehungen zwischen biomedizinischen Entitäten als Folge biochemischer Reaktionen. Die grundlegendsten Beziehungen für viele biologische Prozesse sind die Interaktionen zwischen Proteinen (PPI). Für das Gewinnen von Informationen über PPIs gibt es zwei sich gegenseitig ergänzende Wege. Ein Weg ist das Kurieren wissenschaftlicher Veröffentlichungen, die PPIs beschreiben. Rund 13,5 Millionen PubMed Abstracts aus den Jahren 1990 bis 2009 wurden in dieser Arbeit auf das Vorkommen von PPIs untersucht. Zur automatisierten Extraktion der PPIs aus dem Textkorpus wurden Methoden des Text-Minings eingesetzt. Die Proteine und deren Positionen in den Abstracts wurden anhand der in GNAT implementierten Named Entity Recognition ermittelt. Zur Bestimmung der relevanten PPIs wurde die Menge aller satzbasierten Proteinpaare nach verschiedenen Kriterien gefiltert. Zu den Kriterien zählen die Anzahl der Sätze, die eine PPI hervorbrachten und die Klassifikationsergebnisse einer SVM (in Abhängigkeit von: Parametereinstellungen beim Training, Abstand zur Hyperebene). Das Evaluieren der PPI-Extraktion pro Filtermethode erfolgte durch den Abgleich mit den PPIs der Pathwaydatenbanken KEGG und Reactome sowie mit den PPIs eines zirkadianen Regulationspathways. Ausgehend von den Ergebnissen mit dem besten F-Measure für die PPI-Extraktion wurde die Pathway-Rekonstruktion auf Datenbankebene vorgenommen. Für die Pathway-Rekonstruktion wurden die zwei Aspekte Pathway-Abdeckung und Pathway-Erweiterung untersucht. Bei der Pathway-Abdeckung wurde für jeden Pathway und dessen zugehörige PPIs überprüft, ob die PPIs in der Menge der Textkorpus-PPIs wiederzufinden sind. Bei der Pathway-Erweiterung wurden für jeden Pathway die Textkorpus-PPIs auf die PPIs reduziert, die aus den im Pathway vorkommenden Proteinen bestehen. Die verbleibenden PPIs repräsentieren eine potentielle Vervollständigung des Pathways. In der Quintessenz ist festzustellen, dass die Rekonstruktion für einige PPI-Pathways komplett möglich ist und potentiell neue PPIs für Pathways mit einer durchschnittlichen Precision von 20% für KEGG, 48% für Reactome und 40% für den zRPW gefunden werden.

Error detection in Information Extraction Results (Wojciech Barczynski)

Large-Scale Information Extraction (IE) recently has attracted considerable attention in research and business. The overall goal is to enable the harvesting of the great amount of valuable information that is constantly published in articles, blogs, websites social networks etc. However, the complexity of natural language still makes it impossible to develop IE systems that can guarantee a certain level of accuracy in any real world setup. However, such high quality data is necessary for the creation of analytical solutions taking into account IE results. Given the absence of systematic approaches to quality assurance of IE, the currently predominant approach is to devote most of the time of an IE project to debugging mistakes the IE system makes, leading to an iterative process of adjusting the IE (re-) configuration, testing the system, spotting  errors, identifying their roots, and prioritizing possible remedies. Our aim is to support error detection and resolution in the development of IE system. We present methods and a tool that support a developer in these tasks by implementing a rule-based error detection approach. The error detection rules are defined in declarative style and can be freely added to the engine to adapt our tool to requirements of specific domains.

ARH - Alternative Splicing Robust Prediction by Entropy Complementing Differential Expression on Exon Arrays (Axel Rasche)

Exon arrays can be analysed in two directions: differential expression analysis and alternative splicing analysis. The processing of the arrays follows two fundamental principles: First, only biologically motivated corrections on the data are allowed with statistical models. Second, comparability between experiments is essential. Where research on 3' gene expression arrays is settled, the analysis of exon microarrays has posed new challenges to the computational analysis like data normalisation and presence tag calculation. Probe binding affinity correction by GC content and background correction had to be redeveloped due to changes in design and protocol. Data evaluation establishes an array-wide gene analysis followed by the isolation of a set of alternatively spliced genes as well as a set of differentially expressed genes. It follows the gene set evaluation with over-representation analysis and group testing on a diverse set of functional resources like pathway databases, transcription factor targets, drug targets and tissue expression. A statistical model is developed to analyse splicing events based on a modified entropy function (ARH - Alternative splicing Robust prediction by Entropy) in order to judge significance of alternative splicing. Using benchmark data sets ARH is evaluated along with eight different methods. To assess the characteristics of the different methods the performance is analysed dependent on aspects such as alternative splicing prediction in presence or absence of differential expression, alternative splicing prediction with respect to replicate numbers and with respect to exon number. The major drawback in developing and comparing new splicing prediction methods is the lack of controlled data sets as available for the standard arrays. Three approaches for validation are used in the method comparison: * Tissue specific splicing with manually collected splicing events, * tissue specific splicing with RT-PCR validated splicing events and * artificial transcript spike-in experiments.

Herkunftsbasierte Bestimmung der Vertrauenswürdigkeit von Web-Daten (Thomas Riegmann)

Mit semantischen Technologien in das Web sind die ersten Schritte zur nächsten Generation des World-Wide-Web gemacht. Zur Zeit nimmt die Veröffentlichung von Daten im Semantic-Web immer mehr zu, wodurch eine größer werdende Anzahl von Anwendungen im Semantic-Web entwickelt wird. Die verarbeiteten Daten leiten die Anwendungen weiter und modifizieren die Daten automatisiert. Jeder kann im Semantic-Web Daten erzeugen und diese zur Verfügung stellen. Das bedeutet, dass die Daten ohne Prüfung mit einer gewissen Zurückhaltung zu behandeln sind. Da die Verarbeitung der Daten automatisiert erfolgt, sollte die Bestimmung von Vertrauenswürdigkeit mit eingeschlossen sein. Dies wurde bisher nicht berücksichtigt, deshalb soll im Rahmen dieser Arbeit ein Ansatz für die Bestimmung der Vertrauenswürdigkeit entwickelt werden. In der realen Welt interessieren bezüglich der Vertrauenswürdigkeit von Informationen häufig Dinge wie die Quelle der Information, wer sie übermittelt und auch auf den Inhalt der Daten. Entsprechend besteht auch für Web-Daten die Notwendigkeit diese mit Informationen über ihre Herkunft zu versehen. Im Rahmen dieser Arbeit war eine Methode zu entwickeln, die die Vertrauenswürdigkeit von Web-Daten anhand von Herkunftsinformationen bestimmt und eine optimierte Berechnung von Vertrauenswerten ermöglicht. Dabei soll der Nutzer Einfluss auf die Berechnung der Vertrauenswerte nehmen können. Es wird der Vertrauensbegriff aus Sicht der Sozialwissenschaften betrachtet, Vertrauen in Daten und deren Einflussfaktoren bezüglich der Vertrauenswürdigkeit erläutert. Die Methode zur Berechnung von Vertrauenswerten für Datenobjekte in Abhängigkeit von ihren Einflussfaktoren wird beschrieben und gezeigt, wie Ungewissheiten bei der Berechnung dargestellt werden können. Zudem wird betrachtet, wie die Berechnung eines Vertrauenswertes optimiert ausgeführt werden kann. Abschließend erfolgt eine Zusammenfassung der Arbeit und ein Überblick über die gewonnenen Erkenntnisse. Außerdem wird auf notwendige Weiterentwicklung bezüglich der Vertrauenswürdigkeit von Web-Daten und die optimierte Berechnung von Vertrauenswerten eingegangen.

Probevortrag: RDFMatView: Indexing RDF Data using Materialized SPARQL queries (Roger Castillo)

The Semantic Web aims to create a universal medium for the exchange of semantically tagged data. The idea of representing and querying this information by means of directed labelled graphs, i.e., RDF and SPARQL, has been widely accepted by the scientific community. However, even when most current implementations of RDF/SPARQL are based on ad-hoc storage systems, processing complex queries on large data sets incurs a high number of joins, which may slow down performance. We propose materialized SPARQL queries as indexes on RDF data sets to reduce the number of necessary joins and thus query processing time. We provide a formal definition of materialized SPARQL queries, a cost model to evaluate their impact on query performance, a storage scheme for the materialization, and an algorithm to find the optimal set of indexes given a query. We also present and evaluate different approaches to integrate materialized queries into an existing SPARQL query engine. An evaluation shows that our approach can drastically decrease the query processing time compared to a direct evaluation.

Trimming Dependency Graphs for Event Extraction (Ekaterina Buyko)

The most recent BioNLP 2009 Shared Task on Event Extraction required to determine, from a sample of Medline abstracts, all mentioned events of nine bio-molecular interaction types, including, e.g., Binding, Transcription and Regulation events. In our approach to event extraction, dependency graphs constitute the fundamental data structure for knowledge capture. Two types of trimming operations pave the way to more effective relation extraction, syntactic simplification and semantic enrichment. Given the methodological framework of the corresponding JReX (Jena Relation Extraction) system, the JulieLab Team scored on 2nd rank in the BioNLP 2009 Shared Task. In more recent experiments, based on slight modifications of JReX and using the same data sets, we were able to achieve 45.7% recall, 57.6% precision and 51.0% F1-score. I will present the Shared Task solution of the JulieLab system and discuss the role of different representation formats of dependency graphs in the event extraction task. Furthermore, I will present our extrinsic evaluation studies of real-life information extraction scenarios.

Boosting Relation Extraction with Limited Closed-World Knowledge (Sebastian Krause)

A number of different approaches to the acquisition of relation-extraction rules exist. In contrast to supervised learning algorithms and manual approaches, using a minimally supervised method requires only a small number of hand-crafted examples in order for a learning algorithm to start. Unfortunately, minimally supervised machine-learning systems are faced with the problem of learning wrong rules, which lead to faulty precision in the extraction task. However, there is a lot of domain-specific knowledge available for many target relations that can be exploited for validation of learned results. The underlying student research project proposes an approach to rule-confidence estimation that makes use of the additional domain knowledge. The knowledge is re-structured to form closed worlds, which gives Relation-Extraction (RE) systems the ability to reason about the correctness of extracted relation instances and learned rules during the learning process. This information is included into the rule ranking to boost the rating of good performing rules and therefore increase the overall extraction precision. Two concrete ranking methods were evaluated using the existing RE system DARE (Domain Adaptive Relation Extraction). The results for two different domains will be discussed.

Moara project: entity recognition, normalization and relation extraction (Mariana Lara Neves)

Moara is a Java library that implements gene/protein tagger and normalization steps based on machine learning approaches. The gene/protein recognition task is based on the case-based reasoning (CBR) approach while their normalization uses an exact and an approximate matching, the latter based on the machine learning algorithms. Both steps may be trained with extra documents for the recognition procedure and new organisms may be added in the normalization component. Moara also includes a relation extraction system also based on CBR foundations. This system has been evaluated in the BioNLP’09 Event Extraction challenge for the extraction of biological events and with the BioText corpus for the relation between diseases and treatments. Moara is available at: http://moara.dacya.ucm.es.

Analyse von parallelen Programmierumgebungen im Kontext von Datenbanksystemen (Robert Nagel)

Aufgrund immer schneller wachsender Datenmengen wird zur Verarbeitung der Daten immer höhere Rechenleistung benötigt. Bis vor wenigen Jahren wurde die Rechenleistung einzelner Prozessoren durch die Erhöhung der verwendeten Taktfrequenz gesteigert. Diese Variante der Leistungssteigerung ist jedoch kaum mehr praktikabel, da dabei inzwischen physikalische Grenzen erreicht werden. Zum einen sind das thermische Probleme, da immer mehr Abwärme abgeführt werden muss. Zum anderen werden bei höheren Taktfrequenzen auch die Signallaufzeiten innerhalb der Chips immer stärker zum limitierenden Faktor. Ein Weg, zusätzliche Rechenleistung nutzbar zu machen, ohne die Taktfrequenzen zu erhöhen, ist die Bereitstellung von mehr Recheneinheiten, die gleichzeitig Daten verarbeiten können. Eine aktuelle Variante der Recheneinheiten-Vervielfachung sind die sogenannten Mehrkern-Prozessoren. Da diese Mehrkern-Prozessoren aktuell einer breiten Öffentlichkeit zur Verfügung stehen, steigt der Bedarf nach Software, die diese Vielzahl an Kernen nutzen kann, stark an. Für die Entwicklung solcher Software wiederum sind Möglichkeiten zur einfachen Handhabung und Nutzung der verfügbaren parallelen Rechenleistung notwendig. Diese Arbeit stellt verschiedene Arten der Parallelität vor und untersucht, wie diese mithilfe paralleler Programmierumgebungen ausgenutzt werden können. Das Hauptaugenmerk wird dabei auf die Ausnutzung der Parallelität innerhalb von Datenbanksystemen gelegt.

TBA (Hagen Möbius)

TBA

Erkennung chemischer Entitäten im VirtualLiver Projekt (Tim Rocktäschel)

Named Entity Recognition ist für Text-Mining-Anwendungen von großer Wichtigkeit. Der Erkennung von Protein- und Gennamen wurde in den letzten Jahren viel Aufmerksamkeit geschenkt. Zahlreiche Tools (u.A. BANNER, ABNER, GNAT, GENO, SciMiner, LingPipe) und Trainingskorpora sind entstanden. Für das zu entwickelnde Kurator-Tool im VirtualLiver Projekt ist dagegen die Erkennung chemischer Entitäten von zentraler Bedeutung. Dazu existiert bislang lediglich Oscar3 als frei verfügbare Software. Der Vortrag wird auf die Herausforderungen bei der Erkennung chemischer Entitäten eingehen und die Verbesserung der Precision von Oscar3 durch verschiedene Filter vorstellen. Anschließend werden die bisher gesammelten Erfahrungen bei der Integration von Oscar3 in UIMA, einer weit verbreiteten Architektur zur Erstellung von Text-Mining-Pipelines, geschildert.

Media Metrics - Text Mining in der Medienbeobachtung (Daniel Kummer)

Media Metrics ist ein Startup im Bereich der Medienbeobachtung, das von der Humboldt-Universität und von Prof. Dr. Ulf Leser als Mentor unterstützt wird. Im Vortrag stellt sich Media Metrics vor. Dabei wird dargestellt, welche Anforderungen sich im Rahmen moderner Medienbeobachtung stellen und inwiefern Text Mining dabei eine zentrale Rolle spielt. Am Beispiel von u.a. Sentiment Analysis wird erläutert, welche praktischen Probleme die Umsetzung theoretischer Verfahren erschweren.

EquatorNLP - Erkennen von Angaben über Erdbebenschäden in Textmeldungen (Lars Döhling)

Nach einem Erdbeben sind Informationen über das Ausmaß der Schäden zentrale Entscheidungsfaktoren über Hilfseinsätze und deren Koordinierung. Eine Quelle für solche Angaben sind natürlichsprachliche Texte, welche aufwändig manuell ausgewertet werden müssen. In einer Diplomarbeit wurde untersucht, inwieweit es möglich ist, die benötigten Informationen automatisch zu extrahieren. Dazu wurde für ein bestehendes CMS ein Softwaremodul zur Extraktion einer komplexen Relation entwickelt, welche die durch Erdbeben verursachten Schäden an Menschen erfasst. Diese Extraktion gliedert sich in zwei Phasen: Identifikation der Entitäten (Named Entity Recognition, NER) und der Beziehungen zwischen ihnen (Relationsextraktion, RE). Für die erste Phase wurde ein kombinierter Ansatz aus Lexikonabfragen und Nachbereitungsregeln entwickelt. Für die anschließende RE-Phase wurde eine zweiteilige Methode untersucht, welche zuerst einen Graph von Entitätspaaren mithilfe eines Musterabgleichs in Dependenzgraphen bestimmt und anschließend daraus die komplexen Relationsinstanzen durch Suche nach Maximalen Cliquen synthetisiert. Im Vortrag werden die entwickelten Methoden erläutert und die Ergebnisse einer Evaluation auf einem domänenspezifischen Korpus vorgestellt.

PubMed-Relevanzranking mit Lucene (Christoph Jacob)

Mit mittlerweile über 20 Mio. referenzierten wissenschaftlichen Artikeln stellt die frei verfügbare Datenbank PubMed den ersten Anlaufpunkt für Recherchen im biomedizinischen Sektor dar. Die schwache Strukturierung der enthaltenen Volltexte sowie Probleme wie Synonymie und Ambiguität erschweren die Suche. So werden für einfache Boolsche Anfragen oft unüberschaubar viele Ergebnisse zurück gegeben, deren Relevanz der Nutzer selber überprüfen muss. Daher haben sich in den vergangenen Jahren einige Systeme etabliert, welche den Nutzer bei der Suche nach relevanten Informationen unterstützen - so auch das am Lehrstuhl WBI entwickelte Informationssystem GeneView, welches eine Gen-zentrierte Suche mit Hilfe der Volltextsuchmaschine Lucene implementiert. Im Rahmen einer Studienarbeit wurden auf PubMed basierende Informationssysteme hinsichtlich ihres Relevanzrankings sowie bestehende Rankingverfahren auf ihre Tauglichkeit im biomedizinischen Kontext untersucht. Darüber hinaus wurde GeneView um zwei Rankingverfahren erweitert: das Erste basiert auf der Möglichkeit Volltexte in Sektionen wie Title, Abstract, Introduction usw. zu unterteilen und führt eine nach Sektionen gewichtete Suche durch um Dokumente welche den Suchterm z.B. im Titel enthalten höher zu ranken. Das zweite Verfahren bedient sich der GeneOntology und erweitert den ursprünglichen Suchterm um verknüpfte Konzepte. Beide Verfahren wurden anhand eines eigens erstellten Goldstandards evaluiert mit dem Ziel, optimale Sektionsgewichtungen zu ermitteln und damit das Ranking der Suchergebnisse in GeneView zu verbessern. Die Ergebnisse der Studienarbeit, sowie die Vorgehensweise zur Ermittlung optimaler Gewichtungen werden in diesem Vortrag präsentiert.

Computational approaches to the study of gene function (Miguel Andrade)

Our group uses and develops computational methods and databases for the prediction of functions of genes and proteins with a focus on human disease. I will present an overview of recent results on several fronts: prediction of RNA transcripts, analysis of stem cell gene expression, analysis of protein repeats, and text mining.

Warehousing Web Data (Ioana Manolescu-Goujot)

The development and increased popularity of Web-based applications have lead to large and fast increasing volumes of Web-related data sources. We mainly consider data under the form of structured documents (i.e. XML) and Semantic Web data (i.e., RDF and its associated semantic schema language, RDF-S). The scale and complexity of this data require scalable techniques for storing, indexing, distributing and querying. The talk will present works carried in the Leo (formerly Gemo) group of INRIA Saclay, France, on building efficient warehouses for Web data. The first part of the talk will be concerned with large-scale distributed publishing and sharing XML data within the ViP2P platform (http://vip2p.saclay.inria.fr). ViP2P is a fully implemented platform whose scalability was tested when deployed over hundreds of peers in a WAN. In the second part of the talk, I will describe the RDFViewS project which aims at speeding up RDF query processing based on materialized views which also exploit data semantics. Finally, I will conclude by briefly discussing ongoing developments related to building distributed warehouses of XML and RDF data.

Accurate long-read alignment using prefix tree indexing and similarity based multiple pattern alignment (Astrid Rheinländer)

Sequence analysis is one of the main challanges in current bioinformatics. In particular, the alignment of sequences to each other is used for finding structural, functional, or evolutionary relationships between two sequences and to identify highly conserved regions in a genome. With next-generation sequencing devices, the sequencing costs can be immensely reduced at the tradeoff of a higher number of erroneous reads. Although there exist popular tools such as BLAST or BLAT, these tools do not scale well to the amount of data produced by next-generation sequencing. Plus, many of these tools cannot guarantee a completely accurate alignment result. In this talk, we present PeARL, a tool for similarity based long-read alignment that produces 100 % accurate alignment results. The alignment algorithm is built on top of a prefix tree based data structure that is capable to index large read collections and entire genomes. We introduce the alignment algorithm together with pruning strategies and describe how PeARL can be parallelized using a MapReduce inspired approach. We discuss the performance of our tool in terms of accuracy and alignment speed in comparison with two other alignment tools and we also cover the achieved speed-up and scale-up when running PeARL in parallel.

Scan Merging - zur verbesserten Peptidsequenzierung durch Fusion von Massenspektrometriedaten (Martin Filip)

Das DBnovo-Projekt ist eine interdisziplinäre Zusammenarbeit der Institute Chemie und Informatik der HU-Berlin. Zielstellung dieses Projektes ist die Sequenzierung von Peptiden in komplexen Peptidgemischen. Die spezifische Abfolge einzelner Aminosäuren ist für jedes Peptid charakteristisch. Ziel ist es, die Abfolge der Aminosäuren zu ermitteln. Per Massenspektrometrie wird ein Peptid durch Bindungsbrüche zwischen den Aminosäuren in kleinere Fragmente zerteilt und deren „Masse zu Ladungsverhältnis“ gemessen. Jedes Fragment erzeugt in dem Fragmentspektrum ein Signal, das die Intensität des gemessenen „Masse zu Ladungsverhältnisses“ wiedergibt. Die relevanten Signale werden ermittelt und die Massendifferenz zwischen ihnen berechnet. Da alle Aminosäuren eine spezifische Masse besitzen, lassen sich aus den Massendifferenzen die Aminosäuren identifizieren. Aus den Daten wird ein Graph aufgebaut. Jeder Knoten steht für einen Signal, jede Kante zwischen zwei Knoten steht für genau eine Massendifferenz und damit für Kompositionen von Aminosäuren. Wie kann man aus der Kombination inzelner Scans mehr Informationen gewinnen und damit die Anzahl der Messungen reduzieren?

Dynamic Join Algorithm Switching at Query Execution Time (Matthias Sax)

Join optimization is one of the most challenging tasks in query processing. The performance of joins depend not only on the algebraic/logical query execution plan (QEP), but also on the chosen join algorithms. Static optimization techniques often suffer from outdated or unavailable statistics on the data. This results in sub-optimal QEPs and poor query execution times. Adaptive Query Processing (AQP) tackles this problem. The execution of the query gets monitored and the QEP can be re-optimized if plan suboptimalities are encountered. This work introduces a new AQP technique by applying Antoshenkov's competition model to join operations within Avnur's and Hellerstein's Eddy operator. Our technique allows us, to change the join algorithm during query execution on the fly. Non of the current AQP techniques did this so far. As this work is part of the Stratosphere research project, we will run in a highly parallelized MapReduce like environment. We assume that the input will fit into main-memory completely. Hence, the overhead of running multiple join-operators in parallel is neglected and we can expect a big performance advantage over other optimization techniques.

Evolution von Ontologien in den Lebenswissenschaften (Michael Hartung)

In den Lebenswissenschaften haben sich Ontologien in den letzten Jahren auf breiter Front durchgesetzt und sind in vielen Anwendungs- und Analyseszenarien kaum mehr wegzudenken. So etablierten sich nach und nach immer mehr domänenspezifische Ontologien, z.B. Anatomie-Ontologien oder Ontologien zur Beschreibung der Funktionen von Genen oder Proteinen. Da das Wissen in den Lebenswissenschaften sich rapide ändert und weiterentwickelt, müssen die entsprechenden Ontologien ständig angepasst und verändert werden, um einen möglichst aktuellen Wissensstand zu repräsentieren. Nutzer von Ontologien müssen mit dieser Evolution umgehen können, d.h. um "Up-to-Date" zu sein, sollten die aktuellsten Versionen einer Ontologie verwendet werden. Dies ist häufig nur schwer umsetzbar, da die Evolution weitreichende Einflüsse auf existierende Datenbestände, Analyseergebnisse oder Anwendungen haben kann. Innerhalb des Vortrags wird auf Werkzeuge und Algorithmen zum Umgang mit sich ständig ändernden Ontologien im Bereich der Lebenswissenschaften eingegangen. Zunächst wird ein generelles Framework für quantitative Evolutionsanalysen präsentiert. Das Framework gestattet umfassende Analysen der Evolution von Ontologien und Mappings. Ergebnisse zeigten, dass alle untersuchten Ontologien/Mappings stetig verändert werden und ein signifikantes Wachstum aufweisen. Es existiert somit der Bedarf Nutzer mit entsprechenden Algorithmen/Werkzeugen zu unterstützen. So besteht eine immer wiederkehrende Aufgabe in der Bestimmung von Änderungen zwischen zwei Versionen einer Ontologie, d.h. worin besteht der Unterschied (Diff) und wie hat sich die neuere Version aus der alten Version heraus entwickelt. Dazu wird ein auf Regeln basierter Algorithmus vorgestellt, welcher den Diff zwischen zwei Ontologieversionen bestimmt. Es werden sowohl einfache wie auch komplexe Änderungen erkannt, was eine kompakte und verständliche Diff-Repräsentation garantiert. Die enorme Größe von Ontologien in den Lebenswissenschaften erschwert es Nutzern oftmals deren Evolution kompakt und intuitiv zu erfassen. Hierzu wird ein neuartiger automatisierter Algorithmus zur Bestimmung (in)stabiler Ontologieregionen präsentiert. Nutzer können somit stark geänderte oder stabile Teile innerhalb einer Ontologie aufspüren und Trends in deren Entwicklung abschätzen. Abschließend wird auf das webbasierte System OnEX eingegangen. OnEX erlaubt einen interaktiven Zugang zu Informationen über die Evolution und Änderungen in Ontologien. Durch einen speichereffizienten Versionierungsansatz konnten 16 Ontologien mit ca. 700 Versionen versioniert und über OnEX zugänglich gemacht werden.

Parallelisierung von Text Mining Workflows in einer Cloud (Erik Drießler)

Der Vortrag soll einen Zwischenstand über die Diplomarbeit "Parallelisierung von Text Mining Workflows in einer Cloud" liefern. Ziel der Diplomarbeit ist es, mit U-Compare erstellte UIMA TextMining Workflows unter Verwendung von Nephele in einer Cloud-Umgebung verteilt zur Ausführung zu bringen. Die Erstellung eines Workflows und dessen Test über einer kleinen Datenmenge erfolgt über U-Compare. Nach dem Export des Workflows wird weitestgehend automatisiert ein JobGraph für Nephele kreiert, welcher durch Nephele verteilt im EC2 Umfeld ausgeführt wird. In einem zweiten Punkt der Diplomarbeit wird ein Wiederaufsetzkonzept für  Workflows entwickelt, um eine Effizienzsteigerung bei deren Ausführung zu erreichen. Die Zwischenergebnisse abgeschlossener Workflowdurchläufe werden in die JobGraph-Generierung einbezogen, um die notwendigen Workflowschritte zu reduzieren. In einem weiteren Schritt kann dieses Konzept auf Fehlerbehandlung erweitert werden. Fehlgeschlagene Workflowläufe können für einen neuen Durchlauf die Zwischenergebnisse des gescheiterten Durchlaufs verwenden. Der Schwerpunkt des Vortrags soll auf dem Zusammenspiel von UIMA, Nephele und der verteilten Ausführung liegen. Hierbei soll auch über Erfahrungen und Schwierigkeiten mit Nephele berichtet werden.

Text Mining for the Reconstruction of Protein-Protein Interaction Networks (Quang Long Nguyen)

A wealth of information is available only in web pages, patents, publications etc. Extracting information from such sources is the main purpose of text mining. This thesis focuses on the application, evaluation and the improvement of pattern-based approaches applied to relation extraction from biomedical documents. It presents techniques that improve a given baseline system, the Ali Baba algorithm for pattern-based relationship extraction, in all relevant aspects, i.e., recall, precision, and extraction speed. The thesis first reviews various information extraction approaches for the discovery of complex events among genes and proteins. Next, we introduce techniques for filtering sets of automatically generated patterns and analyze their effectiveness for different information extraction tasks. Essentially, our approach provides a solution to the problem of finding a ‘good” set of patterns in pattern-based relation extraction. We show that our techniques yield large improvements in all tasks we analyzed. For instance, they double the F-score for the task of gene expression extraction compared to the use of the original Ali Baba system. As a second major contribution, we present a simple yet effective filtering technique aiming at increasing the speed of relation extraction. The technique is based on evaluating patterns based on their potential to result in high scoring matches for a given sentence. We show that this idea leads to considerable speed-ups while incurring only a negligible penalty in effectiveness. For instance, they can yield a 100-fold increase in extraction speed at only 3% worse F-score. Finally, we present result of a large-scale application of our system to all available MEDLINE abstracts. The extraction results are evaluated by comparing them to manually curated information from biological databases. Overall, we used patterns that are automatically generated from 5 million citations to extract protein-protein interaction from other 15 million citations. Our system achieved precision, recall and F-score of 7.2%, 28.3% and 11.5%, respectively. We show that, our system generates patterns automatically without using any gold standard corpus and thus avoids tedious and time-consuming task of the manual curation of training data. In addition, our system performs very fast due to the simplicity and the effectiveness of pattern filtering algorithm.

Improving the prediction of miRNA function by integration of miRNA target predictions and gene regulatory networks (Marie Gebhardt)

One of the first transcription factors examined by ChIP-seq was the RE1 silencing transcription factor (REST; Neuron-restrictive silencing factor, NRSF), which is known as a repressor of neuronal genes in non-neuronal tissue like Jurkat cells and is for example involved in Huntington’s disease. Many miRNAs regulated by REST (REST-miRNAs) are known from ChIP-seq and other experiments. Based on this knowledge the question arose if one can find predicted binding sites for REST-miRNAs overrepresented in the 3’UTRs of REST regulated genes to see if there is a cooperation of the transcriptional repressor with the repressing miRNAs. Computationally predicted binding sites for the whole human genome were used for overrepresentation analysis regarding all genes not regulated by REST as a background and calculating p-values by randomization. Some miRNAs could be identified to be overrepresented in REST regulated genes but not in neuronal specific genes. This type of analysis generates interesting candidates for further examination and points to possible circuits and interactions in the marginally elucidated network of transcription factors and miRNAs. It will be extended to multiple ChIP-seq datasets. Since miRNA-binding site predictions still suffer from high false positive rate, upcoming techniques like HITS-CLIP and PAR-CLIP will soon be used to filter current miRNA predictions and improve the identification of regulatory networks.

How Caching Improves Efficiency and Result Completeness for Querying Linked Data (Olaf Hartig)

Link traversal based query execution is a novel query approach which enables applications that exploit the Web of Data to its full potential. This approach makes use of the characteristics of Linked Data: During query execution it traverses data links to discover data that may contribute to query results. Once retrieved from the Web, the data can be cached and reused for subsequent queries. We expect such a reuse to be beneficial for two reasons: First, it may improve query performance because it reduces the need to retrieve data multiple times; second, it may provide for additional query results, calculated based on cached data that would not be discoverable by a link traversal based execution alone. However, no systematic analysis exist that justifies the application of caching strategies based on these assumptions. In this talk we evaluate the potential of caching to improve efficiency and result completeness in link traversal based query execution systems. We conceptually analyze the potential benefit of keeping and reusing retrieved data. Furthermore, we verify the theoretical impact of caching by conducting a comprehensive experiment that is based on a real-world application scenario.

A Main Memory Index Structure to Query Linked Data (Olaf Hartig)

A possible approach to query Linked Data combines the actual evaluation of a query with the traversal of data links in order to discover and retrieve potentially relevant data. An implementation of this idea requires approaches that support an efficient and flexible management of temporary, ad hoc data collections that emerge during query execution. However, existing proposals for managing RDF data primarily focus on persistent storage and query execution for large datasets and, thus, are unsuitable in our dynamic scenario which involves many small sets of data. In this talk we investigate main memory data structures to store Linked Data in a query execution system. We discuss the requirements for such a data structure, introduce three strategies that make use of hash table based indexes, and compare these strategies empirically.

Scoring Protein Function Predictions (Björn Pollex)

In my thesis I have developed, implemented and evaluated two methods for generating scored protein function predictions based on the binary function prediction method developed by Samira Jaeger. The goal was to find a scoring scheme, such that higher scores indicate a higher probability that a prediction is correct. The first step was to transform annotations into feature vectors that represent the supporting evidence for this annotation. These supporting evidences are derived from protein-protein-interactions that are conserved among multiple species, as well as ortholgy relationships among proteins. I implemented and evaluated two methods to derive scores from these feature vectors. The first method is a simple sum-of-scores apprach, while the second one is based on a k-NN search in the feature space. Since there is no accepted standard method of evaluating protein function prediction algorithms, a lot of work went into formulating an appropriate evaluation scheme. In this talk I will provide a summary of these topics and present some of the results I have gathered. While one algorithm clearly outperforms the other, both offer a lot of potential for future research. With my talk, I hope to inspire an interesting discussion that gives rise to new ideas.