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

Forschungsseminar SS 06

Arbeitsgruppe Informationsintegration | Arbeitsgruppe Wissensmanagement in der Bioinformatik

Neue Entwicklungen in der Bioinformatik und Informationsintegration

Prof. Felix Naumann und Prof. Ulf Leser
  • wann? Dienstags, 11-13 Uhr
  • wo? RUD25, 4.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.

Themenverwandtes Forschungsseminar der DBIS Gruppe: "Neue Entwicklungen im Datenbankbereich", Mittwochs von 13-15 Uhr in RUD 25, 3.113

Folgende Termine und Vorträge sind bisher vorgesehen:

Datum Thema Vortragende(r)
09.05.06
14:00 Uhr, Humboldt-Kabinett
Identification and testing of diagnostic serum protein profiles in glioblastoma patients Quang Long Nguyen
16.05.06
15-17 Uhr, RUD25, 4.113
Entwurf und Implementierung eines generischen Substring-Index
Diplomarbeit
David Weese
30.05.06 Efficiently Identifying Inclusion Dependencies in RDBMS
Probevortrag für Workshop "Grundlagen von Datenbanken"
und
Filtern von IND Kandidaten mit Hilfe von BLOOM-Filtern
Ergebnisse der Arbeiten als Studentische Mitarbeiterin
Jana Bauckmann und Véronique Tietz
06.06.06 XML Data Cleaning with XClean Melanie Weis
13.06.06 Tree Edit Distance based Schema Matching
Diplomarbeit
Evgeniya Ershova
13.07.06
11 c.t., RUD 25, IV.113
Text Mining to Reproduce Manually Curated Databases: Obesity Gene Map
Diplomarbeit
Martin Schmidt
24.07.06
15 c.t., RUD25 3.113
Berlin - Santiago und zurück Jens Bleiholder
15.08.06, 11 c.t., RUD25 3.113 Ein Compiler für PQL mit zwei Backends
Studienarbeit
und
Visualisierung GRIPP-indexierter Graphen
Studienarbeit
Thomas Trost
und
Johannes Vogt
22.08.06, 11 c.t., RUD25 3.113 Präfix-Bäume als Indexstruktur für String-Attribute in relationalen Datenbanken
Diplomarbeit
und
Validierung von Genomannotationen
Diplomarbeit
Nicky Hochmuth
und
Raphael Bauer
05.09.06, 11 c.t., RUD25 3.113 Auswahl von Graphindexen zur Optimierung von SparQL-Anfragen
Studienarbeit
Christian Rothe

Zusammenfassungen

Identification and testing of diagnostic serum protein profiles in glioblastoma patients (Quang Long Nguyen)

Statistical analysis is the method of choice when multiple data sets are being compared to find correlations, for example between the protein concentration in a biological sample and a disease status. Data mining is the synthesis of statistics, machine learning, information theory, and computing used to discover patterns, trends, and relationships in complex data sets. Here we investigated the applicability of data mining to find diagnostic serum protein patterns in astrocytoma and compared the results with those obtained by statistical methods. We analysed the serum concentrations of 7 candidate proteins. Data mining methods were applied to determine protein profiles associated with the presence of a high grade astrocytoma and with survival in 28 patients. Hypothetical serum protein profiles were developed by data mining that allow correct assignment into the astrocytoma group in 92% of all cases, with 3 false positive and no false negative case. The same analysis was performed using logistic regression statistics. The diagnostic values of the derived protein patterns were compared and validated by bootstrap tests. When compared with data mining results, statistical analysis defined protein profiles with less predictive value and decreased stability. In conclusion, data mining is preferable over statistics as a first screening of associations of multiple variables even in small cohorts. The method revealed hypothetical serum protein profiles for astrocytoma patients that associate with diagnosis and survival time.

Efficiently Identifying Inclusion Dependencies in RDBMS (Jana Bauckmann)

