IBM Israel Research Seminars

The analysis of pathways (metabolic, regulatory, biochemical) and protein networks gives rise to many graph recognition problems. Primarily, we are searching for one graph structure within another, allowing certain deviations in topology and looking for the best possible match. The problem is further complicated by allowing similarity - rather than requiring identity - between nodes which are annotated by labels, denoting e.g. proteins.

In fact, the above formulation generalizes the concept of an alignment between sequences to an alignment between pathways. We suggest a formalization that captures the intuitive notion of pathway alignment in terms of Approximate Labeled Subgraph Homeomorphism (ALSH), as follows: Given two directed labeled graphs P and T and a predefined label-to-label similarity score matrix, compute the homeomorphic sub-graph of T which is structurally most similar to P and which also maximizes the overall node-to-node resemblance. We present polynomial-time solutions to the ALSH problem where P and T are trees (both rooted and un-rooted, both ordered and unordered). We embodied these algorithms into MetaPathwayHunter, a tool that given a query pathway and a collection of pathways finds and reports all approximate occurrences of the query in the collection, ranked by similarity and statistical significance.

The program also supports a visualization interface with which the alignment of two homologous pathways can be graphically displayed.

Joint work with Ron Pinter, Michal Ziv-Ukelson, Esti Yeger-Lotem and Dekel Tsur.

About the Speaker
Oleg Rokhlenko is a PhD candidate of Dept. of Computer Science at the Technion. He received his B.A and MSc. in Computer Science, in 2001 and 2003, respectively, both from the Technion. From 1999-2001 he worked as a software engineer in Intel. His research interests include computational biology, bioinformatics, combinatorics, and graph theory.