Core Decomposition Analysis of Weighted Biological Networks

Abstract

Summary of thesis:

English version:

In biology, advanced, high-throughput experimental methods are becoming faster, cheaper and more accessible. Effective network analysis tools applicable to a broad range of networks is therefore needed in order to gain biologically relevant knowledge from the continuously growing mass of empirical data. Weighted complex networks, where the connections between the nodes are associated by non-uniform strengths, have been applied in the context of numerous scientific fields, including informatics, physics, sociology and biology. There exist several approaches for finding important sets of nodes in weighted networks, and much of the work comprising this dissertation is related to the development and investigation of one such method, namely the generalization of k-core analysis to weighted network, the s-core network decomposition.

The k-core network decomposition method has proven to be an effective tool for selecting the central set of nodes contained within a network by recursively removing nodes with low connectivity until a highly clustered innermost core is all that remains of the initial network. In recent years, k-core, or k-shell, analysis has been successfully applied to disease spreading, protein-protein interaction and air traffic networks, among others. The s-core method combines the influence of topology and link-weight values in the node-peeling process, using the node strength s instead of degree k in the node-removal query. Core decomposition methods rely on networks where the minority of the nodes are contained in the innermost cores. To accommodate for the application of core decomposition methods when the innermost s-core size is large, we developed an extension to s-core analysis, the s-core+ decomposition method, employing an iterative link-peeling scheme when the innermost s-core is reached. The relationship between k-core and s-core was also investigated extensively. In order to create weighted biological networks from multiple samples of gene-expression and proteomic data, we calculated correlation matrices across the biological samples and the subsequent weighted topological overlap (wTO) matrices. This approach creates robust networks, where node-pairs that are strongly correlated with mutual neighbors receive large values in the wTO matrix. Numerous studies have shown that this approach is suited for analyzing biological data, and we applied a modified version of this method to gene-expression data from human and mouse, creating two networks for each species based on all available tissue samples, or just those from brain and central nervous system. These networks were considered separately and compared within and across species and tissue type. Proteomic data from kidneys in three-spined stickleback populations indigenous to both fresh water and salt water was also analyzed using the above framework.

The resulting networks were analyzed, using the s-core+ decomposition results as node-centrality rank. For the biological networks, the method effectively uncovered interesting biochemical behavior, showing great promise for future applications. The s-core+ decomposition based node ranking was applied to the human and mouse network comparisons, providing a general scaffold for comparing topological similarities and differences between nodes. We have shown that the s-core and s-core+ network decomposition methods can be applied successfully to a variety of networks, ranging from random network models with various link-weight distributions, the yeast protein-protein interaction network, social networks to the US air traffic network.

Norsk versjon:

Avanserte eksperimentelle metoder for generering av biologiske datasett har stadig blitt både raskere, billigere og mer tilgjengelige. For å kunne håndtere, og få biologisk relevant kunnskap fra, slike datamengder, er det behov for effektive nettverksanalyseverktøy som er anvendbare på flere typer nettverk. Vektede, komplekse nettverk, der forbindelsene mellom nodene har tilhørende ikkeuniforme styrkeverdier, har blitt brukt innen flere vitenskapelige felt, slik som informatikk, fysikk, sosiologi og biologi. Det finnes mange måter for å finne viktige nodegrupper i vektede nettverk, og mye av arbeidet i denne avhandlingen er relatert til utvikling og utforsking av én slik metode, nemlig generaliseringen av k-core-analyse til vektede nettverk, s-core-nettverksdekomponering.

Metoden kjent som k-core-nettverksdekomponering har vist seg å være et effektivt verktøy for utvelgelse av sentrale nodegrupper i et nettverk, ved å rekursivt fjerne noder med lav grad (antall nabonoder) inntil en sentral kjerne av noder er alt som gjenstår av startnettverket. De siste årene, har k-core-, også kjent som k-shell-, analyse blitt brukt med hell på nettverksstudier av blant annet sykdomsspredning, protein-protein-interaksjoner og flytrafikk. s-core-metoden kombinerer effekten av nettverkstopologien i tillegg til lenkevektene for å bestemme hvilke noder som skal fjernes, og bruker nodestyrken s i stedet for graden k i algoritmen for nodefjerning. Core-dekomponeringsmetoder fungerer best på nettverk der det er relativt få noder i den innerste kjernen. For å tilrettelegge metodikken for situasjoner der de innerste kjernene er store, utviklet vi en utvidelse av s-core-analyse, s-core+, der lenker med lav lenkevekt fjernes når innerste s-core-kjerne er nådd. Sammenhengen mellom k-core og s-core ble grundig utforsket.

For å konstruere vektede biologiske nettverk fra en rekke prøver med genekspresjons- og proteomikkdata, regnet vi ut korrelasjonsmatriser fra tidsrekkene med biologisk data med påfølgende utregninger av matriser for vektet topologisk overlapp (wTO). Denne metoden gir robuste nettverk der nodepar som er sterkt korrelerte med de samme naboene får store wTO-verdier. Flere studier viser at denne fremgangsmåten passer for å analysere biologiske datasett, og vi anvendte en modifisert versjon av metoden på genekspresjonsdata fra menneske og mus til å lage to nettverk for hver art basert på alle vevsprøver, eller kun vev fra hjerne og sentralnervesystemet. Disse nettverkene ble analysert separat og sammenlignet innad og på tvers av art og vevstyper. Proteomikkdata fra nyrer i trepigget stingsild fra populasjoner i både saltvann og ferskvann ble også analysert ved bruk av overfornevnte metodikk.

De resulterende nettverkene ble analysert ved å bruke dekomponeringsresultatene fra s-core+ som en rangering for nodesentralitet. For de biologiske nettverkene avdekket metoden interessant biokjemisk oppførsel, noe som lover godt for fremtidige anvendelser. Noderangering basert på s-core+ ble anvendt for å sammenligne menneske- og musenettverkene, men er også et generelt rammeverk for sammenligning av topologiske likheter og ulikheter mellom noder. Vi har vist at nettverksdekomponeringsmetodene s-core og s-core+ kan anvendes på, og gir gode resultater for, flere nettverkstyper, slik som tilfeldige nettverk med et utvalg lenkevektsfordelinger, protein-protein-interaksjonsnettverket for gjær, sosiale nettverk og flytrafikknettverket i USA.