Network Archaeology: Uncovering Ancient Networks from Present-Day Interactions

Thursday, March 1, 2012 - 4:00pm - 4:15pm
Keller 3-180
Carl Kingsford (University of Maryland)
Many questions about present-day interaction networks could be answered by tracking how the network changed over time. We present a suite of algorithms to uncover an approximate node-by-node and edge-by-edge history of changes of a network when given one or more present-day networks. The algorithms use either a plausible probabilistic growth model or an assumption of parsimony. From the reconstructed history, we model the arrival time of extant and ancestral interactions and find that complexes have significantly re-wired over time and that new edges tend to form within existing complexes. We also hypothesize a distribution of per-protein duplication rates, track the change of the network's clustering coefficient, and predict paralogous relationships between extant proteins that are likely to be complementary to the relationships inferred using sequence alone. Finally, we infer plausible parameters for the model, thereby predicting the relative probability of various evolutionary events.

Joint work with Saket Navlakha, Rob Patro, Emre Sefer, Justin Malin, and Guillaume Marçais.