Date of Degree
Hernan A. Makse
Robert M. Haralick
David J. Phillips
Biological and Chemical Physics | Biophysics | Computational Biology | Data Science | Dynamic Systems | Systems Biology
Symmetry, Graph Fibrations, Synchronization, Network reconstruction, Network motifs
The description of a complex system like gene regulation of a cell or a brain of an animal in terms of the dynamics of each individual element is an insurmountable task due to the complexity of interactions and the scores of associated parameters. Recent decades brought about the description of these systems that employs network models. In such models the entire system is represented by a graph encapsulating a set of independently functioning objects and their interactions. This creates a level of abstraction that makes the analysis of such large scale system possible. Common practice is to draw conclusions about the functioning of the network by calculating the topological features like degree distribution, clustering coefficient, community structure and others.
Symmetry is the foundation of many breakthroughs in physics ranging from Newton’s law and Lagrangian mechanics to standard model and crystallography. In graph theory symmetries are usually associated with automorphisms – transformations of a graph that leave its structure unchanged. Despite the prevalent existence of symmetry in physical systems, biological networks with rare exceptions are believed to not be rich in symmetries. We suspect that the underlying reason for this disparity is the fact that the existence of an automorphism imposes a rigid constraint on the network that can be easily violated. Biological networks are constructed by compiling the experimentally obtained data, which has a natural cost associated with it – these networks are imperfect. Among others imperfection comes from two basic factors: (1) the observed network is a network that belongs to a particular specimen under investigation that has an individual structure developed due to mutations and adaptations this specimen underwent and (2) the observed network is built on experimental data that inevitably contains a degree of uncertainty and experimental errors. Therefore, the real network that underlies the system under investigation might be symmetric, but due to the mentioned imperfections this symmetry might be hard to detect.
The key contribution of this dissertation is the development and application of a novel, symmetry-inspired, approach to the analysis of biological networks employing the fibration symmetry that has never been observed in a real system before. Fibrations were first introduced in 1959 by Alexander Grothendieck in the framework of category theory and were extended to graph theory by Boldi and Vigna in 2002. In the beginning of the 21st century Golubitsky, Stewart and co-authors developed a theory of coupled-cell networks and discovered that the existence of the groupoid symmetry has a deep connection with the dynamics of the underlying network. Namely, they saw that groupoid symmetry can lead to cluster synchronization in a network. The equivalence between the fibration symmetry and groupoid symmetry was discussed by DeVille and Lerman in their 2013 paper, which allowed them to conclude that the existence of the fibration symmetry can lead to cluster synchronization in a network. Fibration symmetry constrains the network in a less rigid fashion than automorphisms and is therefore harder to break and easier to observe in real networks. In fact, all nodes that are symmetric under automorphisms are symmetric in terms of fibration symmetry, but not vice versa.
Fibration symmetries allowed us to identify a novel type of building blocks of biological networks, fiber building blocks, based on the symmetry and the underlying synchronization. We were able to classify fiber building blocks into classes described with two numbers that we call fiber numbers. Further by supplementing the fibration symmetry with the principle of symmetry breaking we uncover another type of building blocks that we call symmetry breaking building blocks. We find that these two types of building blocks perform core functions in biological networks – synchronization, clock and memory. Considering the less rigid symmetry allows the symmetry-based analysis to be applied to real networks, however even this weaker condition is not always perfectly satisfied. The traditional approach to dealing with networks with errors is to refine them with network reconstruction algorithms that are conventionally based on the local or global topological features of the network, which leave network structure and dynamics out of the picture. An additional contribution of this thesis is the design of a network reconstruction algorithm aimed at detecting the imperfect fibration symmetries in the network and restoring network topology to ”fix” them.
Leifer, Ian, "Symmetry-Inspired Analysis of Biological Networks" (2022). CUNY Academic Works.
This work is embargoed and will be available for download on Monday, October 17, 2022
Graduate Center users:
To read this work, log in to your GC ILL account and place a thesis request.
See the GC’s lending policies to learn more.