Technical Report PHD-2007-16

Title: Algorithms for Labeled Graph Matching with Applications to Systems Biology
Authors: Oleg Rokhlenko
Supervisors: Ron Pinter
Abstract: 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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2007
To the main CS technical reports page

Computer science department, Technion