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

Neue Entwicklungen im Datenbankbereich und in der Bioinformatik

• wann? Dienstags, 15-17 c.t.
• wo? RUD 25, 3.113

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

Graphindexierung nach Agrawal (Andre Koschmieder)

tba.

GeoJoin for in-network event-detection using wireless sensor networks (Timo Glaesser)

In recent years wireless sensors networks have fueled hopes that cheap, distributed environmental monitioring could be at hand. However due to the resource constraints (esp. energy) they have mostly been used as a tool for gathering data while the processing is done at the gateway nodes where resources are practically unlimited. During my talk I will discuss the feasibility of in-network join and aggregate computation and describe suitable algorithms.

Evaluation von Constituent Parsern anhand von Dependency Graphen (Stefan Pietschmann)

In jüngerer Zeit wird vermehrt versucht für die Informationsextraktion (IE) aus biomedizinischen Texten Parsing-Verfahren einzubinden. Dabei werden zwei große Gruppen unterschieden: Constituent Parser, welche Constituent Trees liefern und Dependency Parser, welche Dependency Graphen liefern. Während Constituent Trees die in der (Computer-)Linguistik häufiger angewandte Form ist und damit einhergehend mehr bewährte Parser, hand-annotierte Korpora und ein Annotations-Standard existieren, ist dies für Dependency Graphen bisher nicht der Fall. Allerdings sind diese aufgrund ihrer Form potentiell nützlicher für die IE. In dieser Studienarbeit wird am Beispiel einer Evaluation von zwei beliebigen Constituent Parsern auf Ebene von Dependency Graphen gezeigt, wie sich dieses Dilemma durch Kombination beider Verfahren in gewisser Hinsicht lösen lässt.

Kürzeste Pfade mit GRIPP (Leonid Igorevic Snurnikov)

Effiziente Ausführung von Distanzanfragen auf Graphen ist nicht nur in der Bioinformatik von besonderem Interesse. Im Rahmen meiner Studienarbeit sollte analysiert werden, inwiefern GRIPP (graph indexing based on pre- and postorder numbering) für diese Aufgabe auf skalenfreien Graphen benutzt werden kann. Mit GRIPP lassen sich Erreichbarkeitsanfragen auf sehr großen Graphen in beinah konstanter Zeit beantworten. Ist der Erfolg übertragbar auf Distanzanfragen? Kann man den GRIPP-Index diesbezüglich erweitern oder reicht eine andere Suchstrategie schon aus?

Systems Biology = Networks + Structures: Interaction Networks at Different Levels of Resolution (Michael Lappe)

The quest for determining the function and structure of the protein complement for the human genome is one of the central challenges in the post-genomic era. In this context I will review some of our work on Protein-Protein Interaction networks. We adress the question of how huge this challenge is in terms of the size of the human interactome and how it can be coverd most effectively using existing experimental protocols. I'll also discuss methods to derive additional information harvested from scientific literature using text-mining and methods for functional inference based on this data. Since many measures used in the analysis of PPi networks stem from the analysis of social networks, i.e. the socio-affinity model, it becomes appearant that some architectural features are valid across different (biological) networks. Finally, I will touch on recent work that views protein structures as networks, so-called Residue Interaction Graphs, or RIGs. Some of the features that can be learned from RIGs might help to develop novel concepts and algorithms that might be transferable and prove useful in tackling other biological problems.

Visualisierung der Energie- und Kommunikationsdaten einer auf PowerTOSSIM basierenden Simulation eines drahtlosen Sensornetzwerkes (Christian Czekay)

Die rasanten Fortschritte in der Hardwarefertigung in den letzten Jahren / Jahrzehnten haben den drahtlos kommunizierenden Sensornetzwerken einen weiten Raum an Einsatzmöglichkeiten eröffnet. Um die Robustheit, Korrektheit und Energieeffizienz von neu entwickelten Algorithmen für solche Sensornetzwerke zu prüfen, sind Simulationen unerläßlich. Deren manuelle Auswertung ist mühselig und fehleranfällig und das Ziel meiner Studienarbeit ist es deshalb, ein Web- und Datenbank-gestütztes Werkzeug bereitzustellen, welches den Nutzer dabei unterstützt Simulationen durchzuführen und auszuwerten. Besonderer Wert wurde dabei auf die grafische Visualisierung des Energieverbrauchs und der Kommunikationsaktivität der Sensorknoten gelegt. Als Basis wird der Simulator PowerTOSSIM benutzt. PowerTOSSIM ist ein 'discrete event network simulator' für TinyOS (Betriebssystem für eingebettete drahtlose Systeme) basierte Programme. Im Vortrag wird die Funktionweise des Systems vorgestellt und auf die Skalierbarkeit und die daraus resultierenden Grenzen für die Simulationsgröße eingegangen.

