@article{15146, abstract = {The extracellular matrix (ECM) serves as a scaffold for cells and plays an essential role in regulating numerous cellular processes, including cell migration and proliferation. Due to limitations in specimen preparation for conventional room-temperature electron microscopy, we lack structural knowledge on how ECM components are secreted, remodeled, and interact with surrounding cells. We have developed a 3D-ECM platform compatible with sample thinning by cryo-focused ion beam milling, the lift-out extraction procedure, and cryo-electron tomography. Our workflow implements cell-derived matrices (CDMs) grown on EM grids, resulting in a versatile tool closely mimicking ECM environments. This allows us to visualize ECM for the first time in its hydrated, native context. Our data reveal an intricate network of extracellular fibers, their positioning relative to matrix-secreting cells, and previously unresolved structural entities. Our workflow and results add to the structural atlas of the ECM, providing novel insights into its secretion and assembly.}, author = {Zens, Bettina and Fäßler, Florian and Hansen, Jesse and Hauschild, Robert and Datler, Julia and Hodirnau, Victor-Valentin and Zheden, Vanessa and Alanko, Jonna H and Sixt, Michael K and Schur, Florian KM}, issn = {1540-8140}, journal = {Journal of Cell Biology}, number = {6}, publisher = {Rockefeller University Press}, title = {{Lift-out cryo-FIBSEM and cryo-ET reveal the ultrastructural landscape of extracellular matrix}}, doi = {10.1083/jcb.202309125}, volume = {223}, year = {2024}, } @inbook{12428, abstract = {The mammary gland consists of a bilayered epithelial structure with an extensively branched morphology. The majority of this epithelial tree is laid down during puberty, during which actively proliferating terminal end buds repeatedly elongate and bifurcate to form the basic structure of the ductal tree. Mammary ducts consist of a basal and luminal cell layer with a multitude of identified sub-lineages within both layers. The understanding of how these different cell lineages are cooperatively driving branching morphogenesis is a problem of crossing multiple scales, as this requires information on the macroscopic branched structure of the gland, as well as data on single-cell dynamics driving the morphogenic program. Here we describe a method to combine genetic lineage tracing with whole-gland branching analysis. Quantitative data on the global organ structure can be used to derive a model for mammary gland branching morphogenesis and provide a backbone on which the dynamics of individual cell lineages can be simulated and compared to lineage-tracing approaches. Eventually, these quantitative models and experiments allow to understand the couplings between the macroscopic shape of the mammary gland and the underlying single-cell dynamics driving branching morphogenesis.}, author = {Hannezo, Edouard B and Scheele, Colinda L.G.J.}, booktitle = {Cell Migration in Three Dimensions}, editor = {Margadant, Coert}, isbn = {9781071628867}, issn = {1940-6029}, pages = {183--205}, publisher = {Springer Nature}, title = {{A Guide Toward Multi-scale and Quantitative Branching Analysis in the Mammary Gland}}, doi = {10.1007/978-1-0716-2887-4_12}, volume = {2608}, year = {2023}, } @article{12534, abstract = {Brownian motion of a mobile impurity in a bath is affected by spin-orbit coupling (SOC). Here, we discuss a Caldeira-Leggett-type model that can be used to propose and interpret quantum simulators of this problem in cold Bose gases. First, we derive a master equation that describes the model and explore it in a one-dimensional (1D) setting. To validate the standard assumptions needed for our derivation, we analyze available experimental data without SOC; as a byproduct, this analysis suggests that the quench dynamics of the impurity is beyond the 1D Bose-polaron approach at temperatures currently accessible in a cold-atom laboratory—motion of the impurity is mainly driven by dissipation. For systems with SOC, we demonstrate that 1D spin-orbit coupling can be gauged out even in the presence of dissipation—the information about SOC is incorporated in the initial conditions. Observables sensitive to this information (such as spin densities) can be used to study formation of steady spin polarization domains during quench dynamics.}, author = {Ghazaryan, Areg and Cappellaro, Alberto and Lemeshko, Mikhail and Volosniev, Artem}, issn = {2643-1564}, journal = {Physical Review Research}, number = {1}, publisher = {American Physical Society}, title = {{Dissipative dynamics of an impurity with spin-orbit coupling}}, doi = {10.1103/physrevresearch.5.013029}, volume = {5}, year = {2023}, } @article{12158, abstract = {Post-translational histone modifications modulate chromatin activity to affect gene expression. How chromatin states underlie lineage choice in single cells is relatively unexplored. We develop sort-assisted single-cell chromatin immunocleavage (sortChIC) and map active (H3K4me1 and H3K4me3) and repressive (H3K27me3 and H3K9me3) histone modifications in the mouse bone marrow. During differentiation, hematopoietic stem and progenitor cells (HSPCs) acquire active chromatin states mediated by cell-type-specifying transcription factors, which are unique for each lineage. By contrast, most alterations in repressive marks during differentiation occur independent of the final cell type. Chromatin trajectory analysis shows that lineage choice at the chromatin level occurs at the progenitor stage. Joint profiling of H3K4me1 and H3K9me3 demonstrates that cell types within the myeloid lineage have distinct active chromatin but share similar myeloid-specific heterochromatin states. This implies a hierarchical regulation of chromatin during hematopoiesis: heterochromatin dynamics distinguish differentiation trajectories and lineages, while euchromatin dynamics reflect cell types within lineages.}, author = {Zeller, Peter and Yeung, Jake and Viñas Gaza, Helena and de Barbanson, Buys Anton and Bhardwaj, Vivek and Florescu, Maria and van der Linden, Reinier and van Oudenaarden, Alexander}, issn = {1546-1718}, journal = {Nature Genetics}, keywords = {Genetics}, pages = {333--345}, publisher = {Springer Nature}, title = {{Single-cell sortChIC identifies hierarchical chromatin dynamics during hematopoiesis}}, doi = {10.1038/s41588-022-01260-3}, volume = {55}, year = {2023}, } @inproceedings{12676, abstract = {Turn-based stochastic games (aka simple stochastic games) are two-player zero-sum games played on directed graphs with probabilistic transitions. The goal of player-max is to maximize the probability to reach a target state against the adversarial player-min. These games lie in NP ∩ coNP and are among the rare combinatorial problems that belong to this complexity class for which the existence of polynomial-time algorithm is a major open question. While randomized sub-exponential time algorithm exists, all known deterministic algorithms require exponential time in the worst-case. An important open question has been whether faster algorithms can be obtained parametrized by the treewidth of the game graph. Even deterministic sub-exponential time algorithm for constant treewidth turn-based stochastic games has remain elusive. In this work our main result is a deterministic algorithm to solve turn-based stochastic games that, given a game with n states, treewidth at most t, and the bit-complexity of the probabilistic transition function log D, has running time O ((tn2 log D)t log n). In particular, our algorithm is quasi-polynomial time for games with constant or poly-logarithmic treewidth.}, author = {Chatterjee, Krishnendu and Meggendorfer, Tobias and Saona Urmeneta, Raimundo J and Svoboda, Jakub}, booktitle = {Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms}, isbn = {9781611977554}, location = {Florence, Italy}, pages = {4590--4605}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Faster algorithm for turn-based stochastic games with bounded treewidth}}, doi = {10.1137/1.9781611977554.ch173}, year = {2023}, } @inbook{12720, abstract = {Here we describe the in vivo DNA assembly approach, where molecular cloning procedures are performed using an E. coli recA-independent recombination pathway, which assembles linear fragments of DNA with short homologous termini. This pathway is present in all standard laboratory E. coli strains and, by bypassing the need for in vitro DNA assembly, allows simplified molecular cloning to be performed without the plasmid instability issues associated with specialized recombination-cloning bacterial strains. The methodology requires specific primer design and can perform all standard plasmid modifications (insertions, deletions, mutagenesis, and sub-cloning) in a rapid, simple, and cost-efficient manner, as it does not require commercial kits or specialized bacterial strains. Additionally, this approach can be used to perform complex procedures such as multiple modifications to a plasmid, as up to 6 linear fragments can be assembled in vivo by this recombination pathway. Procedures generally require less than 3 h, involving PCR amplification, DpnI digestion of template DNA, and transformation, upon which circular plasmids are assembled. In this chapter we describe the requirements, procedure, and potential pitfalls when using this technique, as well as protocol variations to overcome the most common issues.}, author = {Arroyo-Urea, Sandra and Watson, Jake and García-Nafría, Javier}, booktitle = {DNA Manipulation and Analysis}, editor = {Scarlett, Garry}, isbn = {978-1-0716-3003-7}, issn = {1940-6029}, pages = {33--44}, publisher = {Springer Nature}, title = {{Molecular Cloning Using In Vivo DNA Assembly}}, doi = {10.1007/978-1-0716-3004-4_3}, volume = {2633}, year = {2023}, } @inproceedings{12735, abstract = {Asynchronous programming has gained significant popularity over the last decade: support for this programming pattern is available in many popular languages via libraries and native language implementations, typically in the form of coroutines or the async/await construct. Instead of programming via shared memory, this concept assumes implicit synchronization through message passing. The key data structure enabling such communication is the rendezvous channel. Roughly, a rendezvous channel is a blocking queue of size zero, so both send(e) and receive() operations wait for each other, performing a rendezvous when they meet. To optimize the message passing pattern, channels are usually equipped with a fixed-size buffer, so sends do not suspend and put elements into the buffer until its capacity is exceeded. This primitive is known as a buffered channel. This paper presents a fast and scalable algorithm for both rendezvous and buffered channels. Similarly to modern queues, our solution is based on an infinite array with two positional counters for send(e) and receive() operations, leveraging the unconditional Fetch-And-Add instruction to update them. Yet, the algorithm requires non-trivial modifications of this classic pattern, in order to support the full channel semantics, such as buffering and cancellation of waiting requests. We compare the performance of our solution to that of the Kotlin implementation, as well as against other academic proposals, showing up to 9.8× speedup. To showcase its expressiveness and performance, we also integrated the proposed algorithm into the standard Kotlin Coroutines library, replacing the previous channel implementations.}, author = {Koval, Nikita and Alistarh, Dan-Adrian and Elizarov, Roman}, booktitle = {Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming}, isbn = {9798400700156}, location = {Montreal, QC, Canada}, pages = {107--118}, publisher = {Association for Computing Machinery}, title = {{Fast and scalable channels in Kotlin Coroutines}}, doi = {10.1145/3572848.3577481}, year = {2023}, } @misc{12736, abstract = {Although a wide variety of handcrafted concurrent data structures have been proposed, there is considerable interest in universal approaches (Universal Constructions or UCs) for building concurrent data structures. UCs (semi-)automatically convert a sequential data structure into a concurrent one. The simplest approach uses locks [3, 6] that protect a sequential data structure and allow only one process to access it at a time. However, the resulting data structure is blocking. Most work on UCs instead focuses on obtaining non-blocking progress guarantees such as obstruction-freedom, lock-freedom or wait-freedom. Many non-blocking UCs have appeared. Key examples include the seminal wait-free UC [2] by Herlihy, a NUMA-aware UC [10] by Yi et al., and an efficient UC for large objects [1] by Fatourou et al.}, author = {Aksenov, Vitaly and Brown, Trevor A and Fedorov, Alexander and Kokorin, Ilya}, booktitle = {Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming}, isbn = {9798400700156}, location = {Montreal, QB, Canada}, pages = {438--440}, publisher = {Association for Computing Machinery}, title = {{Unexpected scaling in path copying trees}}, doi = {10.1145/3572848.3577512}, year = {2023}, } @inproceedings{12760, abstract = {Dynamic programming (DP) is one of the fundamental paradigms in algorithm design. However, many DP algorithms have to fill in large DP tables, represented by two-dimensional arrays, which causes at least quadratic running times and space usages. This has led to the development of improved algorithms for special cases when the DPs satisfy additional properties like, e.g., the Monge property or total monotonicity. In this paper, we consider a new condition which assumes (among some other technical assumptions) that the rows of the DP table are monotone. Under this assumption, we introduce a novel data structure for computing (1 + ϵ)-approximate DP solutions in near-linear time and space in the static setting, and with polylogarithmic update times when the DP entries change dynamically. To the best of our knowledge, our new condition is incomparable to previous conditions and is the first which allows to derive dynamic algorithms based on existing DPs. Instead of using two-dimensional arrays to store the DP tables, we store the rows of the DP tables using monotone piecewise constant functions. This allows us to store length-n DP table rows with entries in [0, W] using only polylog(n, W) bits, and to perform operations, such as (min, +)-convolution or rounding, on these functions in polylogarithmic time. We further present several applications of our data structure. For bicriteria versions of k-balanced graph partitioning and simultaneous source location, we obtain the first dynamic algorithms with subpolynomial update times, as well as the first static algorithms using only near-linear time and space. Additionally, we obtain the currently fastest algorithm for fully dynamic knapsack.}, author = {Henzinger, Monika H and Neumann, Stefan and Räcke, Harald and Schmid, Stefan}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science}, isbn = {9783959772662}, issn = {1868-8969}, location = {Hamburg, Germany}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Dynamic maintenance of monotone dynamic programs and applications}}, doi = {10.4230/LIPIcs.STACS.2023.36}, volume = {254}, year = {2023}, } @phdthesis{12716, abstract = {The process of detecting and evaluating sensory information to guide behaviour is termed perceptual decision-making (PDM), and is critical for the ability of an organism to interact with its external world. Individuals with autism, a neurodevelopmental condition primarily characterised by social and communication difficulties, frequently exhibit altered sensory processing and PDM difficulties are widely reported. Recent technological advancements have pushed forward our understanding of the genetic changes accompanying this condition, however our understanding of how these mutations affect the function of specific neuronal circuits and bring about the corresponding behavioural changes remains limited. Here, we use an innate PDM task, the looming avoidance response (LAR) paradigm, to identify a convergent behavioural abnormality across three molecularly distinct genetic mouse models of autism (Cul3, Setd5 and Ptchd1). Although mutant mice can rapidly detect threatening visual stimuli, their responses are consistently delayed, requiring longer to initiate an appropriate response than their wild-type siblings. Mutant animals show abnormal adaptation in both their stimulus- evoked escape responses and exploratory dynamics following repeated stimulus presentations. Similarly delayed behavioural responses are observed in wild-type animals when faced with more ambiguous threats, suggesting the mutant phenotype could arise from a dysfunction in the flexible control of this PDM process. Our knowledge of the core neuronal circuitry mediating the LAR facilitated a detailed dissection of the neuronal mechanisms underlying the behavioural impairment. In vivo extracellular recording revealed that visual responses were unaffected within a key brain region for the rapid processing of visual threats, the superior colliculus (SC), indicating that the behavioural delay was unlikely to originate from sensory impairments. Delayed behavioural responses were recapitulated in the Setd5 model following optogenetic stimulation of the excitatory output neurons of the SC, which are known to mediate escape initiation through the activation of cells in the underlying dorsal periaqueductal grey (dPAG). In vitro patch-clamp recordings of dPAG cells uncovered a stark hypoexcitability phenotype in two out of the three genetic models investigated (Setd5 and Ptchd1), that in Setd5, is mediated by the misregulation of voltage-gated potassium channels. Overall, our results show that the ability to use visual information to drive efficient escape responses is impaired in three diverse genetic mouse models of autism and that, in one of the models studied, this behavioural delay likely originates from differences in the intrinsic excitability of a key subcortical node, the dPAG. Furthermore, this work showcases the use of an innate behavioural paradigm to mechanistically dissect PDM processes in autism.}, author = {Burnett, Laura}, issn = {2663-337X}, pages = {178}, publisher = {Institute of Science and Technology Austria}, title = {{To flee, or not to flee? Using innate defensive behaviours to investigate rapid perceptual decision-making through subcortical circuits in mouse models of autism}}, doi = {10.15479/at:ista:12716}, year = {2023}, }