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

Neue Entwicklungen im Datenbankbereich und in der Bioinformatik

• wann? Dienstags, 13-15 c.t.
• wo? RUD 26, 0'307

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

Hierarchische Versionierung in relationalen Datenbanken (Karsten Lohse)

Das Ziel meiner Studienarbeit ist die Entwicklung einer leistungsfähigen hierarchischen Versionierungsstrategie in relationalen Datenbanken, die auch den Zugriff von Altanwendungen ermöglicht, die diese Versionierung nicht unterstützen. Die entwickelte Strategie wurde mit den Daten von SwissProt gemessen werden. Diese Messung wurde mit einer Datenbank ohne Versionierung und mit dem Oracle Workspace Manager verglichen werden.

TextGrid - Integration in den Textwissenschaften (Thorsten Vitt)

Das Projekt TextGrid errichtet eine grid-fähige Workbench für die gemeinschaftliche philologische Bearbeitung, Analyse, Annotation, Edition und Publikation von Textdaten. Dabei geht es in weiten Teilen um Verknüpfung und Integration: Im Bereich der Suche gilt es, verschiedene Suchtypen über unterschiedliche Datenbestände (z.Z. Metadaten über Objekte, Beziehungen zwischen Objekten, Volltext- und Strukturinformationen in Objekten sowie Authorisierungsinformationen) miteinander zu integrieren. Der Arbeitsplatz der Textwissenschaftler muss lokale und entfernte Werkzeuge und Daten miteinander integrieren und den (technisch unterschiedlich versierten) Fachwissenschaftlern Mittel an die Hand geben, um ihre Texte und Editionen einfach mit anderen Ressourcen zu verknüpfen. Externen Initiativen müssen zudem einfache Möglichkeiten zur Verfügung gestellt werden, ihre Werkzeuge und Ressourcen in TextGrid und umgekehrt TextGrid-Dienste in ihre Infrastruktur zu integrieren. Der Vortrag gibt einen Überblick über die TextGrid-Architektur und Details zu ausgewählten Lösungen.

XML versus RDBMS: Performanz und Implementierung linguistischer Anfragen (Matthias Bindernagel)

Ziel der vorliegenden Arbeit ist es, zwei Implementationen von einfachen Anfragesprachen gegen ein annotiertes Textkorpus in Hinsicht auf ihre Performanz und Praktikabilität zu vergleichen. Die erste Implementation basiert auf einem relationalen Datenbankmanagementsystem. Anfragen gegen das Korpus werden nach SQL übersetzt und ausgeführt. Die zweite Implementation beruht auf einem Korpus im XML-Format. Für die Speicherung wird eine XML-Datenbank verwendet. Anfragen werden vor ihrer Ausführung nach XQuery übersetzt. Für den direkten Vergleich der beiden Varianten wird ein allgemeines Datenformat der Text- und Annotationsdaten spezifiziert, ausserdem wird eine allgemeine Anfragesprache vorgestellt. Die Ergebnisse dieser Arbeit können keine Empfehlung zugunsten einer der getesteten Implementationen aussprechen. Sowohl die relationale als auch die XML-basierte Umsetzung sind in der in dieser Arbeit verwendeten Form nicht fähig Anfragen gegen ein umfangreiches Korpus effizient auszuführen und im Rahmen einer Webapplikation verwendet zu werden. Die durchgeführten Messungen zeigen jedoch konkrete Schwachstellen in der Informationsorganisation und der Implementation auf, deren genauere Untersuchung einer weiteren Implementation vorangehen sollte.

Optimierung von Workflow-Anwendungen durch mengenorientierte Verarbeitung (Henning Zahn)

Diese Arbeit verfolgt die Annahme, dass das Sammeln von Bestellanfragen zeitnah laufender Geschäftsprozesse (Workflows) zu einer Optimierung der betriebswirtschaftlichen Performanz des Gesamtsystems führt. Dazu werden deren Nachrichten an gemeinsam genutzte Dienstanbieter derart akkumuliert, dass sich ein Wechsel von einer Vielzahl von Einzelbestellungen zu einer einzigen Sammelbestellung vollzieht. Auf diese Weise kann oftmals ein niedrigerer Einstandspreis für die erstandene Ware oder Dienstleistung erreicht werden. Ein zwischen den Kommunikationspartnern platzierter, generischer Proxy soll dabei diesem Optimierungsanspruch gerecht werden. Das Gesamtkonzept wird in einer prototypischen Umsetzung implementiert und auf seine Tauglichkeit getestet.

