Duplication and Divergence Effect on Network Motifs in Undirected Bio-Molecular Networks.pdf

312 IEEE TRANSACTIONS ON BIOMEDICAL CIRCUITS AND SYSTEMS, VOL. 9, NO. 3, JUNE 2015 Duplication and Divergence Effect on Network Motifs in Undirected Bio-Molecular Networks Pei Wang, Jinhu Lü, Fellow, IEEE, Xinghuo Yu, Fellow, IEEE, and Zengrong Liu Abstract—Duplication and divergence are two basic evolu- tionary mechanisms of bio-molecular networks. Real-world bio-molecular networks and their statistical characteristics can be well mimicked by artificial algorithms based on the two mecha- nisms. Bio-molecular networks consist of network motifs, which act as building blocks of large-scale networks. A fundamental question is how network motifs are evolved from long time evo- lution and natural selection. By considering the effect of various duplication and divergence strategies, we find that the underlying duplication scheme of the real-world undirected bio-molecular networks would rather follow the anti-preference strategy than the random one. The anti-preference duplication mechanism and the dimerization processes can lead to the formation of various motifs, and robustly conserve proper quantities of motifs in the artificial networks as that in the real-world ones. Furthermore, the anti-preference mechanism and edge deletion divergence can robustly preserve the sparsity of the networks. The investigations reveal the possible evolutionary mechanisms of network motifs in real-world bio-molecular networks, and have potential impli- cations in the design, synthesis and reengineering of biological networks for biomedical purpose. Index Terms—Bio-molecular network, duplication and diver- gence, evolutionary mechanism, network growth model, network motif. I. INTRODUCTION I T is well known that biological systems can be describedby complex networks. Structures and functions of complex networks arising from various disciplines have been extensively investigated in the last several decades [1], [2]. Manuscript received January 12, 2014; revised March 25, 2014; accepted July 2