Network deconvolution as a general method to distinguish direct dependencies in networks

Nature Biotechnology
Soheil FeiziManolis Kellis

Abstract

Recognizing direct relationships between variables connected in a network is a pervasive problem in biological, social and information sciences as correlation-based networks contain numerous indirect relationships. Here we present a general method for inferring direct effects from an observed correlation matrix containing both direct and indirect effects. We formulate the problem as the inverse of network convolution, and introduce an algorithm that removes the combined effect of all indirect paths of arbitrary length in a closed-form solution by exploiting eigen-decomposition and infinite-series sums. We demonstrate the effectiveness of our approach in several network applications: distinguishing direct targets in gene expression regulatory networks; recognizing directly interacting amino-acid residues for protein structure prediction from sequence alignments; and distinguishing strong collaborations in co-authorship social networks using connectivity information alone. In addition to its theoretical impact as a foundational graph theoretic tool, our results suggest network deconvolution is widely applicable for computing direct dependencies in network science across diverse disciplines.

References

Apr 1, 1994·Proteins·U GöbelA Valencia
Jan 4, 1994·Proceedings of the National Academy of Sciences of the United States of America·E Neher
Dec 7, 2000·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·Nir FriedmanD Pe'er
Jul 20, 2001·Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics·M E Newman
Apr 24, 2002·Physical Review. E, Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics·B G GiraudA S Lapedes
Oct 14, 2003·Nature Biotechnology·Ziv Bar-JosephDavid K Gifford
Jul 31, 2004·Bioinformatics·Alberto de la FuentePedro Mendes
Mar 15, 2005·Nature Biotechnology·Diego di BernardoJames J Collins
Mar 9, 2006·BMC Bioinformatics·Kenzie D MacIsaacErnest Fraenkel
Oct 10, 2006·Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics·M E J Newman
Mar 14, 2007·Molecular Systems Biology·Roded SharanRon Shamir
Jan 1, 2009·Proceedings of the National Academy of Sciences of the United States of America·Martin WeigtTerence Hwa
Jan 7, 2010·PLoS Computational Biology·Lukas Burger, Erik van Nimwegen
Mar 24, 2010·Proceedings of the National Academy of Sciences of the United States of America·Daniel MarbachGustavo Stolovitzky
Jun 29, 2010·Journal of Computational Neuroscience·Christopher J QuinnNicholas G Hatsopoulos
Sep 2, 2010·Nature Reviews. Microbiology·Riet De Smet, Kathleen Marchal
Oct 12, 2010·PloS One·Vân Anh Huynh-ThuPierre Geurts
Nov 23, 2011·Proceedings of the National Academy of Sciences of the United States of America·Faruck MorcosMartin Weigt
Dec 14, 2011·PloS One·Debora S MarksChris Sander
Apr 3, 2012·Bioinformatics·Robert KüffnerRalf Zimmer
May 31, 2012·Proceedings of the National Academy of Sciences of the United States of America·Timothy Nugent, David T Jones
Jul 17, 2012·Nature Methods·Daniel MarbachGustavo Stolovitzky
Nov 10, 2012·Nature Biotechnology·Debora S MarksChris Sander
Nov 24, 2012·BMC Systems Biology·Anne-Claire HauryJean-Philippe Vert
Feb 16, 2013·Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics·Magnus EkebergErik Aurell

Citations