Orthologes Clustern auf multipartiten Proteingraphen (Enrico Maier)

Orthologe Proteine sind homologe Proteine unterschiedlicher Organismen, die sich durch eine vertikale Vererbung aus einem Protein des letzten gemeinsamen Vorfahren der betrachteten Organismen entwickelt haben. Obwohl der Grad der Sequenzähnlichkeit zwischen den Orthologen unterschiedlicher Organismen variiert und abhängig von der vergangenen Zeit seit dem Speziationsereignis ist, besitzen viele dieser Proteine die gleichen Funktionen in unterschiedlichen Organismen. In dieser Arbeit wurde eine Methode aus der kombinatorischen Optimierung implementiert, die eine proteomweite Identifizierung orthologer Proteine zwischen multiplen Organismen erlaubt. Mit Hilfe dieser Methode soll ein fundamentales Problem der vergleichenden Proteomik geklärt werden, die Identifizierung von Proteinen unterschiedlicher Organismen, die an denselben biologischen Prozessen beteiligt sind. Weiterhin wird ein Transfer funktionaler Informationen von experimentell charakterisierten Proteinen auf deren Orthologen in nur wenig untersuchten Organismen ermöglicht. Der Vortrag gibt einen Einblick in das Orthologiekonzept, in die Problematik der Orthologenidentifikation und in die Funktionsweise der implementierten Methode. Abschließend werden die Ergebnisse der Untersuchungen hinsichtlich der Eignung der implementierten Methode für die proteomweite Identifikation orthologer Proteine zwischen unterschiedlichen Organismen vorgestellt.

XArch - An Archive Management System for Scientific and Register Data (Heiko Mueller)

Databases on the Web are subject to continuous change. In many cases only the most recent versions of data are preserved. Failure to archive earlier states of the data may, for example, lead to loss of scientific evidence, and the basis of findings may no longer be verifiable. We present XArch, an archive management system for scientific and register data. XArch is based on a nested merge approach that efficiently stores multiple versions of hierarchical data in a compact archive. By merging elements into one data structure, any specific version is retrievable from the archive in a single pass over the data and efficient tracking of object history is possible. XArch allows one to create new archives, merge new versions of data into existing archives, and execute both snapshot and temporal queries using a declarative language. We demonstrate the full functionality of XArch using scientific and demographic reference data.

Probenerfassung und Klassifikation von Massenspektren in der Metabolitanalyse (Georg Basler)

Die Metabolitanalyse ist eine Disziplin der Biologie, welche die Erforschung des Metaboloms – der Stoffwechselprozesse in Organismen – zum Ziel hat. Am Max-Planck-Institut für Molekulare Pflanzenphysiologie in Potsdam werden mit Hilfe von Gas-Chromatographie- und Massenspektrometriegeräten (GC/MS) aus pflanzlichen Proben Massenspektren erzeugt, deren computergestützte Verarbeitung die Identifikation der enthaltenen Metaboliten ermöglicht. Dadurch können Stoffwechselwege auf molekularer Ebene erforscht werden, was auch als vierter bedeutender Beitrag neben den Gebieten des Genoms, Transkriptoms und Proteoms bezeichnet wird (Kopka, Joachim (2005): Current Challenges and Developments in GC-MS based Metabolite Profiling Technology, 313). In der vorliegenden Arbeit wurde ein Software-System („Sample Composer“) entwickelt, welches die Beschreibung pflanzlicher Proben für die Metabolitanalyse ermöglicht, und die erfassten Informationen in ein bestehendes Laboratory Information Management System integriert. Ziel der Arbeit war es, den gesamten Ablauf eines Metabolitanalyse-Experiments, von der Pflanzenaussaat über die Probennahme bis hin zur Analyse der Massenspektren reproduzieren und elektronisch verarbeiten zu können. Die Erfassung von Proben mit dem Sample Composer ermöglicht es, eine Probe und die darin gemessenen Massenspektren mit der Pflanze, von der die Probe entnommen wurde, über eine Datenbankverbindung in Beziehung zu setzen. So können Methoden der Bioinformatik angewandt werden, welche die Korrelationen zwischen dem experimentellen Aufbau und den Messergebnissen untersuchen. Weiterhin wurden Möglichkeiten der Klassifikation von Massenspektren durch Support Vector Machines (SVM) untersucht. Es wurden in-silico-Experimente zur Klassifikation nach Aminosäuren sowie nach verschiedenen Zucker- und Säureklassen durchgeführt. Die Ergebnisse der SVM wurden unter Verwendung verschiedener Kernelfunktionen und Parameter mit denen eines Entscheidungsbaumverfahrens verglichen, und deuten auf eine lineare Trennbarkeit und gute Erfassung der chemischen Eigenschaften durch eine der verwendeten Repräsentationen hin.

