A standard paradigm in computational biology is to leverage interaction networks as prior knowledge in analyzing high-throughput biological data, where the data give a score for each vertex in the network. One classical approach is the identification of altered subnetworks, or subnetworks of the interaction network that have both outlier vertex scores and a defined network topology. One class of algorithms for identifying altered subnetworks search for high-scoring subnetworks in subnetwork families with simple topological constraints, such as connected subnetworks, and have sound statistical guarantees. A second class of algorithms employ network propagation—the smoothing of vertex scores over the network using a random walk or diffusion process—and utilize the global structure of the network. However, network propagation algorithms often rely on ad hoc heuristics that lack a rigorous statistical foundation. In this work, we unify the subnetwork family and network propagation approaches by deriving the propagation family, a subnetwork family that approximates the sets of vertices ranked highly by network propagation approaches. We introduce NetMix2, a principled algorithm for identifying altered subnetworks from a wide range of subnetwork families. When using the propagation family, NetMix2 combines the advantages of the subnetwork family and network propagation approaches. NetMix2 outperforms other methods, including network propagation on simulated data, pan-cancer somatic mutation data, and genome-wide association data from multiple human diseases.
Get full access to this article
View all access options for this article.
References
1.
Addario-BerryL, BroutinN, DevroyeL, et al. On combinatorial testing problems. Ann Stat 2010;38(5):3063–3092.
2.
Arias-CastroE, CandèsEJ, HelgasonH, et al. Searching for a trail of evidence in a maze. Ann Stat, 2008;36(4):1726–1757.
3.
Arias-CastroE, CandèsEJ, DurandA. Detection of an anomalous cluster in a network. Ann Stat, 2011;39(1):278–304.
4.
Arias-CastroE, DonohoDL, HuoX. Adaptive multiscale detection of filamentary structures in a background of uniform random points. Ann Stat, 2006;34(1):326–349.
5.
AyatiM, ErtenS, ChanceMR, et al.MOBAS: Identification of disease-associated protein subnetworks using modularity-based scoring. EURASIP J Bioinform Syst Biol, 2015; 2015(1):7.
6.
AzencottC-A, GrimmD, SugiyamaM, et al. Efficient network-guided multi-locus association mapping with graph cuts. Bioinformatics, 2013;29(13):i171–i179.
7.
BaileyMH, TokheimC, Porta-PardoE, et al. Comprehensive characterization of cancer driver genes and mutations. Cell, 2018;173(2):371–385.
8.
BarelG, HerwigR. NetCore: A network propagation approach using node coreness. Nucleic Acids Res, 2020;48(17):e98–e98.
9.
BattagliaS, MaguireO, CampbellMJ. Transcription factor co-repressors in cancer biology: Roles and targeting. Int J Cancer, 2010;126(11):2511–2519.
10.
BenjaminiY, HochbergY. Controlling the false discovery rate: A practical and powerful approach to multiple testing. J R Stat Soc Ser B (Methodol), 1995;57(1):289–300.
BoyleEA, LiYI, PritchardJK. An expanded view of complex traits: From polygenic to omnigenic. Cell, 2017;169(7):1177–1186.
13.
CadenaJ, ChenF, VullikantiA. Near-optimal and practical algorithms for graph scan statistics with connectivity constraints. ACM Trans Knowl Discov Data, 2019; 13(2):20:1–20:33.
14.
CaiTT, JinJ, LowMG. Estimation and confidence sets for sparse normal mixtures. Ann Stat, 2007;35(6):2421–2449.
15.
CalifanoA, ButteAJ, FriendS, et al. Leveraging models of cell regulation and GWAS data in integrative network-based association studies. Nat Genet, 2012;44(8):841–847.
16.
CaoM, ZhangH, ParkJ, et al. Going the distance for protein function prediction: A new distance metric for protein interaction networks. PLoS One, 2013;8(10).
17.
CarlinDE, FongSH, QinY, et al. A fast and flexible framework for network-assisted genomic association. iScience, 2019; 16:155–161.
18.
ChakravartyD, GaoJ, PhillipsS, et al. OncoKB: A precision oncology knowledge base. JCO Precis Oncol, 2017; 1:1–16.
19.
ChasmanD, SiahpiraniAF, RoyS. Network-based approaches for analysis of complex biological systems. Curr Opin Biotechnol, 2016; 39:157–166.
20.
ChitraU, DingK, LeeJCH, et al. Quantifying and reducing bias in maximum likelihood estimation of structured anomalies. In: Proceedings of the 38th International Conference on Machine Learning PMLR;, 2021; pp. 1908–1919.
ChoobdarS, AhsenME, CrawfordJ, et al. Assessment of network module identification across complex diseases. Nat Methods, 2019;16(9):843–852.
23.
ChuaHN, SungW, WongL. Exploiting indirect neighbours and topological weight to predict protein function from protein-protein interactions. Bioinformatics, 2006;22(13):1623–1630.
24.
CornishAJ, MarkowetzF. SANTA: Quantifying the functional content of molecular networks. PLoS Comput Biol, 2014;10(9):e1003808-.
25.
CowenL, DevkotaK, HuX, et al. Diffusion state distances: Multitemporal analysis, fast algorithms, and applications to biological networks. SIAM J Math Data Sci, 2021;3(1):142–170.
26.
CowenL, IdekerT, RaphaelBJ, et al. Network propagation: A universal amplifier of genetic associations. Nat Rev Genet, 2017;18(9):551–562.
27.
CreixellP, ReimandJ, HaiderS, et al. Pathway and network analysis of cancer genomes. Nat Methods, 2015;12(7):615–621.
28.
DasJ, YuH. HINT: High-quality protein interactomes and their applications in understanding human disease. BMC Syst Biol, 2012; 6(1):92.
29.
DavisJ, GoadrichM. The relationship between precision-recall and ROC curves. In: Proceedings of the 23rd International Conference on Machine Learning. ICML ’06 Association for Computing Machinery: New York, NY, USA;, 2006; pp. 233–240.
30.
de la FuenteA. From ‘differential expression’ to ‘differential networking’—Identification of dysfunctional regulatory networks in diseases. Trends Genet, 2010;26(7):326–333.
31.
DengM, ZhangK, MehtaS, et al. Prediction of protein function using protein–protein interaction data. J Comput Biol, 2003;10(6):947–960.
32.
DimitrakopoulosCM, BeerenwinkelN. Computational approaches for the identification of cancer genes and pathways. WIREs Syst Biol Med, 2017; 9(1):e1364.
33.
DittrichMT, KlauG, RosenwaldA, et al. Identifying functional modules in protein–protein interaction networks: An integrated exact approach. Bioinformatics, 2008;24(13):i223–i231.
34.
DonohoD, JinJ. Higher criticism for detecting sparse heterogeneous mixtures. Ann Stat, 2004;32(3):962–994.
35.
EfronB. Large-scale simultaneous hypothesis testing: The choice of a null hypothesis. J Am Stat Assoc, 2004;99(465):96–104.
36.
EfronB. Correlation and large-scale simultaneous significance testing. J Am Stat Assoc 2007a;102(477):93–103.
37.
EfronB. Size, power and false discovery rates. Ann Stat 2007b;35(4):1351–1377.
38.
EfronB, TurnbullBB, NarasimhanB. Locfdr: Computes local false discovery rates. R package version, 2011; 1:1–7.
39.
FongSH, CarlinDE, OzturkK, et al. Strategies for network GWAS evaluated using classroom crowd science. Cell Syst, 2019;8(4):275–280.
40.
GhiassianSD, MencheJ, BarabásiA-L. A DIseAse MOdule Detection (DIAMOnD) algorithm derived from a systematic analysis of connectivity patterns of disease proteins in the human interactome. PLoS Comput Biol, 2015;11(4):e1004120-.
41.
GlazJ, NausJ, WallensteinS. Scan Statistics. Springer-Verlag New York: New York, NY, USA; 2001.
42.
GligorijevićV, PržuljN. Methods for biological data integration: Perspectives and challenges. J R Soc Interface, 2015; 12(112):20150571.
43.
GreeneCS, KrishnanA, WongAK, et al. Understanding multicellular function and disease with human tissue-specific networks. Nat Genet, 2015;47(6):569–576.
44.
GuoX, LinW, BaoJ, et al. A comprehensive Cis-EQTL analysis revealed target genes in breast cancer susceptibility loci identified in genome-wide association studies. Am J Human Genet, 2018;102(5):890–903.
45.
GuoZ, LiY, GongX, et al. Edge-based scoring and searching method for identifying condition-responsive protein–protein interaction sub-network. Bioinformatics, 2007;23(16):2121–2128.
HofreeM, ShenJP, CarterH, et al. Network-based stratification of tumor mutations. Nat Methods, 2013;10(11):1108–1115.
49.
HormozdiariF, PennO, BorensteinE, et al. The discovery of integrated gene networks for autism and related disorders. Genome Res, 2015;25(1):142–154.
50.
HornH, LawrenceMS, ChouinardCR, et al. NetSig: Network-based discovery from cancer genomes. Nat Methods, 2018;15(1):61–66.
51.
HuangJK, CarlinDE, YuMK, et al. Systematic evaluation of molecular networks for discovery of disease genes. Cell Syst, 2018;6(4):484–495.
52.
IdekerT, OzierO, SchwikowskiB, et al. Discovering regulatory and signalling circuits in molecular interaction networks. Bioinformatics, 2002;18(Suppl. 1):S233–S240.
53.
IdekerT, ThorssonV, RanishJA, et al. Integrated genomic and proteomic analyses of a systematically perturbed metabolic network. Science, 2001;292(5518):929–934.
54.
JiaP, ZhaoZ. Network assisted analysis to prioritize GWAS results: Principles, methods and perspectives. Human Genet, 2014;133(2):125–138.
KulldorffM. A spatial scan statistic. Commun Stat Theory Methods, 1997;26(6):1481–1496.
57.
KöhlerS, BauerS, HornD, et al. Walking the interactome for prioritization of candidate disease genes. Am J Human Genet, 2008;82(4):949–958.
58.
LamparterD, MarbachD, RueediR, et al.Fast and rigorous computation of gene and pathway scores from SNP-based summary statistics. PLoS Comput Biol, 2016; 12(1):e1004714.
59.
LawrenceMS, StojanovP, MermelCH, et al. Discovery and saturation analysis of cancer genes across 21 tumour types. Nature, 2014;505(7484):495–501.
60.
LazarevaO, BaumbachJ, ListM, et al. On the limits of active module identification. Brief Bioinform, 2021;22(5).
61.
LeeI, BlomUM, WangPI, et al. Prioritizing candidate disease genes by network-based boosting of genome-wide association data. Genome Res, 2011;21(7):1109–1121.
62.
LeisersonMD, EldridgeJV, RamachandranS, et al. Network analysis of GWAS data. Curr Opin Genet Dev, 2013;23(6):602–610.
63.
LeisersonMDM, VandinF, WuH-T, et al. Pan-cancer network analysis identifies combinations of rare somatic mutations across pathways and protein complexes. Nat Genet, 2015;47(2):106–114.
64.
LeviH, ElkonR, ShamirR. DOMINO: A network-based active module identification algorithm with reduced rate of false calls. Mol Syst Biol, 2021; 17(1):e9593.
65.
LiuY, BrossardM, RoqueiroD, et al. SigMod: An exact and efficient method to identify a strongly interconnected disease-associated module in a gene network. Bioinformatics, 2017;33(10):1536–1544.
66.
LuoY, ZhaoX, ZhouJ, et al.A network integration approach for drug-target interaction prediction and computational drug repositioning from heterogeneous information. Nat Commun, 2017; 8(1):573.
67.
McLachlanGJ, BeanRW, JonesLB-T. A simple implementation of a normal mixture approach to differential gene expression in multiclass microarrays. Bioinformatics, 2006;22(13):1608–1615.
68.
MencheJ, SharmaA, KitsakM, et al. Uncovering disease-disease relationships through the incomplete human interactome. Science, 2015;347(6224):1257601–1257601.
69.
MitraK, CarvunisA-R, RameshSK, et al. Integrative approaches for finding modular structure in biological networks. Nat Rev Genet, 2013;14(10):719–732.
70.
modENCODEConsortium, RoyS, ErnstJ, et al. Identification of functional elements and regulatory circuits by Drosophila ModENCODE. Science, 2010;330(6012):1787–1797.
71.
NabievaE, JimK, AgarwalA, et al. Whole-proteome prediction of protein function via graph-theoretic analysis of interaction maps. Bioinformatics, 2005; 21:i302–i310.
72.
NakkaP, RaphaelBJ, RamachandranS. Gene and network analysis of common variants reveals novel associations in multiple complex diseases. Genetics, 2016;204(2):783–798.
73.
NibbeRK, KoyutürkM, ChanceMR. An integrative-omics approach to identify functional sub-networks in human colorectal cancer. PLoS Comput Biol, 2010; 6(1):e1000639.
74.
NikolayevaI, PlaOG, SchwikowskiB. Network module identification–a widespread theoretical bias and best practices. Methods, 2018; 132:19–25.
75.
PageL, BrinS, MotwaniR, et al. The PageRank Citation Ranking: Bringing Order to the Web. Technical Report. Stanford InfoLab: Stanford, CA, USA; 1999.
76.
PanW, LinJ, LeCT. A mixture model approach to detecting differentially expressed genes with microarray data. Funct Integr Genom, 2003;3(3):117–124.
77.
PaullEO, CarlinDE, NiepelM, et al. Discovering causal pathways linking genomic events to transcriptional states using tied diffusion through interacting events (TieDIE). Bioinformatics, 2013;29(21):2757–2764.
78.
Picart-ArmadaS, BarrettSJ, WilléDR, et al. Benchmarking network propagation methods for disease gene identification. PLoS Comput Biol, 2019;15(9):1–24.
79.
PiñeroJ, Ramírez-AnguitaJM, Saüch-PitarchJ, et al. The DisGeNET knowledge platform for disease genomics: 2019 update. Nucleic Acids Res, 2020;48(D1):D845–D855.
80.
PoundsS, MorrisSW. Estimating the occurrence of false positives and false negatives in microarray studies by approximating and partitioning the empirical distribution of P-values. Bioinformatics, 2003;19(10):1236–1242.
81.
RadivojacP, ClarkWT, OronTR, et al. A large-scale evaluation of computational protein function prediction. Nat Methods, 2013;10(3):221–227.
82.
ReynaMA, ChitraU, ElyanowR, et al. NetMix: A network-structured mixture model for reduced-bias estimation of altered subnetworks. J Comput Biol, 2021;28(5):469–484.
RobinsonS, NevalainenJ, PinnaG, et al. Incorporating interaction networks into the determination of functionally related hit genes in genomic experiments with Markov random fields. Bioinformatics, 2017;33(14):i170–i179.
85.
RollandT, TaşanM, CharloteauxB, et al. A proteome-scale map of the human interactome network. Cell, 2014;159(5):1212–1226.
86.
SharanR, UlitskyI, ShamirR. Network-based prediction of protein function. Mol Syst Biol, 2007; 3:88–88.
87.
SharpnackJ, KrishnamurthyA, SinghA. Near-optimal anomaly detection in graphs using Lovász extended scan statistic. In: Proceedings of the 26th International Conference on Neural Information Processing Systems, Volume 2. NIPS’13 2013a; pp. 1959–1967.
88.
SharpnackJ, RinaldoA, SinghA. Detecting anomalous activity on networks with the graph fourier scan statistic. IEEE Trans Signal Process, 2016;64(2):364–379.
89.
SharpnackJ, SinghA, RinaldoA. Changepoint detection over graphs with the spectral scan statistic. In: Artificial Intelligence and Statistics 2013b; pp. 545–553.
90.
ShresthaR, HodzicE, SauerwaldT, et al. HIT'nDRIVE: Patient-specific multidriver gene prioritization for precision oncology. Genome Res, 2017;27(9):1573–1588.
91.
SzklarczykD, FranceschiniA, WyderS, et al. STRING V10: Protein–protein interaction networks, integrated over the tree of life. Nucleic Acids Res, 2015;43(D1):D447–D452.
92.
TateJG, BamfordS, JubbHC, et al. COSMIC: The catalogue of somatic mutations in cancer. Nucleic Acids Res, 2019;47(D1):D941–D947.
93.
UffelmannE, HuangQQ, MunungNS, et al. Genome-wide association studies. Nat Rev Methods Prim, 2021;1(1):1–21.
94.
UlitskyI, ShamirR. Identification of functional modules using network topology and high-throughput data. BMC Syst Biol, 2007; 1(1):8.
95.
VandinF, ClayP, UpfalE, et al. Discovery of mutated subnetworks associated with clinical data in cancer. In: Pacific Symposium on Biocomputing 2012a; pp. 55–66.
96.
VandinF, UpfalE, RaphaelBJ. Algorithms for detecting significantly mutated pathways in cancer. J Comput Biol, 2011;18(3):507–522.
97.
VandinF, UpfalE, RaphaelBJ. De novo discovery of mutated driver pathways in cancer. Genome Res 2012b;22(2):375–385.
98.
VanunuO, MaggerO, RuppinE, et al.Associating genes and protein complexes with disease via network propagation. PLoS Comput Biol, 2010; 6(1):e1000641.
99.
VelgheA, Van CauwenbergheS, PolyanskyA, et al. PDGFRA alterations in cancer: Characterization of a gain-of-function V536E transmembrane mutant as well as loss-of-function and passenger mutations. Oncogene, 2014;33(20):2568–2576.
100.
VlaicS, ConradT, Tokarski-SchnelleC, et al.ModuleDiscoverer: Identification of regulatory modules in protein-protein interaction networks. Sci Rep, 2018; 8(1):433.
101.
WangX, TerfveC, RoseJC, et al. HTSanalyzeR: An R/bioconductor package for integrated network analysis of high-throughput screens. Bioinformatics, 2011;27(6):879–880.
102.
WestonJ, ElisseeffA, ZhouD, et al. Protein ranking: From local to global structure in the protein similarity network. Proc Natl Acad Sci, 2004;101(17):6559–6563.
103.
XiaJ, GillEE, HancockREW. NetworkAnalyst for statistical, visual and network-based meta-analysis of gene expression data. Nat Protoc, 2015;10(6):823–844.
104.
ZhuZ, ZhangF, HuH, et al. Integration of summary data from GWAS and EQTL studies predicts complex trait gene targets. Nat Genet, 2016;48(5):481–487.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
