IEEE/ACM Trans Comput Biol Bioinform. 2020 May-Jun;17(3):769-776. doi: 10.1109/TCBB.2019.2904965. Epub 2019 Mar 13.
Identifying topological relationships among multiple entities in biological networks is critical towards the understanding of the organizational principles of network functionality. Theoretically, this problem can be solved using minimum Steiner tree (MSTT) algorithms. However, due to large network size, it remains to be computationally challenging, and the predictive value of multi-entity topological relationships is still unclear. We present a novel solution called Cluster-based Steiner Tree Miner (CST-Miner) to instantly identify multi-entity topological relationships in biological networks. Given a list of user-specific entities, CST-Miner decomposes a biological network into nested cluster-based subgraphs, on which multiple minimum Steiner trees are identified. By merging all of them into a minimum cost tree, the optimal topological relationships among all the user-specific entities are revealed. Experimental results showed that CST-Miner can finish in nearly log-linear time and the tree constructed by CST-Miner is close to the global minimum.
确定生物网络中多个实体之间的拓扑关系对于理解网络功能的组织原则至关重要。从理论上讲，这个问题可以通过使用最小斯坦纳树（MSTT）算法来解决。然而，由于网络规模庞大，这仍然是一个具有计算挑战性的问题，并且多实体拓扑关系的预测价值仍不清楚。我们提出了一种称为基于聚类的斯坦纳树挖掘器（CST-Miner）的新解决方案，用于即时识别生物网络中的多实体拓扑关系。给定用户特定实体的列表，CST-Miner 将生物网络分解为嵌套的基于聚类的子图，在这些子图上确定多个最小斯坦纳树。通过将它们全部合并到一个最小成本树中，可以揭示所有用户特定实体之间的最佳拓扑关系。实验结果表明，CST-Miner 可以在近对数线性时间内完成，并且由 CST-Miner 构建的树接近全局最小。
