Technical Report CS-2013-01

Title: Partial Information Network Queries
Authors: Ron Y. Pinter and Meirav Zehavi
Abstract: We present a new pattern matching problem, the partial information query problem, which includes as special cases two problems that have important applications to bioinformatics: the alignment query problem and the weighted topology-free query problem. In both problems we have a pattern $P$ and a graph $H$, and we need to find a subgraph of $H$ that resembles $P$. An alignment query requires knowing the topology of $P$, while a weighted topology-free query ignores it. We provide a solution to users that have partial information regarding the topology of $P$. We present a fixed-parameter algorithm for this problem when $P$ is a set of trees, and improve the best known time complexities of the alignment query problem when $P$ is a path, of the alignment query problem when $P$ is a tree and of the weighted topology-free query problem.
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 or PS files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2013
To the main CS technical reports page

Computer science department, Technion