Network Archaeology: Uncovering Ancient Networks from Present-day Interactions!!Saket Navlakha!!Department of Computer Science!University of Maryland, College Park, USA!!Joint work with Carl Kingsford!Yeast PPI network:! 2,599 proteins! 8,275 interaction edges!Did these proteins interact 10 million years ago?!How have these protein complexes reconfigured over evolutionary time?!Which model of evolution best characterizes the structure of this network?!Last.fm social network:! 2,957 users! 9,659 friendship edges!When did this user enter the network?!How do growth principles of social networks differ from those of biological networks?!Who recruited these users to join the network?!How are networks changing over time?!yeast!worm!fly!human!Difficult to study in biology because we do not have access to ancestral networks!!Extant networks are insufficient to track fine-level changes:!1 billion years – widely separated in time!?"?"?"?"Difficult to study in sociology if networks are not crawled regularly or if data remains hidden (privacy issues)!(2010)"(2002)"What can we do with ancestor networks?!Estimate the age of a node or a edge!1"3"4"5"2"Track the emergence of clusters and motifs!t"="100"t"="500"Validate growth models by comparing histories!Privacy implications of predicting user activity!DMC"PA"FF"ER"✔"✗"✗"✗"Actual!Predicted!Networks vs. sequence view of evolution!Truth"Networks"Sequence"Down-sample to create realistic & smaller network!Challenge:)Given)a)present1day)network)G)and)a))probabilistic)model)by)which)G)putatively)evolved,)can)we)reconstruct)an)ancestral)version)of)G?)Related work!* Do not handle node labels:!– Leskovec and Faloutsos (ICML 2007) and Hormozdiari+ (PLoS Comp. Biol. 2007) find seeds graphs (putative ancestral subnetworks) under the Kronecker and a duplication-based model!* Do not model the evolution of interactions over time:!– Flannick+ (Genome Res. 2006), Kelley+ (PNAS 2003), and Singh+ (RECOMB 2007) align multiple static networks to find conserved substructures!* Do not reconstruct ancestral networks:!– Middendorf+ (PNAS 2005), Wiuf+ (PNAS 2006), Bezáková+ (ICML 2006), and Leskovec+ (KDD 2008) compute the likelihood that a growth model produced a given network!!* Do not apply to general graphs:!– Dutkowski+ (Bioinformatics 2007) and Gibson and Goldberg (PSB 2009) use the history encoded by the gene sequence phylogeny to reconstruct ancient networks!– Ahmed and Xing (PNAS 2009) use node attributes (e.g. gene expression, Senator voting patterns) to recover a hidden underlying static network!– Mithani+ (Bioinformatics 2009) use principles from metabolic networks to model edge gain & loss amongst fixed set of nodes!Network growth models!Barabási+"(Science&1999)"node)v)chooses)anchor)u,)starts)probabilistic)fire,)links)to)burnt)nodes)v)u"Forest Fire!Preferential Attachment!1 ""2 ""3 ""4 "5"Degree)distribution:)1"3"4"5"2"v"new)node)v)links)to)k)existing)nodes)according)to)the)histogram)Leskovec+"(KDD"2005)"Popular technique to study how graph properties evolve under various growth mechanisms!Duplication-Mutation with Complementarity model!A biological growth mechanism that closely characterizes PPI networks1,2,3"1Vazquez+"(Complexus&2003);"2PereiraQLeal+"(Phil.&Trans.&R.&Soc.&Lond.&B.&Biol.&2006);"3Middendorf+"(PNAS&2005)"Step)1:)Node)v)enters,)chooses)random)anchor)node)u,)and)copies)its)links))Step)2:)For)each)neighbor)x)of)v,)delete)either)(u,x))or)(v,x))with)prob.)qmod))Step)3:)Add)edge)(u,v))with)prob.)qcon)v"u"Step"1"v"u"Step"2"v"u"Step"3"BUT:)the)growth)model)produces)a)random)and)unlabeled)graph)whose)history)does)not)correspond)to)the)history)of)a)real)network)Network archaeology!Main idea: reverse a network backwards in time as per the model!a"b"c"e"f"d"g"ab"cg"efd"Duplication-based (DMC)!Preferential Attachment (PA)!Forest Fire (FF)!Erdös-Renyi (ER)!Watts-Strogatz!Network"Model"…!Ancestor graph at time t-4!✔"models interactions!✔"maintains labels!likelihood estimate!✔"Input graph at time t!G∗t−∆t:= argmaxGt−∆tPr(Gt−∆t| Gt, M, ∆t)DMC"model"presentQday"network"ancestor"network"Zme"steps"Given Gtand DMC, find the most likely precursor network,G∗t−∆t:G∗t−∆t:= argmaxGt−∆tPr(Gt−∆t| Gt, M, ∆t)DMC"model"presentQday"network"ancestor"network"Zme"steps"Find:"most)likely)path)of)graphs)(G1,)G2,)…,)Gt&1))that)produced)Gt)under)DMC'Gt'Gt&1'Gt&1'Gt&1'…"……)G1'G1'G1'G1'HighQlikelihood"path"≥ n≥ n − 1Given Gtand DMC, find the most likely precursor network,G∗t−∆t:BUT:)number)of)possible)paths)is))Ω(n!)G∗t−∆t:= argmaxGt−∆tPr(Gt−∆t| Gt, M, ∆t)DMC"model"presentQday"network"ancestor"network"Zme"steps"Given Gtand DMC, find the most likely precursor network,G∗t−∆t:prior"probability"(uniform)"ignore"denominator"(constant"over"all"candidates)"Bayes’"rule"G∗t−1:= argmaxGt−1Pr(Gt| Gt−1, M) Pr(Gt−1|M)Pr(Gt|M)Instead, set ∆t = 1, greedily approximate:What is the likelihood that u is a duplicate of v?!Prob. that u was chosen as v’s anchor!Common neighbors of u and v !(no divergence)!Symmetric difference !of u and v (divergence)!qcon if (u,v) exists!1-qcon else!E.g:"u)v)⇒"Gt)uv)Gt11)(1 − qmod)2(qcon)In each step, merge the pair with the highest likelihood of duplicating:!argmaxu,v∈GtLDMC(u, v)(qmod2)21n − 1LDMC(u, v)=1n − 1�N (u)∩N (v)1 − qmod�N (u)�N (v)qmod2(γuv)Synthetic DMC experiments!Repeat 100x!Assess performance when evolutionary history is known!!Store"known"node/anchor"phylogeny"and"node"arrival"Zmes".".".""DMC(0.1,0.1)DMC(0.1,0.3)DMC(0.1,0.5)DMC(0.1,0.7)DMC(0.1,0.9)DMC(0.3,0.1)...DMC(0.9,0.9)100 graphs, 100 nodes eachReverse Gt=100Compare historiesSynthetic DMC results!Better ordering with low qmod (less divergence) and high qcon (connected to anchor)!50-60% of node/anchor relationships correctly identified!Randomly replace 10% of true edges in Gt=100!Recovery of ancient PPI networks!Started only with extant PPI network for yeast!!Validating arrival times: older proteins have orthologs in more eukaryotic species – COG age class1"!1Clusters"of"Orthologous"Genes,"Tatusov+"BMC&Bioinforma=cs&2003;"2Ispolatov+"NAR&2005;"3PereiraQLeal+"Genome.&Biol.&2007.&Evolutionary principles reflected in best DMC parameters: med-low qmod = 0.4, med-high qcon = 0.7 (new proteins are usually connected to their duplicates2,3 and share some interaction partners) !!Result: The