Aug 10, 2013·Nature Biotechnology·Babak Alipanahi, Brendan J Frey
Mar 4, 2014·PloS One·Michele FilosiCesare Furlanello
May 9, 2014·PloS One·Alejandro F VillaverdeJulio R Banga
Aug 26, 2014·PloS One·Muhammed A Yildirim, Michele Coscia
Oct 1, 2015·Proceedings of the National Academy of Sciences of the United States of America·Taek KangLeonidas Bleris
Jun 19, 2014·Biophysical Journal·Sudhakaran PrabakaranEduardo Sontag
Jan 29, 2014·BioEssays : News and Reviews in Molecular, Cellular and Developmental Biology·Victoria Moignard, Berthold Göttgens
Aug 8, 2015·Journal of Theoretical Biology·Shiguo DengHuijie Yang
Nov 8, 2014·Briefings in Bioinformatics·Ben TengZengyou He
Apr 20, 2016·Proceedings of the National Academy of Sciences of the United States of America·Juan ZhaoLuonan Chen
Apr 8, 2015·Nature Biotechnology·Baruch Barzel, Albert-László Barabási
Jul 6, 2014·Progress in Lipid Research·Tuulia Hyötyläinen, Matej Orešič
Mar 29, 2014·Methods : a Companion to Methods in Enzymology·Andrew E TeschendorffReimer Kuehn
Jun 17, 2016·Bioinformatics·Yue DengLani F Wu
Sep 30, 2016·Scientific Reports·Xiao-Fei ZhangHong Yan
Jan 4, 2017·PLoS Computational Biology·Hualou Liang, Hongbin Wang
Aug 19, 2014·Journal of Experimental Botany·Atsushi Fukushima, Miyako Kusano
Aug 2, 2016·PLoS Computational Biology·Fei LiuLuonan Chen
Apr 23, 2016·Scientific Reports·Wenjing RuanTao Wu
Feb 13, 2016·Scientific Reports·Nooshin OmranianZoran Nikoloski
Jul 23, 2016·Scientific Reports·Xiao HanCelso Grebogi
Feb 27, 2016·Scientific Reports·Hoang M Tran, Satish T S Bukkapatnam
Jan 20, 2017·IEEE Transactions on Nanobioscience·Malay BhattacharyyaSanghamitra Bandyopadhyay
Dec 21, 2017·Nature Communications·Jose CasadiegoMarc Timme
May 20, 2015·Bioinformatics and Biology Insights·Xiaoxi DongAndrey Morgun
Jun 9, 2017·MSystems·Julia W NeilsonRaina M Maier
Aug 31, 2018·Bioinformatics·Mahsa GhanbariMartin Vingron
Apr 8, 2015·Nature Biotechnology
Apr 17, 2015·Nature·Erika Check Hayden
May 31, 2019·FASEB Journal : Official Publication of the Federation of American Societies for Experimental Biology·Francisco J OrtegaJosé M Fernández-Real
Jan 15, 2016·Physical Review Letters·Dong ZhouShlomo Havlin
Oct 7, 2019·Proteins·Rojan ShresthaAndras Fiser
Jan 7, 2020·Bioinformatics·Rasmus Magnusson, Mika Gustafsson
Aug 26, 2014·Statistical Applications in Genetics and Molecular Biology·Chris J OatesSimon E F Spencer
Nov 22, 2016·Molecular BioSystems·Le Ou-YangXiao-Fei Zhang
Feb 14, 2015·Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics·Zhaoyang ZhangGang Hu
Dec 13, 2016·EURASIP Journal on Bioinformatics & Systems Biology·Nurgazy Sulaimanov, Heinz Koeppl
Jun 20, 2018·Nature Methods·Taibo LiKasper Lage
Aug 8, 2018·Nature Communications·Bo WangJure Leskovec
Jan 12, 2016·Quantitative Biology·Ronak Y PatelGary D Stormo
Jun 1, 2019·NPJ Systems Biology and Applications·Daniel LillBoris N Kholodenko
Jun 20, 2019·Frontiers in Genetics·Clark GlymourPeter Spirtes
Jan 31, 2015·Physical Review Letters·Xiao HanZengru Di
May 17, 2017·Physical Review. E·Francesco AlderisioMario di Bernardo
May 24, 2019·Frontiers in Genetics·Walter NelsonRoded Sharan
Aug 1, 2014·Network Science·Andrew K RiderNitesh V Chawla
Jan 21, 2017·BMC Systems Biology·Minsu Lee, HyungJune Lee
Jul 14, 2017·Scientific Reports·Yang YangPhilip S Yu
Nov 14, 2018·Nature Communications·Syed HaiderPaul C Boutros

Related Concepts

In Silico
Computer Programs and Programming
Two-Parameter Models
Signal Transduction
Determination, Sequence Homology
Computational Molecular Biology
Cdna Microarrays
Gene Modules
Research Design
Viral Structural Proteins

Trending Feeds

COVID-19

Coronaviruses encompass a large family of viruses that cause the common cold as well as more serious diseases, such as the ongoing outbreak of coronavirus disease 2019 (COVID-19; formally known as 2019-nCoV). Coronaviruses can spread from animals to humans; symptoms include fever, cough, shortness of breath, and breathing difficulties; in more severe cases, infection can lead to death. This feed covers recent research on COVID-19.

Systemic Juvenile Idiopathic Arthritis

Systemic juvenile idiopathic arthritis is a rare rheumatic disease that affects children. Symptoms include joint pain, as well as fevers and skin rashes. Here is the latest research on this disease.

Chronic Fatigue Syndrome

Chronic fatigue syndrome is a disease characterized by unexplained disabling fatigue; the pathology of which is incompletely understood. Discover the latest research on chronic fatigue syndrome here.

Cell Atlas Along the Gut-Brain Axis

Profiling cells along the gut-brain axis at the single cell level will provide unique information for each cell type, a three-dimensional map of how cell types work together to form tissues, and insights into how changes in the map underlie health and disease of the GI system and its crosstalk with the brain. Disocver the latest research on single cell analysis of the gut-brain axis here.

Myocardial Stunning

Myocardial stunning is a mechanical dysfunction that persists after reperfusion of previously ischemic tissue in the absence of irreversible damage including myocardial necrosis. Here is the latest research.

Pontocerebellar Hypoplasia

Pontocerebellar hypoplasias are a group of neurodegenerative autosomal recessive disorders with prenatal onset, atrophy or hypoplasia of the cerebellum, hypoplasia of the ventral pons, microcephaly, variable neocortical atrophy and severe mental and motor impairments. Here is the latest research on pontocerebellar hypoplasia.

Central Pontine Myelinolysis

Central Pontine Myelinolysis is a neurologic disorder caused most frequently by rapid correction of hyponatremia and is characterized by demyelination that affects the central portion of the base of the pons. Here is the latest research on this disease.

Trichotillomania

Trichotillomania is an impulse control disorder characterized by the recurrent pulling of one's hair resulting in noticeable hair loss. Here are the latest discoveries in this field.

DDX3X Syndrome

DDX3X syndrome is caused by a spontaneous mutation at conception that primarily affects females due to its location on the X-chromosome. DDX3X syndrome has been linked to intellectual disabilities, seizures, autism, low muscle tone, brain abnormalities, and slower physical developments. Here is the latest research.

Related Papers

Nature Methods
Daniel MarbachGustavo Stolovitzky
Proceedings of the National Academy of Sciences of the United States of America
Daniel MarbachGustavo Stolovitzky
Drug Discovery Today
Paola Lecca, Corrado Priami
© 2021 Meta ULC. All rights reserved