Automatic model selection in classification using the Minimum Description Length Principle (Daniel Renz)

The Minimum Description Length (MDL) criterion can be applied to a wide variety of model selection problems. It basically states that the model that best compresses the description length of the data is the one that also best explains the data. In the context of machine learning we will apply it to the probability density estimation problem, in which we have to choose from a set of models (densities) the one that best approximates the true model. We will evaluate the learned densities by doing a classification on several data sets which are widely used in the machine learning community to compare state-of-the-art classifiers such as Support Vector Machines. To do this, we build a simple classifier that uses the probability densities for each class (that we learned from the training data) to classify the test data by assigning each test data point to the class with the highest probability. The data is mapped into some higher dimensional space, which we call \textit{product space}, because every feature (dimension) in this space is a (non-linear) function of one or two features of the original data. In the product space, we do a covariance estimation of the data, thereby assuming that the contours of same probability in the product space are elliptic. Depending on the product functions used, this implies some (non-elliptic) density distribution in the feature space. We use our MDL model selection rule to do a greedy hill-climbing optimization on the family of distributions implied by the product functions. As a starting point for the optimization we take the least-squares estimate which (in the under-determined case) minimizes the norm of the error. The optimization process sparsifies the model, thereby - in the optimal case - getting rid of the parameters that account for overfitting. Our aim in this thesis was to build a \textit{machine} that automatically generates product features and/or selects features as needed to build a reliable density estimator for classification purposes. We discuss problems and obstacles that we found on our way, some of which may be the reason why our classifier cannot compare with established state-of-the-art classifiers.

Auswertung regulärer Ausdrücke in Graphen (Daniel Renz)

Ein zentrales Anliegen der Systembiologie ist die Aufklärung von Stoffwechselwegen. Verschiedene Hochdurchsatz-Techniken zur Spezfikation biochemischer Wechselwirkungen generieren heutzutage sehr große Datenmengen, die in Datenbanken verfügbar gemacht werden. Ziel meiner Diplomarbeit war, eine Indexstruktur zu entwickeln, die insbesondere für metabolische Netzwerke die Beantwortung von Suchanfragen in Form regulärer Pfadausdrücke unterstützt. In diesem Vortrag stelle ich die Ergebnisse der Arbeit vor. Neben der prinzipiellen Vorgehensweise zum Finden regulärer Ausdrücke in gerichteten kantenbeschrifteten Graphen und bestehender Optimierungsansätze wird die k-Minimierung präsentiert -- ein neues heuristisches Verfahren zur Verkleinerung des Ausgangsgraphen. Das anfängliche Ziel der Diplomarbeit, das bestehende DataGuide-Verfahren von Nestorov et al. durch Verwendung der k-Minimierung als Preprocessing auch auf große zyklische Graphen anwenden zu können, konnte nicht erreicht werden. Dafür zeigt sich anhand der ausgewerteten Testanfragen, dass die k-Minimierung bereits selbst gut als Indexstruktur genutzt werden kann.

Methoden zur Erstellung von Term-Hierarchien aus Phänotypendaten (Christoph Boehm)