Querying Distributed RDF Data Sources with SPARQL (Bastian Quilitz)

Integrated access to multiple distributed and autonomous RDF data sources is a key challenge for many semantic web applications. As a reaction to this challenge, SPARQL, the W3C Recommendation for an RDF query language, supports querying of multiple RDF graphs. However, the current standard does not provide transparent query federation, which makes query formulation hard and lengthy. Furthermore, current implementations of SPARQL load all RDF graphs mentioned in a query to the local machine. This usually incurs a large overhead in network traffic, and sometimes is simply impossible for technical or legal reasons. To overcome these problems we present DARQ, an engine for federated SPARQL queries. DARQ provides transparent query access to multiple SPARQL services, i.e., it gives the user the impression to query one single RDF graph despite the real data being distributed on the web. A service description language enables the query engine to decompose a query into sub-queries, each of which can be answered by an individual service. DARQ also uses query rewriting and cost-based query optimization to speed-up query execution. Experiments show that these optimizations significantly improve query performance even when only a very limited amount of statistical information is available.

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.

Systematisierung von Layout- und Navigationsverfahren für baumartige Strukturen (Robert Scheffler)

Baumartige Strukturen sind eine spezielle Form von Graphen, die Hierarchien mit zusätzlichen Querverbindungen abbilden. Sie können unter anderem zur Beschreibung von Wissen in technologischen Thesauri oder für parametrisierte Konstruktionsmodelle im Werkzeugbau eingesetzt werden. Um diese Strukturen verständlich zu machen, können sie visualisiert werden. In meiner Studienarbeit stelle ich existierende Methoden des Graph Drawing vor und bewerte ihre Eignung für das Layout von baumartigen Strukturen. Damit sehr große Graphen beherrschbar werden, müssen außerdem geeignete Navigations- und Interaktionsformen für die Darstellung gefunden werden. Im Vortrag stelle ich das Konzept der baumartigen Strukturen und ihre Anwendung vor. Dann gebe ich eine kurze Einführung in das Graph Drawing und behandele ausgewählte Methoden. Abschließend präsentiere ich Vorschläge für die Visualisierung baumartiger Strukturen.

Model-Driven-Architecture(MDA)-Einsatz für Goya (Silvio Pohl)

Im Open-Source-Umfeld gibt es einige interessante Frameworks, die den Einsatz von modellgetriebener Entwicklung ermöglichen. Die "prominentesten" Vertreter sind AndroMDA und openArchitectureWare. Die Studienarbeit zeigt, wie die beiden Frameworks für das Goya-Projekt, angepasst an die Projektrahmenbedingungen, eingesetzt werden können.

Performance-Vergleich semantischer Gen-Ähnlichkeitsmaße (Andrej Masula)

Die Messung der Ähnlichkeit von Paaren von Genen und Proteinen über ein Alignment ihrer Sequenzen ist ein allgemein verbreitetes Verfahren, um funktionale Zusammenhänge zu beurteilen. Alternativ kann die Ähnlichkeit auch auf Basis bereits bestehender wissenschaftlicher Erkenntnisse über dieses Gene beurteilt werden. Damit dies sowohl einheitlich als auch maschinell durchführbar ist, müssen die Erkenntnisse formalisiert werden. Eine Möglichkeit ist, die Formalisierung über Ontologien zu realisieren. In den letzten Jahren wurden einige Maße entwickelt, die die semantische Ähnlichkeit für Gene und Proteine unter Verwendung der Gene Ontology (GO) berechnen. Dabei werden die GO-Terme, die zu zwei Genen annotiert sind, auf Ähnlichkeit untersucht. Da bisher eine vergleichende Analyse semantischer Gen- Ähnlichkeitsmaße fehlte, wurden in dieser Studienarbeit vier verbreitete Verfahren auf ihre Performance geprüft.

Extraktion von räumlichen und zeitlichen Informationen aus Webtexten (Nora Popp)

Ein besonderes Problem bei der Informationsextraktion aus dem Internet stellt die Vielzahl von unstrukturierten Texten dar. In vielen dieser unstrukturierten Texte finden sich Angaben zu Raum und Zeit, Informationen, die in ganz verschiedenen Problemfeldern von großem Interesse und Nutzen sind. So ist es zum Beispiel beim Katastrophenmanagement von großer Wichtigkeit, so genaue Informationen wie möglich über den Ort und die Zeit eines Unglücks oder einer Maßname zu erhalten, um dann schnell und effektiv reagieren zu können. Im Rahmen dieser Studienarbeit wurden verschiedene Herangehensweisen an die Extraktion von räumlicher und zeitlicher Information aus unstrukturierten Webtexten untersucht und gegenübergestellt. Außerdem wurde sowohl eine Methode zur Extraktion von räumlicher Information als auch eine Methode zur Extraktion von zeitlicher Information implementiert und evaluiert. Der Schwerpunkt des Vortrags wird auf der Extraktion von räumlicher Information liegen.

