Department of Biomedical Engineering, Eindhoven University of Technology, Eindhoven, The Netherlands.
BMC Bioinformatics. 2012 Oct 30;13:281. doi: 10.1186/1471-2105-13-281.
Techniques for reconstruction of biological networks which are based on perturbation experiments often predict direct interactions between nodes that do not exist. Transitive reduction removes such relations if they can be explained by an indirect path of influences. The existing algorithms for transitive reduction are sequential and might suffer from too long run times for large networks. They also exhibit the anomaly that some existing direct interactions are also removed.
We develop efficient scalable parallel algorithms for transitive reduction on general purpose graphics processing units for both standard (unweighted) and weighted graphs. Edge weights are regarded as uncertainties of interactions. A direct interaction is removed only if there exists an indirect interaction path between the same nodes which is strictly more certain than the direct one. This is a refinement of the removal condition for the unweighted graphs and avoids to a great extent the erroneous elimination of direct edges.
Parallel implementations of these algorithms can achieve speed-ups of two orders of magnitude compared to their sequential counterparts. Our experiments show that: i) taking into account the edge weights improves the reconstruction quality compared to the unweighted case; ii) it is advantageous not to distinguish between positive and negative interactions since this lowers the complexity of the algorithms from NP-complete to polynomial without loss of quality.
基于扰动实验的生物网络重建技术经常预测不存在的节点之间的直接相互作用。传递性约简会在间接影响路径可以解释这些关系时删除这些关系。现有的传递性约简算法是顺序的，对于大型网络可能运行时间过长。它们还表现出一些现有的直接相互作用也被删除的异常现象。
我们为标准（无权重）和加权图在通用图形处理单元上开发了用于传递性约简的高效可扩展并行算法。边权重被视为相互作用的不确定性。只有当同一节点之间存在间接相互作用路径且比直接相互作用路径更确定时，才会删除直接相互作用。这是对无权重图的删除条件的改进，在很大程度上避免了直接边的错误消除。
与顺序算法相比，这些算法的并行实现可以实现两个数量级的加速。我们的实验表明：i）考虑边权重可以提高重建质量与无权重情况相比；ii）不区分正相互作用和负相互作用是有利的，因为这会降低算法的复杂性，使其从 NP 完全问题变为多项式问题，而不会降低质量。
