Topic:
Fast Methods for Finding Colored Motifs in Graphs

Motif discovery is the problem of finding subgraphs of a network that appear surprisingly often. Each such subgraph may indicate a small scale interaction feature in a genomic interaction network, a significant relationship involving rock musicians, or insight into any other application that can be represented as a network. We look at the problem of constrained search for motifs based on colors (e.g. gene ontology term or musician type for those examples). This talk presents a brief review of the state of the art in motif finding, re-engineers the gTrie data structure from Ribeiro et al to support colors, then discusses how to tackle the “surprisingly often” part of the problem by extending the work of Picard and Schbath to replace random simulation by analysis. 

Joint work with: Alfredo Ferro, Rosalba Giugno, Giovanni Micale, Misael Mongiovì, and Alfredo Pulvirenti.

Bio

Dennis Shasha is a professor of computer science at the Courant Institute of New York University and an Associate Director of NYU Wireless. He works with biologists on pattern discovery for network inference; with computational chemists on algorithms for protein design; with physicists and financial people on algorithms for time series; on clocked computation for DNA computing; and on computational reproducibility. Other areas of interest include database tuning as well as tree and graph matching. 

Because he likes to type, he has written six books of puzzles about a mathematical detective named Dr. Ecco, a biography about great computer scientists, and a book about the future of computing. He has also written five technical books about database tuning, biological pattern recognition, time series, DNA computing, resampling statistics,  and causal inference in molecular networks. He has co-authored over seventy journal papers, seventy conference papers, and twenty patents. He has written the puzzle column for various publications including Scientific American, Dr. Dobb’s Journal, and the Communications of the ACM. He is a fellow of the ACM and an INRIA International Chair.

Back to the Summer School 2016 overview