Visualisierung von Expressionsdaten in Pathways (Oliver Arnold)

Bei der Entwicklung von Medikamenten werden unter anderem DNA Microarrays verwendet, um Expressionslevel von Genen zu ermitteln und so die Auswirkung von Medikamenten zu analysieren oder neue Behandlungsmethoden zu erforschen. Um die Auswirkung von veränderten Expressionsleveln zu verstehen, kann es nützlich sein, die Expressionsdaten auf Enzyme zu mappen, die in Pathways Reaktionen katalysieren. In dieser Studienarbeit wurde ein Programm entwickelt, das Pathways zusammen mit Expressionsdaten visualisiert. Signifikante Veränderungen von Expressionen werden farblich hervorgehoben und durch die Auswahl eines Enzymes, können weitere Informationen zu den Expressionen eingesehen werden. Außerdem werden alle Pathways, die Enzyme enthalten, deren Expressionsniveau in einem Experiment beeinflusst wurden, absteigend nach der Stärke der Beeinflussung sortiert.

Aufbau eines Flexionslexikons für die Katalogbereinigung (Johannes Kozakiewicz)

Der EitcoScout bündelt eine Reihe von Technologien aus Statistik und Künstlicher Intelligenz für individuelle Onlineberatung, Diagnoseunterstützung, intelligente Suche etc. Da in derartigen Anwendungen oft große Kataloge eingesetzt werden, wird in einer EitcoScout-Komponente ein Dubletten-Manager entwickelt, der der Optimierung großer Katalogstrukturen dienen soll. Dabei sollen u.a. ähnliche Artikel identifiziert und Dubletten nach unterschiedlichen Strategien gesperrt werden können. Im Rahmen der Vorverarbeitung wird zusätzliches lexikalisches Wissen benötigt, um alle bedeutungstragenden Wörter in den Katalogdaten auf einheitliche Begriffe abzubilden. Dafür wird ein Flexionslexion benötigt, welches mittels verschiedener Generatoren/Filter automatisch erzeugt wurde und deutsche Flexionsformen auf ihre Grundform (Lemma) abbildet.

Pattern-Based Relationship Extraction Made Faster III. (Peter Palaga)

The biomedical literature contains a wealth of information on associations between many different types of objects, such as protein-protein interactions, gene-disease associations, or subcellular locations of proteins. Pattern-based approach has been followed at WBI to extract such associations.
The talk will summarize the author's work at WBI, including:
- Improvements of the WBI's pattern-based relationship extraction system which resulted in a speed-up by 4 orders of magnitude without seriously compromising the quality of the results.
- new and important "learning format" for the relationship annotation developed at the University of Turku, Finnland
- benchmarks using available corpora in learning format.

TBA. (Thomas Wittnebel)

TBA.

Goodbye Console -- Making scientific applications usable (Holger Pirk)

Most scientific projects seem to start out as a console application. Since the scientist himself is the targeted audience usability is not a concern. If the research is succes- and useful though public interest might develop and with it the need of a usable application. Putting a usable Interface on an existing project is a challenge and should not be underestimated.

In our case we developed a Web-UI for an application for Geno- and Phenotype network analysis. Taking our console-application to this next level we experienced a number of problems. These include scalability-issues, concurrency-problems, security concerns, intutive presentation and more. Using existing frameworks can help solving some of these issues but knowing the frameworks limits helps preventing follow-up-problems.

We want to present our solutions and frameworks to prevent others from repeating our mistakes. This will also include a short presentation of the application to demonstrate functionality and UI-presentation.

Ontology Construction from Phenotype Data (Christoph Böhm)

An ontology is a structure that contains concepts that are, where applicable, combined through relations. Nowadays, ontologies play a central role in computational data processing. Here, data is annotated with concepts from an ontology. These annotations allow the processing to use the structure of the ontology and infer semantics. Effective data processing is specifically important in the life sciences since state-of-the-art high-throughput methods allow for the creation of large datasets in a relatively short time.

The theses tackles the ongoing challenge of creating a species-independent ontology for the phenotype aspect in biology. We extract respective concepts as well as relations from a large text corpus. To induce relations we exploit concept cooccurrence, lexical patterns, and domain specific links between objects. We capture these evidences for relations in a universal data model, i.e. a graph, and extract a hierarchy-like structure which forms the resulting ontology graph.

The talk will give an overview of the separate phases in the ontology construction process. It will go into detail on the exploitation of domain specific links between objects. Furthermore, the creation and use of a graph that captures different evidences for relations will be in the focus. Eventually, we will present some results that show that our approach yields reasonable ontologies.