In large integration projects one is often confronted with poorly documented databases. One possibility to gather information on database schemas is to search for inclusion depen- dencies (IND). These provide a solid basis for deducing foreign key constraints\u2014as they are pre-condition for potential (semantically valid but missing) foreign key constraints.

In this paper we present and compare several algorithms to identify unary INDs. The obvious way is to utilize an appropriate SQL statement on each potential IND to test its sat- isfiedness. We show that this approach is not efficient enough for large databases. Therefore, we developed database-external approaches that are up to several magnitudes faster than a SQL based approach. We tested our algorithms on databases of up to 3 GB with about 1200 attributes, which can be analyzed by our software in approximately 25 minutes.

XML Data Cleaning with XClean (Melanie Weis)

Data cleaning is the process of correcting anomalies in a data source, that may for instance be due to typographical errors or duplicate representations of an entity. It is a crucial task in customer relationship management, data mining, and data integration. With the growing popularity of XML, approaches to effectively and efficiently clean XML data are needed. We present XClean, a data cleaning system that is specifically geared towards cleaning XML data. The talk will cover a system overview, XClean foundations like data model and operators, and the XClean specification programming language.

Tree Edit Distance based Schema Matching (Evgeniya Ershova)

Schema matching is the task of finding semantic correspondences between elements of two schemas. It is an important point in many application domains dealing with data, such as data integration, e-commerce, data warehousing, etc. There have been a lot of research in this field and there exist a lot of matching systems based on different approaches. In line with this diploma thesis we consider the matching between XML Schemas based on tree edit distance. Tree edit distance is the extension of edit distance with the operations on strings to operations on trees. The goal is to find those operations to transform one tree into another, so that the cost is minimal. In the seminar we will introduce two different algorithms of tree edit distance, make an overview of our system and evaluate it on the basis of different tests.

Text Mining to Reproduce Manually Curated Databases: Obesity Gene Map (Martin Schmidt)

Viele hochwertige Datenbanken in der Biologie und Medizin werden mit Hilfe aufwendiger Literaturrecherchen manuell kuriert. So die "Obesity Gene Map", die Daten zu mit Adipositas (Fettleibigkeit) assoziierten Genen sammelt. In dieser Datenbank befinden sich derzeit ca. 400 Gene, wobei diese Liste sicherlich nicht vollständig ist. In der Diplomarbeit beschäftigen wir uns damit, in einer großen Menge von Dokumenten auto- matisch weitere "heiße" Kandidaten für weitere Gene zu finden. Solche Kandidaten sind vielleicht bisher nur am Rande in der Literatur diskutiert wurden, hochspekulativ, oder wurden nicht unmittelbar als ursächlich für krankhafte Fettleibigkeit erkannt -- deshalb wurden sie nicht in die Obesity Gene Map übernommen oder schlicht übersehen. Wir finden, dass wir mit Methoden des Textmining' ca. 88% der OGM auto- matisch reproduzieren können. Auf einem Testdatensatz erreicht das Verfahren eine Präzision von über 95% bei vergleichbar hohem Recall. Wir finden sehr viele neue Kandidaten, die wir nun vorsortieren und abschließen bewerten müssen.

Ein Compiler für PQL mit zwei Backends (Thomas Trost)

Diese Studienarbeit setzt sich mit der Thematik Implementation eines Compilers für die "Pathway Query Language (PQL)", auseinander, welche am Lehrstuhl "Wissensmanagement in der Bioinformatik" entwickelt wurde. Das Ziel dieser Arbeit war es, einen Compiler mit zwei Backends für PQL zu entwicklen. Es sollte auch zusätzlich darauf geachtet werden, dass sich der Compiler leicht erweitern lässt. Ein Backend sollte PL/SQL Code für ein Oracle Datenbankmanagementsystem (DBMS) liefern, das zweite Backend sollte ein Interpreter sein. Das heißt, es sollte ohne Datenbankmanagementsystem die PQL Queries berechnen. Dabei wurde zuerst die Grammatik von PQL formal aufgestellt und anschließend ein Compilerbauwerkzeug gewählt. Die Wahl fiel auf SableCC und anschließend wurde der Compiler mit den zwei Backends unter der Hilfenahme von SableCC implementiert. Bei der Implementation wurde festgestellt, dass man nicht ganz ohne DBMS auskommt. Somit kommt nun ein für den Benutzer völlig transparentes DBMS zum Einsatz.