Eine Ontologie ist nach Staab und Studer eine explizite, formale Spezifikation von gemeinsamen Konzepten einer Domäne. Mit Hilfe von Ontologien können natürlichsprachliche Texte exakter formuliert und deren rechentechnische Verarbeitung erweitert werden. Für biomedizinische Texte existieren bereits organismenspezifische Ontologien. Diese wurden meist von Hand erstellt und besitzen somit eine hohe Qualität. Ist die Menge der betrachteten Konzepte zu groß, ist manuelles Vorgehen nicht durchführbar. Die speziesübergreifende Phänotyp/Genotyp-Datenbank PhenomicDB enthält mehrere Tausend Phänotyp-spezifische Konzepte. Diese Konzepte sollen auf automatischem Wege in (ist-ein)Beziehung zueinander gesetzt werden. Das Ziel der vorliegenden Arbeit ist eine Zusammenstellung und Evaluation der existierenden Methoden zur Term-Hierarchisierung. Es werden erste Ansätze unter Verwendung von Statistik bis zu modernen auf Linguistik und Logik basierende Verfahren betrachtet. In dem Vortrag werden die Klassifikation der Methoden sowie ausgewählte Beispiele besprochen. Des Weiteren werden Experimente mit der Subsumption nach Sanderson und Croft erläutert. Es wird sich herausstellen, dass domänenunabhängige Verfahren unter Verwendung von Statistik über gemeinsame Vorkommen von Termen bereits gute Präzision erreichen können.

Kontextabhängige Tag-Suche basierend auf einer gemeinschaftlichen Tag-Klassifizierung (Heiko Müller )

Innerhalb von Community-Plattformen wie FlickR oder youtube werden die präsentierten Inhalte von den Benutzern durch Tags beschrieben. Eine Tag-Suche ermöglicht das Finden von Inhalten, die durch bestimmte Tags gekennzeichnet sind. Diese Arbeit verfolgt die Annahme, dass von Besuchern gestellte Suchanfragen in einer Beziehung zu dem gerade betrachteten Inhalt stehen, zum Beispiel ein Bild oder ein Blog-Eintrag. Um die Relevanz einzelner Suchergebnisse zu stärken bzw. zu schwächen, wird berechnet wie „verwandt“ die gefundene Webseite mit der Seite ist, aus der die Suchanfrage gestellt wurde. Diese Berechnung baut auf einer gemeinschaftlichen Tag-Klassifizierung auf. Stehen zwischen zwei Webseiten viele Tags durch die Tag-Klassifizierung in einer semantischen Beziehung, dann ist davon auszugehen, dass beide Seiten eine hohe inhaltliche Verwandtschaft besitzen. Die Tag-Klassifizierung wird gemeinschaftlich erreicht. Neue Tag-Begriffe werden im Hintergrund in einem Ontologie-System gespeichert und die Benutzer können die Tag-Begriffe in dem Ontologie-System durch verschiedene vorgegebene Beziehungen miteinander in Verbindung setzen. Das Gesamtkonzept wird in einer prototypischen Umsetzung implementiert und auf seine Tauglichkeit getestet.

Falko R* (Karsten Huetter)

Das fehlerannotierte Lernerkorpus FALKO ist ein Projekt der Korpuslinguistik an der HU Berlin. Das Korpus enthält Texte von fortgeschrittenen Lernern des Deutschen als Fremdsprache. Die linguistische Weiterverarbeitung dieser Datenbasis wirft die null- Annotation als Spezialfall auf, der durch eine angepasste Tokenadressierung gelöst wird. Der Vortrag stellt eine alternative Umsetzung des bestehenden FALKO auf Grundlage eines relationalen Datenbanksystems inklusive einer geeigneten Programmierschnittstelle für JAVA vor.

Implementierung eines Data Warehouses für die Nugg.ad AG (Roman Scherer)

Im Rahmen einer Studienarbeit wurde für die Nugg.ad AG ein Data Warehouse implementiert. Nugg.ad ist ein Anbieter von Behavioral Targeting, der Werbevermarktern die Möglichkeit bietet personalisierte Werbung an die Besucher von Internetportalen auszuliefern. Der Vortrag gibt einen Überblick über Behavioral Targeting und geht auf die Implementierung des Data Warehouse ein.