Anschlussprojekte | Sonderprojekte

Förderbeginn 01.07.2003

Effiziente Molekülfragmentsuche durch Rechnerbündeleinsatz

Prof. Dr. Michael Philippsen
Friedrich-Alexander-Universität Erlangen-Nürnberg
Lehrstuhl für Informatik 2 (Programmiersysteme)

Dr. Michael Berthold
Tripos Data Analysis Research Lab
Standard


Die Datenanalyseabteilung der Tripos Inc. in San Francisco entwickelt Algorithmen zur Analyse von Molekülsammlungen mit dem Ziel Gemeinsamkeiten zwischen Molekülen bestimmter Klassen zu finden. Eines der Hauptprobleme ist dabei die sehr große Zahl zu untersuchender Moleküle. In diesem Projekt erwarten wir signifikante Fortschritte durch den Einsatz neuer paralleler Molekül-Mining-Algorithmen auf Rechnerbündeln. Für das Molekül-Mining werden parallele Algorithmen aus dem Bereich der Warenkorbanalyse und zur Analyse häufig auftretender Teilgraphen als Ausgangspunkte verwendet. Die am Lehrstuhl für Informatik 2 der Universität Erlangen entwickelte Programmierumgebung JavaParty wird verwendet, an der Anwendung validiert und weiter entwickelt. Um minimale Objektzugriffszeiten auf Architekturen mit nicht-uniformer Speicherhierarchie zu erzielen, wird JavaParty um Abstraktion zur Objektplatzierung und um Optimierungstechniken zur dynamischen Verbesserung der Lokalität erweitert. Darüber hinaus werden problemspezifische Programmierbibliotheken für das Molekül-Mining entwickelt.

Abschlussbericht
In der Laufzeit vom 1.7.2003 bis zum 31.12.2005 wurde das Projekt von BaCaTeC finanziell gefördert. Die Fördermittel wurden im Wesentlichen für Reisen verwendet. Neben diversen Arbeitstreffen von Projektbeteiligten der Kalifornischen, der Konstanzer und der Erlanger Gruppe wurden internationale Reisen zu Workshops und Konferenzen finanziert, auf denen die eigenen Ergebnisse vorgestellt worden sind. Dieser intensive Gedankenaustausch hatte erheblichen Anteil am Gelingen des Projekts. Im Einzelnen konnten folgende Ergebnisse erzielt werden:

  • 11 Publikationen, darunter 7 international sichtbare Workshop- oder Konferenzbeiträge (einmal best student paper award) und 2 Sammelbände zu Tagungen, an deren Organisation Projektbeteiligte maßgeblich mitgewirkt haben.
    • Berthold, Michael R.; Glen, Robert; Diederichs, Kay; Kohlbacher, Oliver; Fischer, Ingrid (Hrsg.): Computational Life Sciences, First International Symposium on Computational Life Sciences, CompLife 2005, Konstanz. Lecture Notes in Bioinformatics Bd. 3695, Springer Verlag, 2005.
    • Wörlein, Marc; Meinl, Thorsten; Fischer, Ingrid; Philippsen, Michael: A quantitative comparison of the subgraph miners MoFa, gSpan, FFSM, and Gaston, PKDD 2005, In Proceedings of the 9th European Conference on Principles and Practices of Knowledge Discovery in Databases, pp. 392-403, Porto, Portugal, 3.10.-7.10.2005.
    • Borgelt, Christian; Meinl, Thorsten; Berthold, Michael R.: MoSS: A Program for Molecular Substructure Mining, In Proceedings of OSDM 2005, Open Source Data Mining Workshop on Frequent Pattern Mining Implementations, pp. 1-15, Chicago, IL, USA, 21.8.2005.
    • Meinl, Thorsten; Fischer, Ingrid; Philippsen, Michael: Parallel Mining for Frequent Fragments on a Shared-Memory Multiprocessor - Results and Java-Obstacles -, LWA 2005, Beiträge zur GI-Workshopwoche Lernen, Wissensentdeckung, Adaptivität (Workshop der GI-Fachgruppe "Maschinelles Lernen, Wissensentdeckung, Data Mining, FGML", pp. 196-201, Saarbrücken, 10.10.-12.10.2005.
    • Nijssen, Siegfried; Meinl, Thorsten; Karypis, George (Hrsg.): Proceedings of MGTS 2005, 3rd International Workshop on Mining Graphs, Trees and Sequences, Porto, Portugal, 2005.
    • Meinl, Thorsten; Fischer, Ingrid: Subgraph Mining. In Encyclopedia of Data Warehousing and Mining, pp. 1059-1063, 2005.
    • Borgelt, Christian; Meinl, Thorsten; Berthold, Michael R.: Advanced Pruning Strategies to Speed Up Mining Closed Molecular Fragments, In Proceedings of the IEEE SMC 2004 Conference on Systems, Man & Cybernetics, pp. 4565-4570, Den Haag, The Netherlands, 10.10.-13.10.2004.
    • Meinl, Thorsten; Borgelt, Christian; Berthold, Michael R.: Discriminative Closed Fragment Mining and Pefect Extensions in MoFa. In Proceedings of STAIRS 2004, Second Starting AI Researchers' Symposium, pp. 3-14, Valencia, Spain, 22.8.-23.8.2005.
    • Fischer, Ingrid; Meinl, Thorsten: Graph Based Molecular Data Mining - An Overview. In Proceedings of the IEEE SMC 2004 Conference on Systems, Man & Cybernetics, pp. 4578-4582, Den Haag, The Netherlands, 10.10.-13.10.2004.
    • Meinl, Thorsten; Berthold, Michael R.: Hybrid Fragment Mining with MoFa and FSG. In Proceedings of the IEEE SMC 2004 Conference on Systems, Man & Cybernetics, pp. 4559-4564, Den Haag, The Netherlands, 10.10.-13.10.2004. Best student paper award.
    • Meinl, Thorsten; Borgelt, Christian; Berthold, Michael R.: Mining fragments with fuzzy chains in molecular databases. In Proceedings of the Workshop W7 on Mining Graphs, Trees and Sequences (MGTS '04) der PKDD 2004, 8th European Conference on Principles and Practices of Knowledge Discovery in Databases, pp. 49-60, Pisa, Italy, 20.9.-24.9.2004.
  • 5 betreute Studien-/Diplomarbeiten, davon eine, die in Kalifornien durchgefƒuhrt wurde:
    • Thorsten Meinl, Erweiterte Fragmentsuche in Moleküldatenbanken
    • Marc Wörlein, Vergleich von Algorithmen zur Fragmentsuche in Moleküldatenbanken, Teil 1
    • Monic Klöden, Vergleich von Algorithmen zur Fragmentsuche in Moleküldatenbanken, Teil 2
    • Olga Urzova, Zweidimensionale Visualisierung von Molekülgraphen in Java
    • Marc Wörlein, Erweiterung und Parallelisierung eines Graph-Mining-Algorithmus (noch in Bearbeitung)
  • Der erstellte Quellcode ist auf den Web-Seiten des Lehrstuhls veröffentlicht.
  • Es wurden 2 Anträge auf Sachbeihilfen bei der DFG gestellt.
Wir danken BaCaTeC für die Anschubfinanzierung, ohne die dieses spannende Thema, das die beteiligten Lehrstühle auch in Zukunft beschäftigen wird, nicht hätte aufgegriffen werden können.