Counting motifs in probabilistic biological networks

Abstract

Studying the distribution of motifs in biological networks provides valuable insights about the key functions of these networks. Finding motifs in networks is however a computationally challenging task. This task is further complicated by the fact that inherently, biological networks have uncertain topologies. Such uncertainty is often described using probabilistic network models. In this study we tackle this challenge. We present the exact computation of the expected value and variance of the number of occurrences of key motifs in probabilistic networks, as well as a specialized sampling approximate method for computing the variance for very large networks. Our method is generic, and easily extends to arbitrary motif topologies. Our experiments demonstrate that our method scales to large protein interaction networks as well as synthetically generated networks with different connectivity patterns. Using our method, we identify over-represented motifs in protein-protein interaction networks of five different organisms, as well as in human transcription regulatory networks of different human cells with different lineages.