Thursday, October 9, 2014
Speaker: Michael Elberfeld
Venue: IST Austria
In the network orientation problem one is given a mixed graph,
consisting of directed and undirected edges, and a set of
source-target vertex pairs. The goal is to orient the undirected edges
so that a maximum number of pairs admit a directed path from the
source to the target. This NP-complete problem arises in the context
of analyzing physical networks of protein-protein and protein-DNA
interactions. While the latter are naturally directed from a
transcription factor to a gene, the direction of signal flow in
protein-protein interactions is often unknown or cannot be measured en
masse. One then tries to infer this information by using causality
data on pairs of genes such that the perturbation of one gene changes
the expression level of the other gene.
After introducing physical networks of protein interactions and the
related orientation problem, the talk reports on two studies related
to its solution: First, we have a look at optimal solutions to the
problem that are based on an integer linear programming formulation;
this formulation is applied to orient protein-protein interactions in
yeast (this part of the talk is based on ). Second, we consider
approximate solutions and their algorithmic aspects (based on  and
 Silverbush, D., Elberfeld, M., and Sharan, R. (2011).
Optimally orienting physical networks.
Journal of Computational Biology, 18(11):1437–1448.
 Elberfeld, M., Bafna, V., Gamzu, I., Medvedovsky, A., Segev, D.,
Silverbush, D., Zwick, U., and Sharan, R. (2011).
On the approximability of reachability-preserving network orientations.
Internet Mathematics, 7(4):209-232.
 Elberfeld, M., Segev, D., Davidson, C. R., Silverbush, D., and Sharan, R. (2013).
Approximation algorithms for orienting mixed graphs.
Theoretical Computer Science, 483:96-103.