Practical Research Projects - Project Description

Project Description

This is a description of a Practical Research Project associated with the PREP course

Project Title

Comparing small molecular graphs

Quarter

Q1 2010

Responsible

Thomas G. Kristensen.

Second level advisor: Christian N. S. Pedersen.

Aims

Chemical structures can be looked upon as small graphs where nodes are labelled with their atom type. It is generally expected that topologically similar molecules will also have similar chemical properties, and it is therefore interesting to compare these small labelled graphs. However, comparing two graphs with cycles to find out how similar they are can be computationally expensive and previous research in the field has therefore often been based on reducing the graphs to trees and to compare these trees instead. This process will of course loose some information, and might result in a worse result. The aim of this study is to examine algorithms for comparing small graphs containing cycles. The nodes of the graphs can be labelled in different ways, which puts restrictions on which nodes can be matched and makes the problem a bit harder to solve. Generally, matching graphs is NP hard, but the graphs are small and it might not be a problem in practice. Alternatively, there might be heuristics for accelerating the comparison of these graphs. It would be very interesting to shed some light on this.

Learning Outcome

The student should be able to discuss existing methods for comparing molecular graphs when reduced to trees and to explain the differences between these methods.
The student should have implemented and tested a working implementation of a program for comparing molecular graphs using both the naive approach and some kind of heuristic.
The student must prove the ability to evaluate these two methods empirically on real data. To present and discuss the results, and to draw conclusions about the methods usability on real data, when compared to previous studies.

Requirements

The student should have completed "Algorithms and Data structures" and have some experience in implementing algorithms.