Visualisierung GRIPP-indexierter Graphen (Johannes Vogt)

GRIPP ist eine Indexierungsmethode für gerichtete Graphen, die schnelle und speicherplatzeffiziente Anfragen auf diesen Graphen ermöglicht. GRIPP beruht auf einer Umformung von Graphen zu Bäumen, wobei ein Teil der Baumknoten als Verweise auf andere Knoten dienen, und somit Zyklen und andere Nichtbaumstrukturen auf Baumstrukturen abgebildet werden können.

GRIPP-Viewer ist ein Tool, das GRIPP-indizierte Graphen (/Indexbäume/) visualisiert, und Erreichbarkeitsanfragen auf diese indizierten Graphen ausführt und visuell nachvollziehbar macht.

Präfix-Bäume als Indexstruktur für String-Attribute in relationalen Datenbanken (Nicky Hochmuth)

Ziel der Arbeit war die Implementierung und Evaluation von Präfix- Bäumen als Indexstruktur für String-Attribute in einem bestehenden relationalen Datenbankmanagementsystem (Oracle). Es wurde untersucht, inwieweit ein auf Präfixen gebauter Index relationale Operationen (Selektion, Verbund, Schnitt und Differenz) unterstützen kann und ob es möglich ist, die Selektion über String-Attribute einer Relation unabhängig von der Relationengröße praktikabel zu realisieren. Messungen am Beispiel einer EST-Datenbank und Text-Kopora zeigten auf, wann das Einsparen von Zeichenvergleichen durch einen Präfix-Index gegenüber konventionellen Methodiken die Abarbeitung von Datenbankanfragen beschleunigen kann.

Validierung von Genomannotationen (Raphael Bauer)

Das Wissen, das in Genomdatenbanken gespeichert ist unterliegt einer ständigen Veränderung bzw. Verbesserung. Die DNA Sequenz wird weiter aufgeklärt, neue Annotationen wie SNPs, Exons und Introns werden identifiziert, Krankheiten bestimmten Bereichen auf dem Genom zugeordnet.
Arbeiten Wissenschaftler mit diesen Daten, die externen Genomdatenbanken entnommen wurden, passiert es häufig, dass dieses entnommene Wissen gegenüber dem Wissen in externen Genomdatenbanken veraltet oder inkorrekt wird.
In dieser Diplomarbeit wurden in Zusammenarbeit mit Wissenschaftlern Prüffälle aufgestellt. Diese können Inkonsistenzen zwischen externen Genomdatenbanken und früher entnommenen Daten, und damit veraltetes und inkorrektes Wissen, erkennen. Für die Prüffälle wurde ein Framework entwickelt, das in der Lage ist mit den Herausforderungen der Domäne umzugehen.

Auswahl von Graphindexen zur Optimierung von SparQL-Anfragen (Christian Rothe)

Die Arbeit beschäftigt sich mit der Frage, inwiefern bestehende Graphindexe auf einer RDF-Datenmenge zur Optimierung der Bearbeitung einer SparQL-Anfrage verwendet werden können. Es wurden verschiedene Indexe untersucht und mit diesen das Anfragemuster überdeckt. Mit Hilfe statischer Charakteristiken der Indexe wurde die Selektivität der Überdeckungen abgeschätzt und schließlich eine geeignete Überdeckung ausgewählt, die den Kern einer weiterführenden Anfragebearbeitung bildet. Eine prototypische Implementation der entwickelten Algorithmen fand mittels Jena und Java statt.

Kontakt: Jana Bauckmann; bauckmann(at)informatik.hu-berlin.de