Community Discovery and Analysis in Biological Networks

Jianhua Ruan, Ph.D. Candidate
Department of Computer Science and Engineering
Washington University in St. Louis

Abstract

Many complex systems can be represented as networks, where the nodes are the elements in a system, and the edges represent relationships between pairs of elements. Examples include social networks, protein-protein interaction networks, and the World Wide Web. Much effort has been devoted to the study of topological properties that seem to be common to many networks, such as the small-world property and power-law degree distributions. Another important property that has drawn a great deal of interest recently is the so-called community structure, i.e. the existence of some natural division of a network such that nodes in each sub-network are highly associated among themselves, while having relatively fewer/weaker connections with the rest of the network. Automatically identifying such communities is fundamental for revealing the relationships between the structure and function of complex networks, with many applications in different disciplines such as sociology, biology, and computer science.

In this talk, I will discuss the conceptual and algorithmic challenges in community discovery, and present our recent contributions in addressing these challenges. I will show several real applications of our methods in biology and other areas, and demonstrate the advantages of our methods against the existing approaches. Furthermore, I will show that the members of the same community often have very strong functional ties, which may shed light on the organizing principles of the system, and provide key insights about the functions of some previously uncharacterized members. I will conclude with an overview of my research interests and plan of future works.

Speaker Bio

Jianhua Ruan is currently a PhD candidate in the Department of Computer Science and Engineering at Washington University in St Louis. He received his B.S. degree (1998) in Biology from University of Science and Technology of China, and M.S. degree (2002) in Computer Science from California State University. His current research interests in computational biology and bioinformatics include (1) structural and functional properties of biological networks, (2) reverse-engineering of gene transcriptional regulatory networks, and (3) RNA structures and functions.