Graphs, algorithms and bioinformatics
Finding matching subgraphs in a pair of graphs (the subgraph isomorphism problem) is a classical problem in graph theory and theoretical computer science, and a problem that has practical applications. For example, in chemistry it can be useful to represent the structure of compounds as a graph of bonded atoms, and to use graph matching methods to find similarities in a set of compounds (the field of chemistry where this is used is called "chemoinformatics"). The main motivation for proposing this project comes from "bioinformatics", where we have devised a new way to represent protein surfaces as graphs, and we now want to build tools to reason with this representation, for example to find similar surface patches on different proteins that might share a common biological function.
The project proposed here aims to devise graph matching methods to find similarities on the surfaces of large biological molecules.
There are two main parts in this project: an algorithmic part and a visualisation part. The algorithmic part will involve devising and implementing a heuristic algorithm to compute the largest matchings between isomorphic subgraphs of two graphs. Subgraph isomorphism is known to be a hard problem in general, but we suspect that the graphs in our application have helpful structure that could even make it very easy. The visualisation part will involve devising and implementing a tool for viewing and interacting with a graphical representation of the matching subgraphs in 2D and/or 3D.
Målgrupp D, IT
Peter Damaschke and Graham Kemp
Institution Data- och informationsteknik
Uppdaterad: 18 oktober 2011