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 [1]). Second, we consider

approximate solutions and their algorithmic aspects (based on [2] and

[3]).

References:

[1] Silverbush, D., Elberfeld, M., and Sharan, R. (2011).

Optimally orienting physical networks.

Journal of Computational Biology, 18(11):1437–1448.

[2] 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.

[3] 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.