Structural and functional redundancy in biological networks

Several scholars of evolutionary biology have suggested that functional redundancy (also known as "biological degener-
acy") is important for robustness of biological networks. Structural redundancy indicates the existence of structurally
similar subsystems that can perform the same function. Functional redundancy indicates the existence of structurally
di erent subsystems that can perform the same function. For networks with Ornstein--Uhlenbeck dynamics, Tononi et al.
[Proc. Natl. Acad. Sci. U.S.A. 96, 3257{3262 (1999)] proposed measures of structural and functional redundancy that are
based on mutual information between subnetworks. For a network of n vertices, an exact computation of these quantities
requires O(n!) time. We derive expansions for these measures that one can compute in O(n3) time. We use the expan-
sions to compare the contributions of di erent types of motifs to a network's functional redundancy.