DOI: 10.1101/510495Jan 3, 2019Paper

Computational Intractability Law Molds the Topology of Biological Networks

BioRxiv : the Preprint Server for Biology
Ali A AtiiaJerome Waldispuhl


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 modeled 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≠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.

Related Concepts

Anatomy, Regional
Gene Deletion
Plant Leaves
Binding (Molecular Function)
Computed (Procedure)
CYP2C19*1 Allele
HuB Paraneoplastic Encephalomyelitis Antigen

Related Feeds

BioRxiv & MedRxiv Preprints

BioRxiv and MedRxiv are the preprint servers for biology and health sciences respectively, operated by Cold Spring Harbor Laboratory. Here are the latest preprint articles (which are not peer-reviewed) from BioRxiv and MedRxiv.

Related Papers

Journal of Pediatric Health Care : Official Publication of National Association of Pediatric Nurse Associates & Practitioners
N H Busen
© 2021 Meta ULC. All rights reserved