The Balavatnik School of Computer Science, Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel.
Bioinformatics. 2014 May 15;30(10):1449-55. doi: 10.1093/bioinformatics/btu043. Epub 2014 Jan 27.
The graph orientation problem calls for orienting the edges of a graph so as to maximize the number of pre-specified source-target vertex pairs that admit a directed path from the source to the target. Most algorithmic approaches to this problem share a common preprocessing step, in which the input graph is reduced to a tree by repeatedly contracting its cycles. Although this reduction is valid from an algorithmic perspective, the assignment of directions to the edges of the contracted cycles becomes arbitrary, and the connecting source-target paths may be arbitrarily long. In the context of biological networks, the connection of vertex pairs via shortest paths is highly motivated, leading to the following problem variant: given a graph and a collection of source-target vertex pairs, assign directions to the edges so as to maximize the number of pairs that are connected by a shortest (in the original graph) directed path. This problem is NP-complete and hard to approximate to within sub-polynomial factors. Here we provide a first polynomial-size integer linear program formulation for this problem, which allows its exact solution in seconds on current networks. We apply our algorithm to orient protein-protein interaction networks in yeast and compare it with two state-of-the-art algorithms. We find that our algorithm outperforms previous approaches and can orient considerable parts of the network, thus revealing its structure and function.
The source code is available at www.cs.tau.ac.il/∼roded/shortest.zip.
图定向问题要求对图的边进行定向，以便最大化允许从源到目标的有向路径的预指定源-目标顶点对的数量。大多数解决此问题的算法方法都有一个共同的预处理步骤，其中通过反复收缩其循环来将输入图简化为树。尽管从算法角度来看这种简化是有效的，但收缩循环的边的方向分配变得任意，并且连接源-目标的路径可能任意长。在生物网络的上下文中，通过最短路径连接顶点对是高度激励的，从而导致以下问题变体：给定一个图和一组源-目标顶点对，分配边的方向，以便最大化通过最短（在原始图中）有向路径连接的对的数量。这个问题是 NP 完全的，很难在次多项式因子内逼近。在这里，我们为这个问题提供了第一个多项式大小的整数线性规划公式，它允许在当前网络上在几秒钟内精确求解。我们将我们的算法应用于酵母中的蛋白质-蛋白质相互作用网络，并将其与两种最先进的算法进行比较。我们发现我们的算法优于以前的方法，可以定向网络的相当一部分，从而揭示其结构和功能。
源代码可在 www.cs.tau.ac.il/∼roded/shortest.zip 获得。
