Mining Relationships among Multiple Entities in Biological Networks

Jiajie Peng, Linjiao Zhu, Yadong Wang, Jin Chen

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

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.

Original languageEnglish
Article number8666735
Pages (from-to)769-776
Number of pages8
JournalIEEE/ACM Transactions on Computational Biology and Bioinformatics
Volume17
Issue number3
DOIs
StatePublished - May 1 2020

Bibliographical note

Funding Information:
This work has been supported by NSF ABI no. 1458556 and NSFC no. 61702421, U1811262, the International Postdoctoral Fellowship Program (no. 20180029), Top International University Visiting Program for Outstanding Young Scholars of Northwestern Polytechnical University. The authors would like to thank graduate student Mr. Yuan Li at the Harbin Institute of Technology for testing CST-Miner on multiple platforms.

Publisher Copyright:
© 2004-2012 IEEE.

Keywords

  • Biological network
  • clustering
  • minimum steiner tree
  • topological relationship

ASJC Scopus subject areas

  • Biotechnology
  • Genetics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Mining Relationships among Multiple Entities in Biological Networks'. Together they form a unique fingerprint.

Cite this