Introduction to Computational Neuroscience
Introduction to Computational Neuroscience PHYS 597A
Popular in Course
Popular in Physics 2
This 0 page Class Notes was uploaded by Otha Leffler on Sunday November 1, 2015. The Class Notes belongs to PHYS 597A at Pennsylvania State University taught by Reka Albert in Fall. Since its upload, it has received 19 views. For similar materials see /class/233088/phys-597a-pennsylvania-state-university in Physics 2 at Pennsylvania State University.
Reviews for Introduction to Computational Neuroscience
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 11/01/15
Community structure in networks Many realworld networks especially social ones exhibit community structure lntuitively community structure can be defined as the existence of subgraphs that are densely connected but sparsely interconnected Mathematical Ecology Smalle ofRNA Collaborations at the I 1 2 Santa Fe Institute Examples of communities Network World Wide Web Nodes webpages Edges hyperreferences Communities Nodes on related topics Network Friendship network Nodes people Edges friendship Communities Group formation among people Network Metabolic networks Nodes metabolites Edges participation in a chemical reaction Communities Functional modules Definitions of a community Cliques completely connected subgraphs Chain of cliques adjacent cliques share every node except one kclan diameter largest path length is s k Definitions using the edges inside and outside a presumed community k edges of node i that stay inside the community k t edges of node i that go outside of the community Strong community kiin 2 kiout for every node i in the community Weak community 2 kiinz 2i kiout where the sum is over nodes in the community F RadiCChi et al PNAS 101 2658 2004 Community Detecting Algorithms 39 Input A network Gnm 39 Output The number of communities Classification of nodes into these communities 39 Two families of methods Agglomerative bottom up Divisive top down Agglomerative method hierarchical clustering Calculate a weight connectivity measure W for every pair i j of vertices Example of weight number of nodeindependent paths between iand j Start with each node as a separate community Unite the highestweight node pairs Calculate the weights between the newly formed communityies as averages over the nodes in the community Repeat dendogram Divisive method betweenness centrality algorithm 39 Betweenness centrality of an edge is the number of shortest paths between pairs of vertices that run along it 39 Algorithm Calculate the betweenness for all edges in the network Remove the edge with highest betweenness Recalculate the betweenness for all edges affected by the removal Repeat MEJ Newman Phys Rev E 69 066133 2004 This algorithm also leads to a dendogram Q When is it most meaningful to stop Strength of communities To check if a particular division 0 is meaningful we can determine 0 C O 1 The fraction of edges within 3 0 the community divided by the fraction of edges from the community to outside of the community 2 The observed number of edges within the community divided by the expected number of edges within a community if the edges are distributed randomly 3 Modularity measure Q defined as the fraction of edges that fall within communities minus the expected value of the same quantity if edges fall at random without regard for the community structure For either measure the higher the result the better the proposed Commun39ty Strucwre M Girvan and MEJ Newman PNAS 99 2002 Modularitybased agglomeration If QO implies the division gives no more withincommunity edges than would be expected by random chance QgtO indicates a significant community structure Begin with each node in its own community Join two communities if that gives the maximum increase or smallest decrease in Q QT g is l gig go Label propagation a a a a d C d a d a a a FnedMn1984 pressures toward uniformity occur when there is a positively valued interaction between two personsquot Comns1988 within such highly cohesive groups individuals tend to have very homogeneous beliefs Label propagation algorithm Each node is initialized with a separate label is its own community These labels flood across the network following a certain condition Example condition join the community to which the most adjacent nodes belong Faster and as efficient as other algorithms UN Raghavan R Albert S Kumara PRE 76 036106 2007 Inference methods Prepare cDNA Probe Prepare Microarray l Probabilistic methods Clustering analysis Data mining Bayesian networks Deterministic methods Continuous Differential equations Discrete Boolean Four steps in clustering analysis Pairwise correlation analysis Timeseries data spatial data Gene coexpression network Clustering of genes Predicting proteinprotein interaction Drawback No insight into the causal relationship Pairwise similarities between expression profiles Pearson correlation Squared Pearson correlation coefficient Spearman rank correlation Jacknife correlation coefficient Euclidean distance Clustering algorithms Bottomup approach hierarchical clustering Topdown approach Selforganizing maps and K means clustering Expmsslnn rallo 339 39 1 a N m 5 Local clustering algorithm Relationships between expression pro les 4 4 I 3 3 E l g V 5 3i 0 39 g o V M 5 m 72 2 3 39 3 41 l 2 3 4 5 6 7 B 1 2 3 4 a l 7 9 D 1 2 3 4 0 7 D lime Time Time SiT39 tlltaneOUS Timedelayed Inverted Predict proteinprotein interactions Qian et al 2001 JMB 314 10531066 Height Height Height Oncogenic signaling network Glioblastoma data set1 n55 Construction of weighted gene coexpression network I l I based on painNise Pearson Glioblastoma data set 2 n65 correlations Hierarchical clustering to Illllll llllll IllillllllilllIlllllll llllllll quotMl detect groups or modules 9 Br ast Cancer data set n77 O IHHH iliHliIlIlIIIHHHIIHHHHHIIH H HIHiMHHIlIH Keyforab c I NEUVDQEHEEi5143 genes I I Metaboiism 143 genes MI c u l 185 m e W genes I Cytopiasm 1112 genes I immune Response 505 genes Horvath S 613 2006 103 174027 Elucidation of directionality Gene A 4 6209 B Gunvz C AGcne D E moww who Wu 9 M Z k 9 E 2 a x U i TinVD Tlm SR bVX bw 39 regression slopes nzu39 hm Mm J eg bw 1004 and bw 0976 Directionality is assigned to those edges forwhich SR a o l 0 1 w 1139 SR 7 2 yax 1139 SR e 1 quot e X Y ny 097 quot1w i quot rxi Gupta A et al 2006 22 209214 Data mining Extract information based on the statistical co occurrence Algorithm searched for the cooccurrence of pair of genes resulting in the edge generation according to the user defined threshold L Network retrieved by the query DNA repair 21 Bayesian networks These protocols are used for sparse datasets Probabilistic approach which is capable of handling noise The approach is based on the statistical properties of dependence and conditional independence in the data Estimate the confidence in the different features of the network Insight into the causal influence Bayesian analysis Bayes theorem PAB PBAPAPB or LABPA PB normalizing constant NC Posterior Prior Likelihood NC Steps in Bayesian analysis Define state of the system random variable known information Find conditional probability of each node Directed acyclic graph representation of possible causal relationships Conditional independencies 393 o IAE IBD l AE 393 3 ICADE l B IDBCE l A 0 DAG IEAD Continued Find joint distribution A set of local joint probability distributions that statistically convey these relationships The distribution yielding highest Bayesian score is chosen as the best fit to the data Benchmarks for weighting are typically obtained from likelihood G 0 HA B C D E PAPB A EPC BPD APE o o l l l 0 DAG Bayesian analysis produces multiple candidate networks 0 The links can be established randomly or heuristically lterative search algorithms are employed eg genetic algorithm Local map for the gene SVS1 Edge width confidence CLN2 and SVS1 are conditionally 39 lnependent given the expression level of CLN2 Friedman N etal 2000 J comp biol 7 601620 Deterministic Methods for Network Inference A deterministic inference correlates the rate of change in expression level of each gene With the levels of other genes by nding the functional or logical forms of these interdependence relationships Loosely Two classes of deterministic inference methods 1 Continuous 2 Discrete Continuous Methods Identified as systems of linear or nonlinear differential equations in which for example rate of change of expression oint is a linear combination of concentrations of all other Xt dX z N w X l dz 0 Pros and cons can be quite accurate accuracy increases as number of experimental time points increases computational intractability quickly becomes an issue Have been used to infer generegulatory networks in B SUbtiiS Gupta A Varner J D and Maranas C D 39Largesale inference of the transcriptional regulation of Bacillus subtilis39 Computers and Chemical Engineering 2005 29 pp 565576 Rat Chen T He H L and Church G M 39Modeling gene expression with differential equations39 Pac Symp Biocomput 1999 pp 2940 An Example Inferring generegulatory networks in B subtilis A Linear Model of Network Inference Microarray data Microarray data Xmrr N dt 21va To be soior w gt 0 gt activation of i by j w lt 0 gt inhibition of i by j Gupta A Varner J D and Maranas C D 39Largesale inference of the transcriptional regulation of Bacillus subtilis39 Computers and Chemical Engineering 2005 29 pp 565576 Optimization minimize W i Maximizing ka wifwquotf ij Sparseness subject to N T1 wij cJk Vki Wij Wj V1 122N k1 Post Opti mization Dense network Sparse network Discrete Methods Identified as Boolean and other logicbased methods that predict discrete regulatory relationships as for example Boolean A set of nodes V x1x and a list of Boolean functions F f1fn where a Boolean function f xi1xik with k specified input nodes is assigned to node X Example to follow in next slide Pros and cons More computationalIytractable than continuous methods Less accurate than continuous methods Much practical application is currently focused on developing and implementing algorithms for largescale inference eg REVEAL REVerse Engineering ALgorithm Liang S Fuhrman S and Somogyi R 39Reveal a general reverse engineering algorithm for inference of genetic network architectures39 Pac Symp Biocomput 1998 pp 1829 An Example Boolean protocol for network inference Boolean network basics A Boolean network GF consists of a set of nodes Vv1v representing genes and a list of Boolean functions Ff f A Boolean function fv1vk with inputs from specified nodes v1vk is assigned to each node v and this function gives the logical rules AND OR AND NOT etc for the ways in which nodes v1vk will affect the expression of node V The nodes of a Boolean network can take one of two states 0 not expressed or 1 expressed Thus the state of each node V at time t1 is determined by the states of its input nodes at time tand the Boolean function that dictates how these input nodes affect the expression of V A picture no inference yet GVF V1 V2 V3 RULES 11 v2 12 v1 ANDv3 v NOT v1 INPUT OUTPUT v1 v2 v3 V1 V2 V3 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 1 An algorithm for inferring a Boolean network Akutsu T and Miyano 8 Pac Symp on Biocomputing 4 1728 1999 1 For each node v e V execute STEP 2 2 If there is a triplet flWWW satisfying 01m fi1jvk1jvh for all j1m where OJ and I are state outputs and inputs take 2 as a Boolean function assigned to v and take vk vh as input nodes to v 2 Enumerate all triplets flvkvh satisfying Ojv f1jvk1jvh for alj1m What do STEPS 2 and 2 actually mean Not consistent Genesat An algorithmcontinued SOWe dreieCtit time 1 Genes at time t1 G 32 v v3 V V3 v v2 AND NOTv3 v z v2 XOR v3 v N0Tv3 v V we v3 Three Examples Conduct an exhaustive search to find these vkvh triplets All possible combinations of the 16 Boolean functions x AND y x OR y etc for the three node pairs v1v2 v1v3 v2v3 must be checked for each node This assumes that only two or less nodes determine the next state of each node Hybrid Methods Inference methods that bridge the gap between probabilistic and deterministic approaches usually by incorporating some type of stochastic process variability uncertainty into the inference algorithm Pros and cons Arguably most accurate and realistic network inference methods Amount of training data and computational time make methods prohibitive for large networks For Example Probabilistic Boolean Inference N Boolean functions are assigned to each node each with some probability of being selected to advance the state of the node a machinelearning algorithm must be used to update the state of each node at each time point The structure of cellular networks Tu pe aple te censtructand analyze a cellularnelwum we need te clearly denne wnat we ldennty as a nude and wnat we represent Wltn an edge Tne nedes and edges nave te pe at least slrnllarte eacn e ner e g represent ne same type UT cellularcumpunent pmtelrl cnernlcal ertne same type erlnteractlen rnass transren regulatlen We carl and ulten needtu de ne dllfererlttypes er nudes and ed es Gene mRNA proteln Protems Cellular funenons rely on the coordlnated senon ofgene products Interconnectlons between components are the essence of a 1 Life at the cellular level e pmmdesnuemretn cdlsandttssues e rkasmnle rnptnrs e sensecnerntcalstntneenvtmnrnat e duvechemmlracnuns e regulate gene Expresslm y e39e RR m s n tvtng process DavldGuadsellSuenueanalemw Cellular processes form networks on many levels Reaction networks nedes substrateslenzymes edges cnernlcal reac lens Regulatory netwonts mm m s Benesrpl telns edges translatlnn pr redulatlu actlyatlnd urlnnlpnnd Examples of cellular networks Prmelrl lnteractlen nablurks nedes pretelns edges pmtElrlrpmtElrl lnterac lens plndlng 2 Elecnernlcalreactlen netwurks e ernedes reactants substrates erpreducts crtne reactlens enz esecatalyze reactlens reactamrenzymecumplaC reactlurlrl edges needte rellectreactlens and alse catalysls regulatlurl ene pesslplllty dlrected edges nern reactantsenzymestu cumpla rrern cernplex te preductsenzyme gencirneWide prdtein interac icin rnaps Each bait protein can interact with a large number of prey proteins ua Aitndugn usuaiiy tested in a given All netwurks nave giant cunnected Protein interaction maps now contain thousands of nodes and edges itci yeast BEBE interacncins petween 32m pruteins uetz yeast MED interac lEIrlS 2ii5 prpteins GlutDrDsuphlla 47am interactidns arncing 4679 prdteins Ll c eiegans 5534imeracnuns anza prpteins Rual human 28nd lntEraEtlEIns damn prdteins paitprey semng prutein irteracticins are cdnsidered srnrnetncai Many untested irteracticins 7 problem cdrnpcinerts The tdpdidgicai prdperties cit diverse prdtein interacticin netwurks are sirniiar H a mi lam A a 2llll4i Degree distribution of C elegans and D Degree distribution of the yeast protein melanogaster protein networks network is a power law with exponential cutoff as D Drusuphllam C elegans m w WWW m l if m Pot k km em 13kquot PhAhquotIxP 39 w m H 4 The degree manhuan gels clusenu apuwa39rlaw as mare mmmmns are mapped l wlnlll 4141mm H 11m up Miaan r Average path length larger short cycles more abundant than in randomized networks a Comparison of yeast interaction networks Degreedistributiun Clusteringcuemcient Cunnectedcumpunents k Pkk39 yank Oltval and Earaba sl Prmeumlcszt 928 mm The bad news protein interaction maps are far Little overlap 4 be constructed by different Est coverage of Drosophila map is 21 quotquoti 3 Protein interaction networks are incomplete from perfect tween rnaps labs for c elegans it is 10 A H nybnd method are not biologically relevant false positives down assa 39 ese m ads are small scale and slow thus there is a need for War el ililiIC 443 lm IZOGJ prediction methods able to give a short list of candidates rods such as coimmunoprecipitation or coaf nity puri cation pull Not all interactions are simultaneously active Calculate the correlation between the expression timecourse of genes encoding the rst neighbors of hub proteins a Cumpcn lum n e 15 bs Two peaks two different types of hu Party hubs are inside connected modules that interact simultaneously Date hubs connect different modules v Lienle Networks of chenlical reactions rm nun iAmwAly Metabolism Sum of chemical processes e by which nergy is stored or releas Metabolic network Visualization Enzymes shown in blue coenzymes small molecules 1 WWquot 75gt qu awn necessary for enzyme activity in na zm products in black box indicates that annarn as r thCycL Ll m node appears in several locations Tri artite re resentation ofmetaholic network p p Reactlon Stolchlometry Rea mns ReacnunPathWa E y Stummumetn 3 g n 1 1 quot AE gtCD m MatnxS g a 71 n 71 MD E 2 g3 c 1 n 4 50 gtF a mg n 1 71 n Nudetypes g E n 1 7 MMahahtessubstratesarpmdnctsafznxectnnglzs g F n n 1 7 Na am unbetweenmetahahtes and caenzymzs sV Numperurmuxeeuxes m substrate pammpamg m yea mm 7 mmmeemyme cam zxeshhcknctangles s lt n W substrate Hsa reactartmreacnun 7 Enzymesapeme r sV gt n W substrate HS 3 product m reae mm 39 35 r 12 N msubstrates e 5mmmcamplzxmamplexmpmdw M ufreactmns uumns 7 Symmetrical edgesbetweenenzyme andcamplzx Network Representation r Bipartite Graph Network Representation r Substrate Graph R 2 R 71 R 3 Separate Graphf scrapn REEEUD Pathway M A A M a a M Reaemn Raman A B C D E F ME gtCD U A D E 2 E F Ma gtCD 1 50 7F 31 A D E 2 a 0 F a n n c c 1 2 3 gt one type urnuee Substrate Nude Subsme Nude gt Unmreetee Edges Substrate Graph gt Twu types m nudes B Ream Nude gt Each reacnun represented as a shame gt D rEEtEd Edges E F gt Nu mrect ares between names m Re sametype A WaunevKD FeH Pm Ruv Sue 25mm D C Network Representation 7 Reaction Graph Reac un Pa hway Reactmn Graph A a r G D m D 2 a c y F a gt one type urhuge I Reactmn Nude gt undirected egges An edge between WEI reacnuns if they share at east une substrate in summary Three arterhate nelwurk representatmns turthe sarhe reaenuh pathwayr arpartrte Graph A a r 1 2 3 Drreeteg Drecteg Reactmn supstrate Graph Wm Graph A a E F D c cphhemw sAbstvatesmheve exiss a r hs ruhere em 51 mp path inihe hwanne gpph path inihe hhpamte between them graph between them Key Properties of Metabolic Networks gt Metapuh netWEIrkS are scaierftee PM Pmbabmty that a grveh supstrate parrerpatesrh Kteactmns w 5 MW and nut gegree er supstrate huges rhthe prpartrte represehtatruh r k 152 PMUc u k4 2 gt Exrstehee Df hub supstrates such as ATP ADP NADP NADPH carherMetapuhtes ppm 3 A mm a r Ecdr e c e u Jun1 p at quotInquot 11551 mm M W s Distances in Metabolic Networks Pa hs gerheg tn euhheet edutts tn pmducts the aerage rs caieuiateg uh the reachapie parrs Dniy Drstahee grstrrputruh Diimuw Average gegree and on and m N p Reiatrveiy srhau and u hsta39rt neIWEIrK grarheter aeruss urgahrsrhs u Jenna put umme 551 mm Clusteringdegree relation in metabolic networks 6 quotaquot D mum Average clustering coef cient of nodes with degree k Open symbols a model with the same degree distribution Straight line Ck kquot r 39n iii a in mm m k m m k Ravasz et al Science 2971551 2002 No modularity Modularity Model of hierarchical modularity E Ravasz at al Science 25171551 71555 znnz Degree distributions in metabolite and reaction networks h h ank vs degree plot similarto PkgtK The degree exponent yslope1 lul riii metabolites r All mullahs it i mantlan modules page ouuiu 2 Undirected substrate network Undirected reaction network Tanaka Phys RevLett 94 168101 2005 Gene regulatory networks immiuiuoi Intlellm manning ia Nlhn r 1 o nooes genes circle rnRNAs ovals proteins boxes eoges rnass flow continuous or regulation oasneo regulatory eoges acting on edgesr sirnilar to catalysls eoges can be actlvatlrlg or innioiting Simpli ed representation for gene regulatory networks m Outdegree distribution long tailed indegree distribution more limited 2 l E39l il x Direct modulation towards l g quot gx product I e TF mRNA 3 39 39 4 edge or protein modi ed E i protein edge quotwe i 39 General meaning of p 39 45 Twig 39 edges positive or W g3 d nuny on e rec negative information g m Why 15 m g g propagation E Need rules for combining g a 2 n 59 several regulatory effects 3 ssn 1H1aw iir W39Wm Numbnro39Fmrwlelegianl 5mm 39 min12 m Gueizim et al Nature Genetics 3 l l 60 2002 S Lee at al Scienct 298 793 2002 cerewsme 39 Re ulato themes R tram res Regulatory motlfs g W P W Interaction H seq homology Mus mama 5414 me s e Feedforward v an 39 Regulators TF5 blue circles 7 Genes red rectangles Co ointin Dashed edges mean p 9 WW translation Lee cial SLlcliEcEQE 79010021 Coregulation d Protein complex l lemngetal J Biol I 53005 gimme im in i om gimamnin 3 Min 9i i mil 9 al Haunt 4M 02 Conditiondependent transcription subnetworks miiw m zf w 2 i2 i 3 39i l x 531231 523 1 lg nmti 3 ninrii I m39nl Representation of chemical reactions regulation irreversible quotI X gtX reaction axr gtxga Coenzyme reversible x gtX reaction X x dwergence XV mi positive modulation gt x x X E c ne ative odulatio convergence xl x gtx g m n x two reactant reactions xv X autoinnioition E o Vail Computational Analysls oraiochemicai Systems ABA signal transduction network Red enzymes Signal transduction pathways Proteinprotein interaction network Static picture Mapping signaling pathways Spatial information Mapping motifs and patterns during signal propagation Pseudodynamics Analyzing signal processing through networks namic modeling Mapping signaling pathways i WI nmmw n Valm mm mum 1 iilh Von o y 9 r t n y i y g V i 39 x a mum imam w a maquot inwmlm Yalctn Arga etal Biotech and Bioeng 2006 Signal transduction network of the hippocampal CA1 neuron Data binary interactions collected form the experimental llerature System of interacting cellular components involved in phenotypic behavior Edges can be directed or undirected neutral Directed edges are activating or inhibitory Transcription a acmriEVY ta Translation iachlneW sat Ma ayan et al Science 309 1078 2005 Build suhnetworks that start at a speci c ligand Signal propagation can he traced hy looking at links per step LIGAND aggk STEP 1 A STEP 2 Ion CHANNEL V Fast change 7 Permanent change Motif abundance homeostasis and plasticity POSITIVE AND quotram rmm OOPS A BIFANS N POSITIVE AND NEGATIVE rimrme OOPS A scarrmns A Rapidchange ligands engage more motifs in fewer steps At early steps more FFL than expected at later steps more FBL than expected Looked at three key regulators of plasticity 1 Motif counts increase linearly with steps for all regulators prdu mtial paths to key effectors 2 Positive and negative motifs are balanced for glutamate and BDNF homeostasis 3 More positive than negative FBL and FFL in NE long term info storage Benchmark 1 regular lattices IN k tnnxtC mm Network models Onerdlmenslunal lattlEE Prupenles drhrhdh m rhahy largerscale NEDlurks lrldEpErldErltly pr thelrdrlglh ahdmhctldh l The degree hd petweehhess dlsirlbutl rl are decreaslhg Tdelrhehsldhal lamce furlEtlEIrlS usually puwerrlaws l c E 2 The dlstahces scale luganthmlcally Wlth the rlEtWEIVk slze 1 Lu 1v lagN 7 small wurld k 6cunst funnsldenud s depehd uh he 6 c cunsr funnsldenudes 15 I u 100 3 THE lusterlng EDEl flElErlt dEIES nut SEEN etwurk SlZE ahd ls larger hah the ElustEng cdemclem at p DrdlmEnSanal lamce EDDrdlnatlDrl Number Eunstant ElustErlng h cdrhparaple rahddrh gra hs Curlstarlt degree rrlcleht Small wurld netwurk rhddels ahd scalerfree hemdm rhddels Benchmark 2 random graph theory Path length and order in real networks In N k ErdOSrRe39rlyl algorlthm r F ubl Math DEblELEn s ZBUll JEBl rlxed hdde hdrhperrv 39 39 cdhhec1lhg palrs err hddes Wllh prubabllltyp x lavltkgt en pn1 pa Expected degree dlsmbull rl 1 th C dp UIIW 17 lagN Expected pa h length m lag rl a N 9 Real rlEtWEIVkS have shun dlstahces llKE rahddrh graphs yet shuw Expected ElusiEng cdemclem Cmp N s gns Emma my Transition from a lattice to a small world Smallworld networks Real networks resemble both regular lattices and random graphs r r gt perhaps they are in between 1 v l 5 ii ctpi ctoi WattsStrogatz model D Watts 8 Strogatz Nature 393 440 1998 mar l quot lattice with K neighbors 3 i 39 Llpil LID 39 i oreWIre edges With quot239 H r J probabilityp 3 l 39 39 39 quot g I39IE U llIi lilJl iI39 I i 39 0 11 cam 1 logNy c lattice small world random 2K 4K 1 logK N There is a broad interval of p over which Cp C0 but 10510 Is there a regime wi h small land large C The onset 0f the small39world behav39or Degree distribution of a smallworld depends on the system size network Nmz d is the dimension of NJ fpKN the lattice ReWIring does not change the average degree but K modifies the degree distribution cam39tifu ltlt 1 lattice like k K u f I39mu 1fugtgt 1 random graph like Pk depends on the rewiring parameterp but is The transition point depends on the rewiring probability aways centered around ltkgt the size of the network and the average degree C11 C01113 Degree distribution similar to that of a random graph WI h These results cannot be directly compared to most real networks exponentially small probability for very highly connected nodes because the rewiring probability p is not known rhddei the evuiutrdh DantWEIVkS hdtrdsttherrtppdidgy A simple model of network assembly and volution BA model startWrth a small seed err rhhddes ahd rhrh42 edges growth a nude and rh edges added at everystep I preferential attachment 110 21quot Prreeu Arher Sn ihrdrrh Sci 27 292 1976 Earapasr ahd Alpert serehee 286 any man General properties ofthe network nr of nodes N mu 4 7 nr ofedges EEWert 2E Q t average degree k 7 gt 2m E 1 degree distribution Pk WAX Although the network grows he degree distribution becomes stationary Analytical determination of Pk The degree of old nodes increases by acquiring n edges The probability of an old node with degree k is ew receiving a new edge m17km k N k 2 kl 2t 1 withprob 5 Degree Increase 22 0 otherwise Choices follow the increase in the number of nodes with degree k rate equation approach follow the increase in time in kcon inuum theory Rate equation approach Change in average number of nodes with degree k k1 gt k kt k1 4N k7 N 2 4m 2 dtk mMJV 5W rst node number of edges normalization w nod Pk NktNlmektt Plug in Pk m ki ngkjp ggf kvAJr 6k m ltkgt Degree distribution r i and Pk 1 Pkk71Pk1rkPk6m nk 1 forkm Pk z forkm ml Leads to Pk 2quot quot 1 kquot kk 1k 2 Stationary power law with an exponent 7 3 P KrapivSW S Rednei F LeWiaZ Phys Rev Lett 85 4629i2000i Ex 1 Start from a seed of two nodes connected by an edge At each step add a new node and connect it by a single edge to a preexis ing node Let the probability of selec ion be directly propor ional with he degree ofthe old node Is there an easy way to do this Continue growing the graph until you reach 15 nodes Describe he graph average degree degree distribution clustering coefficient connec ivity maximum distance Ex 2 How will the properties ofthe graph change if at each step a new node and two new edges are added Model A growth l39lk uniform zm q m dt m0t 1 g k PM iexpr 7 Characteristic degree scale m Model B M preferential attachment Fixed N edges connect a randomly selected node with a preferentially selected node dk I N k I A17kx 0 dt N N712t N 2 5 ltkgt2mt N tn Pk power law initially 2 Gaussian M lo 1039 k a l BA algorithm with directed edges New edges are directed from the new to the old nodes mi 1 I ktquott m f0rigtm0 4 kfquot varies l L 3 ltkmgtm dkm km km i 17 km i i 7 dz H my I Pmkk2 The degree exponent of the directed scalefree network is 2 How do the other network measures 10 Average path length compare with real networks Clustering coefficient El random graph clustering coefficient 2 o C lnN Odynam c scalefree model random graph Average distances smaller in the BA model than in equivalent random graphs but not as small as in scalefree random graphs Cohen et al in Handbooks of Graphs and Networks 2003 Clustering coefficient decreases with network size B Bollobas and O Riordan in Handbooks of Graphs and Networks 2003 Evolving network models The scalefree model is only a minimal model Makes he simplest assumptions lineargrowh ltkgt2m proportional preferential attachment Hag 0c ki Does not capture variations in the shape of the degree distribution variations in the exponent ofthe powerlaw region the sizeindependent clustering coefficient Hypothesis the basic mechanisms need to be augmented by the incorporation of addi ion of edges without new nodes edge rewiring removal node removal constraints or op imization principles Preferential attachment in real networks citation neurosci 4 39 A 10 xkzHK Kltk 7 Internet no pref attach linear pref attach 139IkAk asl actor collab Consequences of nonlinear preferential attachment Hk Akquot 6131 A initial attrac iveness 1 Sublinear preferential attachment leads to a stretch exponential degree distribution Pk s exp kko I P Krapivsky S Redner F Leyvraz Phys Rev Lett 85 4629 2000 2 Initial attractiveness only shifts the degree exponent A 7m 2 directed network starting point is 2 Dorogovtsev Mendes Samukhin Phys Rev Lett 85 4633 2000 Mechanisms for preferential attachment i Cupylng inecnanisin directed netwurk seiect a nude and an edge drtnis ndde attacn tn ne Endpulnt crtnis edge 2 Walking an a netwurx directed netwurx tne new ndde cdnnects td a nude then td every rst secund nelghburufthlsriude a Attacning tn edges seiect an edge attacn tn ndtn Endpuints drtnis edge 4 Nude ddpiicandn ddpiicate a nude With aii its edges Vandumly prune edges cit new ndde Growth constraints and aging cause FlnltE iitetiine tn acgdire new edges quotmineiiim ts L A N Amaral etal PNAS an l ilwa Gradual aging nag k1 g ylncreasEszth v s N DnmgnvtsevandJ r F Mcrideaiphvs Rev E51184 mun Additional processes also change the degree exponent mp new edges Pk 11k0quot km Again mq edges ieWiied F39 Aineit AVL aaianasi Plivs PEV Leti Kai amizntim c edges added DrrEmWEd 1 27 7quot 12 s N DDYDEDVISEViJ r r Memes Eumpnvs Letl 52 aatznnui A model with high clustering coef cient Each ndde drtne netw m can be eitneractive ur inactive rneie are unly m ac lVE nddes in tne netwurk at any instance 5 g 2 5 s z 5 quot5 z ll tk t11398quot Ukak Pk 15quot K Newman1V Egdllul ths F39PV E55 dam mull A deterministic scalefree model Start with a completely connected graph with ve nodes one central four perip er a e four copies ofthe graph keep the original in the center Connect the four peripheral nodes of each copy to the central node ofthe original Make four copies ofthe graph again connect peripheral nodes to the central node 3 5clique A deterministic scalefree model 39 5clique connect peripheries to centra E Ravasz A L Barabasi Phys Rev E 67 026112 2003 Ex 1 How does the number of nodes increase as a func ion oftime steps Ex 2 How does the degree ofthe central node increase in time Ex 3 How does the number of edges increase as a func ion oftime steps Ex 4 Can you identify the highest degree nodes Prnnerties of the model E a Um ta in39 in1 in N l lnln3 Degree distribution 1quot1 c k Clustering coef cient C is 06 independent of network size Hierarchical structure cl Average clustenng coerncrent or nodes wrtn d Also ooserv egree ed lrl varlous Cellular networks 7 Slgrl of nlerarcnlcal re modular arcnltedu E Paves at al Sclence 297 lssl znnz u t n rnnn Lessons learned from evolving network 4 mode s Tnere rs no unrversal ekponent cnaracterlzrng all networks Tne ongrns ortne prererentral attacnrnent rnrgnt be System dependent lt rs generallv true tnat networks evolve Modellrlg real network ld s entrrv ne processes tnat plav a role rneasure tnerr rreouencv rrorn real data develop dvnarnrcal rnodels tnat capture nese processes Discrete dynamic modeling of biological systems The functional form of regulatory relationships and kinetic parameters are often unknown Increasing evidence for robustness to changes in kinetic parameters bistability two steady states Hypothesis the kinetic details of individual interactions are less important than the organization of the regulatory network Discrete dynamic models assume that nodes can be characterized by only a few minimum two discrete states Discrete models can handle larger networks than continuous models Boolean modeling of biological systems Main assumption components have two main states Expressed or not expressed active or inactive open or closed ion Channel high or low level Denote these states by ON 1 or OFF 0 The changes in state are given by discrete logical rules The future state of a regulated node the output depends on the current state of its regulators inputs which may or may not include its own current state eg lf transcription factor is active gene will be transcribed gene will be expressed in the next time step Boole logic based on the operators NOT AND OR Can be defined based on set intersection and union or inputoutput relations gates truth tables Truth tables for Boolean operators NOT AND OR n1 n2 Out n1 n2 Out In Out 0 O O O O O 0 1 O 1 O 0 1 1 O 1 O O 1 O 1 1 1 1 1 1 1 Out NOT In Out n1 AND n2 Out n1 OR n2 In Out quot 1 quot 2 Out ln1 ln2 Out 0 1 0 0 0 o o o 1 o 0 1 0 o 1 1 1 O O 1 o 1 Out NOT In 1 1 1 1 1 1 Outn1 AND n2 Outn1 OR n2 Ex 1 Give examples for the realization of these Boolean rules in a gene regulatory network Ex 2 Consider a transcription event activated by a transcription factor Compare the continuous and Boolean description of this process From doseresponse curves to aimat with xleol Boolean switches VII 1 llfll M X mRNA Y transcriptional activator If v is large the doseresponse curve becomes a switch If YgtKY dXdtgt0 If YltKY dXdtlt0 The activation threshold is KY If activation is weak mRNA can decay Boolean simplification X Y Activation If YON XON Decay If Y OFF XOFF Hybrid models Boolean regulation combined with continuous decay Each node is characterized by both a continuous and a Boolean variable d A 28 X X X dt 1 2 z o X is defined by the threshold rule Q H ltw L H gtos i 1 quot Compared to EX Tmpg T sir this assumes d KFF Hx constant activation threshold05 maximal synthesis rate decay rate 1 L Glass 8 Kauffman J Theor Biol 39103 1973 Implementing time in discrete models 1 Synchronous models The state of each node is updated simultaneously at multiples of a common timestep Thus the future state means the state at the next timestep Underlying assumption the timescales of all synthesis and decay processes are similar 2 Asynchronous models The state of each node is updated individually Implementations k Different update time for each node 7 k7i Select a random update order in each timestep Tlquot1 Nk W i where is a permutation of the nodes Synchronous models have deterministic state transitions asynchronicity introduces stochasticity update order dependence in the dynamics Boolean models of signaling networks Start with a known or reconstructed network The directed edges in the network indicate regulator target pairs Assume that the state of each node can be 0 or 1 o The rule giving the new state of each node is determined by a Boolean function of the states of the nodes that regulate it Choose between synchronousasynchronous update Start with a known or assumed initial condition The state of the whole network changes in time Identify the attracting states or behaviors of the system Ex 3 Construct a network of three nodes such that their indegree is one or two Associate a Boolean rule to each node Assume that each node s state changes at the same time synchronous update Start with an initial state and update the state of the nodes 10 times What is happening to the state of the network Start from a different initial state Is the final behavior be the same How many different fina statesbehaviors can the network have I I I o 1101 0 0 0 1 I39I o39I I D I I I o o 0 0 o o I I suomsueJi 91218 edwex3 Concepts in Boolean network dynamics Attractor a set of states that repeats itself in afixed sequence can be periodic or a fixed point Fixed point Future State Current State Previous State All states lead to or are part of an attractor Basin of attraction all states leading to a given attractor In a network of N nodes the maximum possible length of a periodic attractor is the total number of states 2N In practice the period length of the attractor is much shorter than this maximum Cause many nodes become frozen due partly to canalizing functions an attractor state shown in detail Iquot transient tree E and sub trees 3 Andy Wuenche wwwddabcom Canalizing forcing functions At least one of the inputs has the property that the output is fixed if this input has one particular value eg a AND b is canalizing because a0 implies a AND b 0 Ex 4 How many twoinput Boolean functions are there How many of them are canalizing Ex 5 Consider a network of four nodes Node A is the signal the Boolean rules of the other three nodes are the following BAorC CAand notD DBandC SetA0 a Assume that each node s state changes at the same time synchronous update Start with an initial state and update the state of the nodes 5 times What attractor did you find b Now start from the same initial state but update the nodes one by one such that each node is updated in each step in a different order Is the result the same Q How can you determine the fixed points of a Boolean model without performing updates In the fixed point time does not matter thus the transfer functions become equations BAorC CAandnotD SolutionA0B0C0D0 DBandC Asynchronous models have the same fixed points as synchronous ones Ex 7 Consider a the same network of four nodes BAorC CAand notD DBandC Set A 1 Assume that each node s state changes at the same time synchronous update Start with an initial state and update the state of the nodes 10 times What attractor did you find Is it the same as for A 0 Attractors for synchronous and asynchronous models Synchronous The analog of a periodic orbit in a synchronous model is a strongly connected component in state space in an asynchronous model Harvey T Bossomaier Proc ECAL97 67 1997 Integrating the Boolean rules into the network The future expression of a node depends on a combination of the expression of other nodes CIR hh EN and not CIR 7 EN EN ECR 5 Introduce complementary nodes gt Tlt5CIR CIR 5 not CIR hh hh Associate pseudonodes to node combinations E5 5 EN and CIR The future expression of nodes depends on the expression of pseudonodes hh ECR CIR 9 Ex 8 construct the augmented network for Ex 5 Use different styles for edges ending in pseudonodes Boolean modeling of gene regulatory networks in the absence of data Cell differentiation is based on differential gene expression Genes regulate each other s expression Stuart Kauffman 1965 Ideas genes can be modeled by onoff switches the structure of the gene regulatory networks is unknown the regulatory functions are unknown network states correspond to cell types The Kauffman NK model Construct a network where each node s indegree is K Assume that the state of each node can be 0 or 1 o The state of each node is updated at each timestep The rule giving the new state of each node is determined by a random Boolean function of the states of its regulators Find the attractors of the network states The number of attractors corresponds to the number of possible cell types How does the number and type of attractors change with N and K Attractors in Kauffman networks For K1 networks are frozen median number of attractors is close to 2N median cycle length close to 1 o For Kgt5 networks are chaotic few attractors median cycle length close to 2N For K2 interesting level of order median number and length of attractors both scale as N This is fairly similar with the number of cell types in different organisms Stability of Kauffman networks What is the effect of a mutation changing the state of a randomly selected node If the final number of changed nodes is small frozen network Percolating changes chaotic network The threshold between order and chaos is K2 One can bias the Boolean functions so there are more of Os or 1s 1 c 2Q1Q Then the threshold varies with the bias Q as K Ordered behavior for kltKC Does the threshold behavior apply to non regular networks Order 2Q1 QK lt 1 This relation is maintained if the underlying network is ER with ltkingtK Q How does this compare with the threshold of a large connected component 100 Does the threshold behavior apply to non regular networks 1 For scalefree networks a With PkZk1 the 115 the condition becomes Q DA V Chanti M Behayinr Enhult 2Q1 QZ7 1 lt 1 39 Z 7 a 39 15 1 115 2 25 3 35 4 39r Scalefree networks with y gt 25 I are robust to random perturbations M Aldana P Cluzel PNAS 100 8711 2003 As we find out more about gene regulatory networks it is not necessary to assume random topologies and regulatory functions anymore It is still interesting to see how successful an ONOFF framework and Boolean logic can be as compared to chemical kineticsbased models Example Boolean modeling of the segment polarity gene network Continuous G von Dassow et al Nature 406 188 2000 Synchronous Boolean R Albert H G Othmer Journ Theor Biol 223 1 2003 Asynchronous Boolean M Chaves R Albert E Sontag Journ Theor Bio 235 431 2005 Continuous Boolean hybrid M Chaves E Sontag R Albert IEE Proc Systems Biology 2006 Idea generate random graphs with a powerlaw degree distribution Fixed N Pkk397 Configuration model choose a degree sequence NkN Pk give the nodes k stubs according to Nk connect stubs randomly Ex 1 Construct a graph with 10 nodes and degree sequence N14 N23 N32 N41 What is a necessary condition for the graph construction
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'