|
|
 |
| 04-11-2003 |
| |
Department of Software Engineering - Seminar in Computer Science
|
|
| |
The next Seminar in Computer Science will be held on
Tuesday - 4/11/2003 at 12.00 a.m, room M317 .
Speaker: Oleg Rokhlenko,
Department of Computer Science,
Technion – Israel Institute of Technology
Haifa, Israel
Title: Tree based comparison of metabolic pathways.
Abstract:
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. We suggest a formalization that captures the intuitive notion of pathway similarity in terms of Approximate Labelled 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 solutions to the ALSH problem where P and T are trees (both rooted and un-rooted, both ordered and unordered). Their complexity is polynomial, where the degree depends on the type of trees allowed. Moreover, a new similarity measure is presented which utilizes a node-to-node scoring table, based on an empirical protein-to-protein comparison matrix.
Oleg Rokhlenko is graduating MSc in Technion. He has been conducting teaching and research at the Computer Science and the Medicine faculties in Technion. His research interests include bioinformatics, computational biology and optimization theory.
|
|
|
|
|
