Alladi Ramakrishnan Hall

Graph Algorithms for Dissecting Gene Networks in Health and Disease

Manikandan Narayanan

NIAID, National Institutes of Health, Bethesda, MD, USA

High-dimensional datasets are routinely generated in
biological sciences (protein interaction, gene expression, and DNA/RNA
sequence data, to name a few), stretching our ability to derive novel
insights from them, with even less effort focused on integrating
disparate data available in the public domain. Hence a most pressing
problem in life sciences today is the development of algorithms to
combine large-scale data on different biological dimensions. The
natural computational problem in these settings is to find sets of
nodes (genes) that simultaneously form well-connected clusters in
diverse networks (defined using different edge sets over the same set
of nodes). In this talk, I intend to present graph algorithms for this
problem using different quality measures like connectivity and
conductance, and show how certain biologically-inspired matching
criteria offers tractable alternatives to previous NP-hard
graph-matching problem formulations. These generic algorithms could
have applications beyond biology in other data science fields as well.

This work is supported by the intramural program of NIH.