Technical Report CS-2012-12

Title: Algorithms for Topology-Free and Alignment Queries
Authors: Ron Y. Pinter and Meirav Zehavi
Abstract: In this article we address two pattern matching problems which have important applications to bioinformatics. First we address the topology-free query problem: Given a set of labels $L$, a multiset $P$ of labels from $L$, a graph $H=(V_H,E_H)$ and a function $Label_H : V_H \rightarrow 2^L$, we need to find a subtree $S$ of $H$ which is an occurrence of $P$. We provide a fixed-parameter algorithm with parameter $k=|P|$ whose time complexity is $O^*(2^k)$ and whose space complexity is polynomial. We also consider three variations of this problem. Then we address the alignment query problem: Given two labeled graphs $P$ and $H$, we need to find a subgraph $S$ of $H$ whose alignment with $P$ is the best among all such subgraphs. We present two algorithms where $P$ and $H$ belong to certain families of DAGs whose time complexities are polynomial and are less restrictive than algorithms that are available today for alignment queries. Topology-free and alignment queries provide means to study the function and evolution of biological networks, and today, with the increasing amount of knowledge regarding biological networks, they are extremely relevant.
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 CS technical reports of 2012
To the main CS technical reports page

Computer science department, Technion