Mining Relationships among Multiple Entities in Biological Networks

Jiajie Peng; Linjiao Zhu; Yadong Wang; Jin Chen

doi:10.1109/TCBB.2019.2904965

Mining Relationships among Multiple Entities in Biological Networks

Jiajie Peng, Linjiao Zhu, Yadong Wang, Jin Chen

Internal Medicine

Research output: Contribution to journal › Article › peer-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 language	English
Article number	8666735
Pages (from-to)	769-776
Number of pages	8
Journal	IEEE/ACM Transactions on Computational Biology and Bioinformatics
Volume	17
Issue number	3
DOIs	https://doi.org/10.1109/TCBB.2019.2904965
State	Published - 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

Access to Document

10.1109/TCBB.2019.2904965

Cite this

@article{b1de39e0404642aa8b3ca8d384f68e8b,

title = "Mining Relationships among Multiple Entities in Biological Networks",

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.",

keywords = "Biological network, clustering, minimum steiner tree, topological relationship",

author = "Jiajie Peng and Linjiao Zhu and Yadong Wang and Jin Chen",

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: {\textcopyright} 2004-2012 IEEE.",

year = "2020",

month = may,

day = "1",

doi = "10.1109/TCBB.2019.2904965",

language = "English",

volume = "17",

pages = "769--776",

number = "3",

}

TY - JOUR

T1 - Mining Relationships among Multiple Entities in Biological Networks

AU - Peng, Jiajie

AU - Zhu, Linjiao

AU - Wang, Yadong

AU - Chen, Jin

N1 - 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.

PY - 2020/5/1

Y1 - 2020/5/1

N2 - 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.

AB - 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.

KW - Biological network

KW - clustering

KW - minimum steiner tree

KW - topological relationship

UR - http://www.scopus.com/inward/record.url?scp=85075529063&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85075529063&partnerID=8YFLogxK

U2 - 10.1109/TCBB.2019.2904965

DO - 10.1109/TCBB.2019.2904965

M3 - Article

C2 - 30872239

AN - SCOPUS:85075529063

VL - 17

SP - 769

EP - 776

IS - 3

M1 - 8666735

ER -

Mining Relationships among Multiple Entities in Biological Networks

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this