Computational intractability law molds the topology of biological networks

Applied Network Science

Katsumi Inoue¹  Jérôme Waldispühl²  Silvia Vidal²  Ali A. Atiia³  Corbin Hopper³ 

[1] National Institute of Informatics;Research Centre on Complex Traits, McGill University;School of Computer Science, McGill University;

关键词: Biological networks;    Systems biology;    Emergence;    Computational complexity;    Computational intractability;    Combinatorial optimization;   

DOI  :  10.1007/s41109-020-00268-0

来源: DOAJ

【 摘 要 】

Abstract Virtually all molecular interaction networks (MINs), irrespective of organism or physiological context, have a majority of loosely-connected ‘leaf’ genes interacting with at most 1-3 genes, and a minority of highly-connected ‘hub’ genes interacting with at least 10 or more other genes. Previous reports proposed adaptive and non-adaptive hypotheses describing sufficient but not necessary conditions for the origin of this majority-leaves minority-hubs (mLmH) topology. We modelled the evolution of MINs as a computational optimization problem which describes the cost of conserving, deleting or mutating existing genes so as to maximize (minimize) the overall number of beneficial (damaging) interactions network-wide. The model 1) provides sufficient and, assuming P ≠ N P $\mathcal {P}\neq \mathcal {NP}$ , necessary conditions for the emergence of mLmH as an adaptation to circumvent computational intractability, 2) predicts the percentage number of genes having d interacting partners, and 3) when employed as a fitness function in an evolutionary algorithm, produces mLmH-possessing synthetic networks whose degree distributions match those of equal-size MINs.

【 授权许可】

Unknown