Vergleich von Algorithmen zur Fragmentsuche in Moleküldatenbanken (gSPan/Gaston)

Student:Marc Wörlein
Title:Vergleich von Algorithmen zur Fragmentsuche in Moleküldatenbanken (gSPan/Gaston)
Type:study thesis
Advisors:Meinl, T.; Fischer, I.; Philippsen, M.
State:submitted on June 8, 2005
Prerequisits:

Studierende, die in dieser Arbeitsguppe mitwirken möchten, sollten Spaß am Programmieren haben und gute Javakenntnisse besitzen.

Topic:

Hintergrund
Die Arbeitsgruppe ParMol wurde im März 2004 gegründet. In ihrem Rahmen sollen neue Verfahren entwickelt werden, um in großen Datenbanken interessante Zusammenhänge zwischen chemischen Strukturen zu finden. Diese Zusammenhänge sollen als Molekülfragmente, d.h. in Form von Zusammenhangsgraphen dargestellt werden. Ein Anwendungsgebiet ist z.B. die in vitro Vorhersage von toxischen Seiteneffekten von Medikamentenkandidaten schon vor in vivo oder klinischen Tests. Im Gegensatz zu bisher bekannten Verfahren sollen auch ähnliche Strukturen gefunden werden, die biologisch oder chemisch die gleiche Wirkung zeigen. Um den dadurch entstehenden, deutlich höheren Rechenbedarf zu decken, werden die entwickelten Verfahren parallelisiert und so entworfen, dass sie sich auch für die Bearbeitung auf verteilten Ressourcen eignen.
In Zusammenarbeit mit dem Lehrstuhl für Bioinfomatik und Maschinelles Lernen der Universität in Konstanz soll in den nächsten Jahren eine Reihe von neuen Verfahren und Methoden auf diesem Gebiet entwickelt werden.

Aufgabe
In den letzten Jahren sind eine Reihe von Algorithmen vorgestellt worden, die häufige Subgraphen in Graphdatenbanken suchen und finden. Ein Anwendungsgebiet ist die bereits erwähnte Suche nach häufigen Fragmenten in Moleküldatenbaken. Was bei der Vielzahl der Algorithmen noch aussteht ist ein ausführlicher Vergleich untereinander unter den selben Vorraussetzungen:

  • identische Hardware
  • gleiche Datensätze
  • gleiche Programmiersprache
  • Verwendung einer gemeinsamen Bibliothek von Graphalgorithmen und -implementierungen Untersucht werden soll neben der reinen Laufzeit auch der Speicherbedarf, die Anzahl der erzeugten und gefundenen Fragmente sowie die evtl. vorhandene Abhängigkeit von den verwendeten Datensätzen.

Abschließend sollte noch kurz andiskutiert werden, inwiefern sich die sequentiellen Verfahren parallelisieren lassen und welche Probleme dabei auftreten können.
Aus der Vielzahl der Algorithmen sind Gaston und gSpan zu implementieren. Der anschließende Vergleich der Algorithmen soll zusammen mit dem Bearbeiter der zweiten Studienarbeit zu diesem Thema gemeinsam durchgeführt werden.

watermark seal