DateNovember 3, 2006
SpeakerNagiza F. Samatova (Oak Ridge National Laboratory)
TopicScalable 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.