COMPUTATIONAL RESEARCH in BOSTON and BEYOND (CRIBB)

Date	November 3, 2006
Speaker	Nagiza F. Samatova (Oak Ridge National Laboratory)
Topic	Scalable Graph-Theoretical Approaches to Biological Network Analysis
Abstract	Many biological objects are naturally represented as graphs. Examples include metabolic, signaling and regulatory pathways, protein interaction networks, and chemical compound graphs. The elucidation of genome-scale structure-function relationships between these objects necessitates the development of more efficient and effective methods for the comparison of their underlying graphs. We present scalable graph-theoretical approaches to this problem including graph matching, maximum clique finding and maximal clique enumeration. Performance benchmarks on advanced hardware architectures will be presented. We will provide a number of examples where these algorithms have been applied to address important biological questions.

Acknowledgements

We thank the generous support of MIT IS&T, CSAIL, and the Department of Mathematics for their support of this series.