Search for: All records

Genome rearrangement is a common model for molecular evolution. In this paper, we consider the Pairwise Rearrangement problem, which takes as input two genomes and asks for the number of minimum-length sequences of permissible operations transforming the first genome into the second. In the Single Cut-and-Join model (Bergeron, Medvedev, & Stoye, J. Comput. Biol. 2010), Pairwise Rearrangement is #P-complete (Bailey, et. al., COCOON 2023), which implies that exact sampling is intractable. In order to cope with this intractability, we investigate the parameterized complexity of this problem. We exhibit a fixed-parameter tractable algorithm with respect to the number of components in the adjacency graph that are not cycles of length 2 or paths of length 1. As a consequence, we obtain that Pairwise Rearrangement in the Single Cut-and-Join model is fixed-parameter tractable by distance. Our results suggest that the number of nontrivial components in the adjacency graph serves as the key obstacle for efficient sampling. 

Many tissues undergo a steady turnover, where cell divisions are on average balanced with cell deaths. Cell fate decisions such as stem cell (SC) differentiations, proliferations, or differentiated cell (DC) deaths, may be controlled by cell populations through cell-to-cell signaling. Here, we examine a class of mathematical models of turnover in SC lineages to understand engineering design principles of control (feedback) loops, that may operate in such systems. By using ordinary differential equations that describe the co-dynamics of SCs and DCs, we study the effect of different types of mutations that interfere with feedback present within cellular networks. For instance, we find that mutants that do not participate in feedback are less dangerous in the sense that they will not rise from low numbers, whereas mutants that do not respond to feedback signals could rise and replace the wild-type population. Additionally, we asked if different feedback networks can have different degrees of resilience against such mutations. We found that all minimal networks, that is networks consisting of exactly one feedback loop that is sufficient for homeostatic stability of the wild-type population, are equally vulnerable. Mutants with a weakened/eliminated feedback parameter might expand from lower numbers and either enter unlimited growth or reach an equilibrium with an increased number of SCs and DCs. Therefore, from an evolutionary viewpoint, it appears advantageous to combine feedback loops, creating redundant feedback networks. Interestingly, from an engineering prospective, not all such redundant systems are equally resilient. For some of them, any mutation that weakens/eliminates one of the loops will lead to a population growth of SCs. For others, the population of SCs can actually shrink as a result of “cutting” one of the loops, thus slowing down further unwanted transformations.