Der 29-jährige David Blumenthal hat auf dem Kongress „Graph-based Representations in Pattern Recognition“ für sein Paper zu Graph Edit Distance den Best Paper Award zugesprochen erhalten.

David Blumenthal hat an der TU Berlin seinen Master in Mathematik abgelegt, bevor er nach Bozen gezogen ist, um an der Fakultät für Informatik sein Doktoratsstudium zu beginnen. Voraussichtlich im Frühjahr 2019 will der von Prof. Johann Gamper betreute Doktorand dieses beenden. „Exact computation of graph edit distance for uniform and non-uniform metric edit costs“ lautet der Titel seines ausgezeichneten Papers, das er auf dem internationalen Kongress in diesem Frühjahr auf Capri eingereicht hat; vorgestellt wurden auf der Konferenz 25 Papers. Blumenthals Thema wurde inzwischen bereits bei Springer publiziert.

Um was dreht sich Ihr Paper genau?
Vereinfacht ausgedrückt verbessere ich exakte Algorithmen für die Berechnung der Graph Edit Distance. Die Graph Edit Distance ist ein Distanzbegriff, mit welchem kombinatorische Graphen miteinander verglichen werden. Kombinatorische Graphen modellieren zum Beispiel Straßennetzwerke oder Moleküle. Viele erinnern sich noch an die Darstellung von Molekülen im Chemieunterricht. Dabei bilden die chemischen Elementen die Knoten des kombinatorischen Graphen und die Bindungen zwischen den Elementen dessen Kanten. Ein relativ weit verbreiteter Begriff, um solcherart als Graphen modellierte Moleküle miteinander zu vergleichen, ist die Graph Edit Distance.

Können Sie diese im Detail erläutern?
Es handelt sich um ein engmaschiges Distanzmaß, das eingesetzt wird, um relativ kleine Graphen auf feine Unterschiede hin zu untersuchen. Der Nachteil liegt darin, dass es generell sehr schwierig ist, diese Unterschiede zu berechnen, da man selbst mit den leistungsstärksten Computern noch zu lange benötigt. Mein Paper beschreibt eine Möglichkeit der Beschleunigung, die aufbauend auf bestehende Algorithmen die Berechnungen wesentlich verbessert.

Als Laie fragt man sich, wie lange eine solche Berechnung dauert.
Die exakte Berechnung der Graph Edit Distance dauert in der Tat für einige Anwendungen zu lange. Auch aus diesem Grund arbeite ich im Rahmen meiner Doktorarbeit derzeit an schnelleren Aproximationstechniken. Für deren Evaluation musste ich die Graph Edit Distance jedoch auch exakt berechnen, weshalb ich verschiedene bereits existierende Algorithmen implementiert habe. Dabei kamen mir Ideen, um zwei dieser Algorithmen zu verbessern. Mein Paper ist also sozusagen ein Nebenprodukt einer größeren Forschungsarbeit.

Können Sie noch einige Beispiele nennen, bei denen ihre Algorithmen künftig angewandt werden?
Hautpanwendung ist sicher die Ähnlichkeitssuche in Graphendatenbanken. Man denke zum Beispiel an einen Wirkstoff bei einem Medikament, bei dem sich Resistenzen gebildet haben. Für die Pharmaindustrie bedeutet dies, dass sie ein neues Medikament entwickeln muss. Dazu bietet es sich an, nach einem Wirkstoff Ausschau zu halten, dessen chemische Struktur der des alten Wirkstoffs ähnelt. Es liegt daher aus mathematischer Sicht nahe, zunächst die Struktur des alten und möglicher neuer Wirkstoffe als Graphen zu modellieren und unter Verwendung der Graph Edit Distance nach Kandidaten für einen neuen Wirkstoff zu suchen, bevor die Pharmaindustrie die nächsten Schritte der klinischen Tests beschreitet. Durch meine Algorithmen wird es künftig möglich sein, den ersten Schritt der Kandidatengenerierung deutlich schneller durchzuführen.

Related Articles

Article
Dalla California alla Val di Fassa per documentare il ladino

Un gruppo di studenti della University of Southern California, seguiti dal ricercatore Alessandro Vietti, sta applicando innovativi strumenti computazionali allo studio delle lingue minoritarie e in via di estinzione.

Interview
Was darf Forschung mit Social Media Daten?

Wer Daten aus sozialen Medien verwenden darf und für welchen Zweck, wird heftig debattiert, seit die Beratungsfirma Cambridge Analytica mithilfe von Facebook-Daten versucht hat, die Wahlentscheidung von Millionen Amerikanern zu manipulieren. Wissenschaftler jedoch nutzen soziale Netzwerke schon lange als Datenquelle. Auch der Computerlinguist Egon Stemle und der Ökosystemforscher Lukas Egarter Vigl von Eurac Research. Ein Gespräch über Möglichkeiten und Methoden solcher Forschung – und über die ethische Verantwortung des Forschers.

Article
Südtirols Nachwuchsforscher erfolgreich

Mit einem Astronomie- und einem Robotikprojekt überzeugten die Südtiroler Nachwuchsforscher die Jury des Wettbewerbs, an dem Schüler aus Südtirol, dem Trentino, Tirol und Graubünden beteiligt waren. Das Finale fand am 19. und 20. April an der Universität Innsbruck statt. Platz eins in der Kategorie „Forschung“ belegten Schüler des Realgymnasiums Bruneck für die Entdeckung einer bisher nicht bekannten Eigenschaft eines Sterns. Der zweite Platz in der Kategorie „Produktentwicklung“ ging an eine fünfköpfige Schülergruppe vom wissenschaftlichen Gymnasium Rainerum für die Entwicklung des Roboters HAIDI. Die Sieger freuen sich über Geldpreise bis zu 3.000 Euro, zur Verfügung gestellt von der Stiftung Südtiroler Sparkasse.

Article
Infos im Internet: Was ist wichtig, was ist richtig?

Das Internet sammelt das Wissen der Welt, Informationen stehen in Überfülle bereit. Nur: Bekommen wir im Netz auch die richtigen Antworten auf unsere Fragen, enthalten sie alle relevanten Informationen? Dieses Problems nimmt sich die Fakultät für Informatik der Freien Universität Bozen an und hat auch schon interessante Lösungswege gefunden.