Happy Wheels Krunkerigri Araba Oyunu
Seminars
Back
Topic: Shotgun Assembly of Labelled Graphs
Date: 15/12/2015
Time: 2:30 p.m. - 3:30 p.m.
Venue: Lady Shaw Building (LSB) Room C1
Category: Seminar
Speaker: Professor Nathan Ross
Details:

Abstract

We consider the problem of reconstructing graphs or labelled graphs from neighborhoods of given radius r. The question of inferring a graph is a generalization of the DNA shotgun problem where the graph is an interval and the nodes are labelled by A, C, G, T. The graph shotgun problem is motivated in part by applications in neuroscience. We provide some necessary and some sufficient conditions for correct recovery both in combinatorial terms and for some generative models including Ising model on lattices and Erdos-Renyi random graphs. Joint work with Elchanan Mossel.

PDF: 20151215_ROSS.pdf