Tresch Achim, Beissbarth T, Sültmann H, Kuner R, Poustka A, Buness A
Institute for Medical Biometry, Epidemiology and Informatics, Mainz, Germany.
J Comput Biol. 2007 Nov;14(9):1217-28. doi: 10.1089/cmb.2007.0085.
The matter of concern are algorithms for the discrimination of direct from indirect regulatory effects from an interaction graph built up by error-prone measurements. Many of these algorithms can be cast as a rule for the removal of a single edge of the graph, such that the remaining graph is still consistent with the data. A set of mild conditions is given under which iterated application of such a rule leads to a unique minimal consistent graph. We show that three of the common methods for direct interactions search fulfill these conditions, thus providing a justification of their use. The main issues a reconstruction algorithm has to deal with, are the noise in the data, the presence of regulatory cycles, and the direction of the regulatory effects. We introduce a novel rule that, in contrast to the previously mentioned methods, simultaneously takes into account all these aspects. An efficient algorithm for the computation of the minimal graph is given, whose time complexity is cubic in the number of vertices of the graph. Finally, we demonstrate the utility of our method in a simulation study.
需要关注的问题是，如何从由容易出错的测量构建的相互作用图中区分直接调节效应和间接调节效应的算法。这些算法中的许多都可以表述为一种从图中移除一条边的规则，使得剩余的图仍然与数据一致。给出了一组温和的条件，在这些条件下，反复应用这样的规则会得到唯一的最小一致图。我们表明，三种常见的直接相互作用搜索方法满足这些条件，从而为它们的使用提供了依据。重建算法必须处理的主要问题是数据中的噪声、调节循环的存在以及调节效应的方向。我们引入了一种新颖的规则，与上述方法不同，它同时考虑了所有这些方面。给出了一种计算最小图的高效算法，其时间复杂度在图的顶点数量上是立方级的。最后，我们在模拟研究中展示了我们方法的实用性。
