Ph.D Thesis

Ph.D StudentRokhlenko Oleg
SubjectAlgorithms for Labeled Graph Matching with Applications
to Systems Biology
DepartmentDepartment of Computer Science
Supervisor PROF. Ron Pinter
Full Thesis textFull thesis text - English Version


Labeled graphs are being used extensively in computational biology to represent entities, such as biochemical networks and pathways, RNA secondary structures, and phylogentic trees. One of the major challenges is to provide techniques for inexact matching (and the resulting alignment) of such graphs in a way that optimizes some objective function. This function usually measures both the similarity between vertices and between edges of two graphs, as well as the resemblance of their structure.

The inexact graph matching problem is NP-hard, and therefore algorithms that reduce the computational complexity of the matching process by imposing topological restrictions on the graphs are called for. In this case inexact graph matching can be regarded as a constrained combinatorial optimization problem. This thesis analyzes the issues and mechanisms that have to be considered for this purpose, regarding topological restrictions, optimization functions, and similarity measures.

Specifically, we study new optimization techniques for the alignment of labeled trees, present a novel approach that utilizes prior knowledge about the required matching to improve a whole class of optimization algorithms, and apply a particular inexact tree matching problem to the alignment of metabolic pathways as an example of the possibilities that this new tree matching approach offers. In addition, we develop a novel optimization approach for devising functional relations between metabolic genes that can be used also as a similarity measure between enzymes that comprise metabolic pathways.

The described techniques have important applications also in areas other than systems biology.