Target search on networks-within-networks with applications to protein-DNA interactions
Lucas Hedström, Seong-Gyu Yang, Ludvig Lizana · 2024
Read Target search on networks-within-networks with applications to protein-DNA interactions by Lucas Hedström, Seong-Gyu Yang, Ludvig Lizana (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-02660.txt.
Description
A 2024 arXiv research paper by Lucas Hedström, Seong-Gyu Yang, Ludvig Lizana. We present a novel framework for understanding node target search in systems organized as hierarchical networks-within-networks. Our work generalizes traditional search models on complex networks, where the mean-first passage time is typically inversely proportional to the node degree. However, real-world search processes often span multiple network layers, such as moving from an external environment into a local network, and then navigating several internal states.
Catalog record
| CREATOR | Lucas Hedström, Seong-Gyu Yang, Ludvig Lizana |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-02660
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Target search on networks-within-networks with applications to protein-DNA interactions Lucas Hedström, Seong-Gyu Yang, Ludvig Lizana Abstract We present a novel framework for understanding node target search in systems organized as hierarchical networks-within-networks. Our work generalizes traditional search models on complex networks, where the mean-first passage time is typically inversely proportional to the node degree. However, real-world search processes often span multiple network layers, such as moving from an external environment into a local network, and then navigating several internal states. This multilayered complexity appears in scenarios such as international travel networks, tracking email spammers, and the dynamics of protein-DNA interactions in cells. Our theory addresses these complex systems by modeling them as a three-layer multiplex network: an external source layer, an intermediate spatial layer, and an internal state layer. We derive general closed-form solutions for the steady-state flux through a target node, which serves as a proxy for inverse mean-first passage time. Our results reveal a universal relationship between search efficiency and network-specific parameters. This work extends the current understanding of multiplex networks by focusing on systems with hierarchically connected layers. Our findings have broad implications for fields ranging from epidemiology to cellular biology and provide a more comprehensive understanding of search dynamics in complex, multilayered environments. I Introduction One of the most well-known results in node-search on complex networks is that the mean-first passage time (MFPT) is inversely proportional to the node degree [ 1 ] . However, in real-world scenarios, search processes typically occur on more complex structures with a networks-within-network-like organizations. In such cases, the node degree is but a crude proxy for search times. Imagine this example: say you wish to find a tourist site in a far-away city. First, you must travel through the airline transportation network to find the correct airport and then find a way through the local transportation system to reach the desired location. Next, you must navigate the local surroundings to find your intended endpoint. To estimate the total travel time, you need to consider the time spent on all these network layers, which is not simply proportional to the number of connections associated with the final destination. This problem generalizes the standard node search on complex networks to systems with a networks-within-network organizations. Apart from travel, this class of search problems encompasses tracking down virus-infected computers or email spammers on Local Area Networks connected to the Internet [ 2 ] , finding super-spreaders in epidemic outbreaks (like COVID-19 [ 3 , 4 ] ), tracing contaminants in river networks or subway systems [ 5 ] , or identifying leaders in organized crime or interconnected terrorist cells [ 6 , 7 ] . Figure 1: Our model considers a three-layer multiplex network. The top layer (green) represents inflow from outside, such as people traveling into a country or proteins diffusing onto DNA from the nucleoplasm. The middle layer (blue) reflects connections inside the system, like the national travel network or translocations between DNA segments. The bottom layer (yellow) captures internal degrees of freedom, such as city streets in a city or conformational states of protein complexes. These cases illustrate search on networks-within-networks in macroscopic scales. However, there are examples at microscopic scales, too. For example, critical cellular processes such as gene regulation, DNA repair, and transcription rely on specific protein complexes finding and binding designated target sites on DNA, typically a short base pair sequence. While searching, these complexes undergo switching between several internal states that regulate the sensitivity and speed of the search or direct the complexes to select parts of the genome. These internal states can represent conformational states or modifications by small molecules or protein subunits. In some cases, the switching is due to thermal fluctuations, where the searching complexes alternate between states having different free energies. For example, the search-and-recognition mode of Transcription Factors (TF) that regulate genes [ 8 ] or sigma factors binding to RNA polymerases to shift the general gene expression of select gene families. Other cases are driven by non-equilibrium switching, hydrolyzing ATP molecules to release energy. One such case occurs in DNA repair where the MutS protein spends two ATP molecules when recognizing a mismatched base pair site and forms a sliding clamp conformation [ 9 ] . This clamp is essential for recruiting the next protein in the repair cascade (e.g., MutL). However, describing the switching between the internal states is not enough to quantify or understand search times for targets on DNA. In addition to the proteins’ internal dynamics, the search often occurs on complex media, like the nucleus or the chromosomes. These structures exhibit fractal-like properties often represented as complex networks [ 10 , 11 , 12 ] . Therefore, like navigating through a multi-layer transportation network when looking for the DNA-target search problem falls in the same class where proteins must navigate complex spatial structures in addition to being in the correct internal state to find and recognize designated targets. Networks-within-networks, a specific subclass of multiplex or multilayer networks [ 13 , 14 , 15 , 16 ] that emphasize connections between distinct, often independent networks, whereas multiplex networks typically describe nodes participating in multiple networks simultaneously, fulfilling different roles on different layers. As illustrated in Fig. 1 , we model a three-layer structure. The middle layer (blue) represents a spatial network, such as 3D contacts within a chromosome, where the target node resides. However, since the target can only be detected when the searcher is in the appropriate internal state, we associate each node in the middle layer with its own network of internal states (orange). We envision this spatial network in contact with an external source called the “bulk” (green).In protein target search, the bulk represents the cell volume surrounding DNA; in travel contexts, it could represent flights arriving from other continents. In this paper, we develop a general theory for node target search on networks-within-networks. Specifically, the theory concerns the concentration of searchers (e.g., proteins) cascading through all network layers from the “bulk”, where we are interested in the steady-state flux through a designated target node. We find several closed-form expressions holding for general network configurations. For example, we find that the steady-state flux J_{\infty} , our proxy for inverse MFPT, follows a universal relationship depending on two network-specific parameters K and \Gamma associated with the blue and orange layers, and the number of nodes N in the spatial layer. When the internal network has two nodes, like in a simple TF two-state target search [ 17 ] we find the time spent on the network is given by a geometrical average of the on and off rates as \sim(k_{\textrm{on}}k_{\textrm{on}}^{\prime})^{1/2} . We also study the trade-off between having a large internal network yielding robustness to network perturbations but, at the same time, generally slowing down the search. II Method II.1 General theory Figure 2: The three-layer multiplex network in Fig. 1 with rates. Every node in spatial space (blue) is connected to the singular bulk node with rates k_{\textrm{on}} and k_{\textrm{off}} . The nodes in the spatial layer are numbered i=1,\cdots,i,\cdots,N and connected by the rates k_{ij} . Every blue node has a network of internal states (orange) connected with rates k_{\textrm{on}}^{\prime} and k_{\textrm{off}}^{\prime} .