@article{10926, abstract = {Conflict over reproduction between females and males exists because of anisogamy and promiscuity. Together they generate differences in fitness optima between the sexes and result in antagonistic coevolution of female and male reproductive traits. Mounting duration is likely to be a compromise between male and female interests whose outcome depends on the intensity of sexual selection. The timing of sperm transfer during mounting is critical. For example, mountings may be interrupted before sperm is transferred as a consequence of female or male choice, or they may be prolonged to function as mate guarding. In the highly promiscuous intertidal snail Littorina saxatilis, mountings vary substantially in duration, from less than a minute to more than an hour, and it has been assumed that mountings of a few minutes do not result in any sperm being transferred. Here, we examined the timing of sperm transfer, a reproductive trait that is likely affected by sexual conflict. We performed time-controlled mounting trials using L. saxatilis males and virgin females, aiming to examine indirectly when the transfer of sperm starts. We observed the relationship between mounting duration and the proportion of developing embryos out of all eggs and embryos in the brood pouch. Developing embryos were observed in similar proportions in all treatments (i.e. 1, 5 and 10 or more minutes at which mountings were artificially interrupted), suggesting that sperm transfer begins rapidly (within 1 min) in L. saxatilis and very short matings do not result in sperm shortage in the females. We discuss how the observed pattern can be influenced by predation risk, population density, and female status and receptivity.}, author = {Perini, Samuel and Butlin, Rogerk and Westram, Anja M and Johannesson, Kerstin}, issn = {1464-3766}, journal = {Journal of Molluscan Studies}, number = {1}, publisher = {Oxford Academic}, title = {{Very short mountings are enough for sperm transfer in Littorina saxatilis}}, doi = {10.1093/mollus/eyab049}, volume = {88}, year = {2022}, } @article{10927, abstract = {Motivation High plasticity of bacterial genomes is provided by numerous mechanisms including horizontal gene transfer and recombination via numerous flanking repeats. Genome rearrangements such as inversions, deletions, insertions and duplications may independently occur in different strains, providing parallel adaptation or phenotypic diversity. Specifically, such rearrangements might be responsible for virulence, antibiotic resistance and antigenic variation. However, identification of such events requires laborious manual inspection and verification of phyletic pattern consistency. Results Here, we define the term ‘parallel rearrangements’ as events that occur independently in phylogenetically distant bacterial strains and present a formalization of the problem of parallel rearrangements calling. We implement an algorithmic solution for the identification of parallel rearrangements in bacterial populations as a tool PaReBrick. The tool takes a collection of strains represented as a sequence of oriented synteny blocks and a phylogenetic tree as input data. It identifies rearrangements, tests them for consistency with a tree, and sorts the events by their parallelism score. The tool provides diagrams of the neighbors for each block of interest, allowing the detection of horizontally transferred blocks or their extra copies and the inversions in which copied blocks are involved. We demonstrated PaReBrick’s efficiency and accuracy and showed its potential to detect genome rearrangements responsible for pathogenicity and adaptation in bacterial genomes.}, author = {Zabelkin, Alexey and Yakovleva, Yulia and Bochkareva, Olga and Alexeev, Nikita}, issn = {1460-2059}, journal = {Bioinformatics}, number = {2}, pages = {357--363}, publisher = {Oxford Academic}, title = {{PaReBrick: PArallel REarrangements and BReaks identification toolkit}}, doi = {10.1093/bioinformatics/btab691}, volume = {38}, year = {2022}, } @misc{10934, abstract = {FtsA is crucial for assembly of the E. coli divisome, as it dynamically links cytoplasmic FtsZ filaments with transmembrane cell division proteins. FtsA allegedly initiates cell division by switching from an inactive polymeric to an active monomeric confirmation, which recruits downstream proteins and stabilizes FtsZ filaments. Here, we use biochemical reconstitution experiments combined with quantitative fluorescence microscopy to study divisome activation in vitro. We compare wildtype-FtsA with FtsA-R286W, a constantly active gain-of-function mutant and find that R286W outperforms the wildtype protein in replicating FtsZ treadmilling dynamics, stabilizing FtsZ filaments and recruiting FtsN. We attribute these differences to a faster membrane exchange of FtsA-R286W and its higher packing density below FtsZ filaments. Using FRET microscopy, we find that FtsN binding does not compete with, but promotes FtsA self-interaction. Our findings suggest a model where FtsA always forms dynamic polymers on the membrane, which re-organize during assembly and activation of the divisome. }, author = {Radler, Philipp}, keywords = {Bacterial cell division, in vitro reconstitution, FtsZ, FtsN, FtsA}, publisher = {Institute of Science and Technology Austria}, title = {{In vitro reconstitution of Escherichia coli divisome activation}}, doi = {10.15479/AT:ISTA:10934}, year = {2022}, } @article{10939, abstract = {Understanding and characterising biochemical processes inside single cells requires experimental platforms that allow one to perturb and observe the dynamics of such processes as well as computational methods to build and parameterise models from the collected data. Recent progress with experimental platforms and optogenetics has made it possible to expose each cell in an experiment to an individualised input and automatically record cellular responses over days with fine time resolution. However, methods to infer parameters of stochastic kinetic models from single-cell longitudinal data have generally been developed under the assumption that experimental data is sparse and that responses of cells to at most a few different input perturbations can be observed. Here, we investigate and compare different approaches for calculating parameter likelihoods of single-cell longitudinal data based on approximations of the chemical master equation (CME) with a particular focus on coupling the linear noise approximation (LNA) or moment closure methods to a Kalman filter. We show that, as long as cells are measured sufficiently frequently, coupling the LNA to a Kalman filter allows one to accurately approximate likelihoods and to infer model parameters from data even in cases where the LNA provides poor approximations of the CME. Furthermore, the computational cost of filtering-based iterative likelihood evaluation scales advantageously in the number of measurement times and different input perturbations and is thus ideally suited for data obtained from modern experimental platforms. To demonstrate the practical usefulness of these results, we perform an experiment in which single cells, equipped with an optogenetic gene expression system, are exposed to various different light-input sequences and measured at several hundred time points and use parameter inference based on iterative likelihood evaluation to parameterise a stochastic model of the system.}, author = {Davidović, Anđela and Chait, Remy P and Batt, Gregory and Ruess, Jakob}, issn = {1553-7358}, journal = {PLoS Computational Biology}, number = {3}, publisher = {Public Library of Science}, title = {{Parameter inference for stochastic biochemical models from perturbation experiments parallelised at the single cell level}}, doi = {10.1371/journal.pcbi.1009950}, volume = {18}, year = {2022}, } @article{10940, abstract = {Magnetic-field-resilient superconducting circuits enable sensing applications and hybrid quantum computing architectures involving spin or topological qubits and electromechanical elements, as well as studying flux noise and quasiparticle loss. We investigate the effect of in-plane magnetic fields up to 1 T on the spectrum and coherence times of thin-film three-dimensional aluminum transmons. Using a copper cavity, unaffected by strong magnetic fields, we can probe solely the effect of magnetic fields on the transmons. We present data on a single-junction and a superconducting-quantum-interference-device (SQUID) transmon that are cooled down in the same cavity. As expected, the transmon frequencies decrease with increasing field, due to suppression of the superconducting gap and a geometric Fraunhofer-like contribution. Nevertheless, the thin-film transmons show strong magnetic field resilience: both transmons display microsecond coherence up to at least 0.65 T, and T1 remains above 1μs over the entire measurable range. SQUID spectroscopy is feasible up to 1 T, the limit of our magnet. We conclude that thin-film aluminum Josephson junctions are suitable hardware for superconducting circuits in the high-magnetic-field regime.}, author = {Krause, J. and Dickel, C. and Vaal, E. and Vielmetter, M. and Feng, J. and Bounds, R. and Catelani, G. and Fink, Johannes M and Ando, Yoichi}, issn = {2331-7019}, journal = {Physical Review Applied}, number = {3}, publisher = {American Physical Society}, title = {{Magnetic field resilience of three-dimensional transmons with thin-film Al/AlOx/Al Josephson junctions approaching 1 T}}, doi = {10.1103/PhysRevApplied.17.034032}, volume = {17}, year = {2022}, } @article{10945, abstract = {Mica-titania pearlescent pigments (MTs) were previously coated with organic molecules to obtain combination pigments (CPs) for achieving certain improvements or functionalities. Anthocyanins (ACNs) are molecules that can be extracted from natural resources and exhibit color changes via pH modifications of the enclosing medium. The purpose of the study was to produce a new series of CPs by depositing ACNs on MTs at different pH values, to observe the changes in color, and to associate these changes to thermogravimetrically determined deposition efficiencies in light of spectral differences. The extraction and deposition methods were based on aqueous chemistry and were straightforward. The ACN deposition generally increased with increasing pH and correlated with the consistency between the charges of the MT surfaces and the dominant ACN species at a specific pH value. The fluorescence of the CPs was inversely correlated with the deposition quantities invoking the possibility of a quenching effect.}, author = {Çoruh, Mehmet Orkun and Gündüz, Güngör and Çolak, Üner and Maviş, Bora}, issn = {2079-6447}, journal = {Colorants}, number = {2}, pages = {149--164}, publisher = {MDPI}, title = {{pH-dependent coloring of combination effect pigments with anthocyanins from Brassica oleracea var. capitata F. rubra}}, doi = {10.3390/colorants1020010}, volume = {1}, year = {2022}, } @phdthesis{11128, abstract = {Although we often see studies focusing on simple or even discrete traits in studies of colouration, the variation of “appearance” phenotypes found in nature is often more complex, continuous and high-dimensional. Therefore, we developed automated methods suitable for large datasets of genomes and images, striving to account for their complex nature, while minimising human bias. We used these methods on a dataset of more than 20, 000 plant SNP genomes and corresponding fower images from a hybrid zone of two subspecies of Antirrhinum majus with distinctly coloured fowers to improve our understanding of the genetic nature of the fower colour in our study system. Firstly, we use the advantage of large numbers of genotyped plants to estimate the haplotypes in the main fower colour regulating region. We study colour- and geography-related characteristics of the estimated haplotypes and how they connect to their relatedness. We show discrepancies from the expected fower colour distributions given the genotype and identify particular haplotypes leading to unexpected phenotypes. We also confrm a signifcant defcit of the double recessive recombinant and quite surprisingly, we show that haplotypes of the most frequent parental type are much less variable than others. Secondly, we introduce our pipeline capable of processing tens of thousands of full fower images without human interaction and summarising each image into a set of informative scores. We show the compatibility of these machine-measured fower colour scores with the previously used manual scores and study impact of external efect on the resulting scores. Finally, we use the machine-measured fower colour scores to ft and examine a phenotype cline across the hybrid zone in Planoles using full fower images as opposed to discrete, manual scores and compare it with the genotypic cline.}, author = {Matejovicova, Lenka}, isbn = {978-3-99078-016-9}, issn = {2663-337X}, pages = {112}, publisher = {Institute of Science and Technology Austria}, title = {{Genetic basis of flower colour as a model for adaptive evolution}}, doi = {10.15479/at:ista:11128}, year = {2022}, } @article{11135, abstract = {We consider a correlated NxN Hermitian random matrix with a polynomially decaying metric correlation structure. By calculating the trace of the moments of the matrix and using the summable decay of the cumulants, we show that its operator norm is stochastically dominated by one.}, author = {Reker, Jana}, issn = {2010-3271}, journal = {Random Matrices: Theory and Applications}, keywords = {Discrete Mathematics and Combinatorics, Statistics, Probability and Uncertainty, Statistics and Probability, Algebra and Number Theory}, number = {4}, publisher = {World Scientific}, title = {{On the operator norm of a Hermitian random matrix with correlated entries}}, doi = {10.1142/s2010326322500368}, volume = {11}, year = {2022}, } @article{11142, abstract = {SnTe is a promising Pb-free thermoelectric (TE) material with high electrical conductivity. We discovered the synergistic effect of Bi2O3 on enhancing the average power factor (PF) and overall ZT value of the SnTe-based thermoelectric material. The introduction of Bi2O3 forms plenty of SnO2, Bi2O3, and Bi-rich nanoprecipitates. These interfaces between the SnTe matrix and the nanoprecipitates can enhance the average PF through the energy filtering effect. On the other hand, abundant and diverse nanoprecipitates can significantly diminish the lattice thermal conductivity (κlat) through enhanced phonon scattering. The synergistic effect of Bi2O3 resulted in a maximum ZT (ZTmax) value of 0.9 at SnTe-2% Bi2O3 and an average ZT (ZTave) value of 0.4 for SnTe-4% Bi2O3 from 300 K to 823 K. The work provides an excellent reference to develop non-toxic high-performance TE materials.}, author = {Hong, Tao and Guo, Changrong and Wang, Dongyang and Qin, Bingchao and Chang, Cheng and Gao, Xiang and Zhao, Li Dong}, issn = {2468-6069}, journal = {Materials Today Energy}, publisher = {Elsevier}, title = {{Enhanced thermoelectric performance in SnTe due to the energy filtering effect introduced by Bi2O3}}, doi = {10.1016/j.mtener.2022.100985}, volume = {25}, year = {2022}, } @article{11143, abstract = {Dravet syndrome is a neurodevelopmental disorder characterized by epilepsy, intellectual disability, and sudden death due to pathogenic variants in SCN1A with loss of function of the sodium channel subunit Nav1.1. Nav1.1-expressing parvalbumin GABAergic interneurons (PV-INs) from young Scn1a+/− mice show impaired action potential generation. An approach assessing PV-IN function in the same mice at two time points shows impaired spike generation in all Scn1a+/− mice at postnatal days (P) 16–21, whether deceased prior or surviving to P35, with normalization by P35 in surviving mice. However, PV-IN synaptic transmission is dysfunctional in young Scn1a+/− mice that did not survive and in Scn1a+/− mice ≥ P35. Modeling confirms that PV-IN axonal propagation is more sensitive to decreased sodium conductance than spike generation. These results demonstrate dynamic dysfunction in Dravet syndrome: combined abnormalities of PV-IN spike generation and propagation drives early disease severity, while ongoing dysfunction of synaptic transmission contributes to chronic pathology.}, author = {Kaneko, Keisuke and Currin, Christopher and Goff, Kevin M. and Wengert, Eric R. and Somarowthu, Ala and Vogels, Tim P and Goldberg, Ethan M.}, issn = {2211-1247}, journal = {Cell Reports}, number = {13}, publisher = {Elsevier}, title = {{Developmentally regulated impairment of parvalbumin interneuron synaptic transmission in an experimental model of Dravet syndrome}}, doi = {10.1016/j.celrep.2022.110580}, volume = {38}, year = {2022}, } @article{11144, abstract = {Thermoelectric materials allow for direct conversion between heat and electricity, offering the potential for power generation. The average dimensionless figure of merit ZTave determines device efficiency. N-type tin selenide crystals exhibit outstanding three-dimensional charge and two-dimensional phonon transport along the out-of-plane direction, contributing to a high maximum figure of merit Zmax of ~3.6 × 10−3 per kelvin but a moderate ZTave of ~1.1. We found an attractive high Zmax of ~4.1 × 10−3 per kelvin at 748 kelvin and a ZTave of ~1.7 at 300 to 773 kelvin in chlorine-doped and lead-alloyed tin selenide crystals by phonon-electron decoupling. The chlorine-induced low deformation potential improved the carrier mobility. The lead-induced mass and strain fluctuations reduced the lattice thermal conductivity. Phonon-electron decoupling plays a critical role to achieve high-performance thermoelectrics.}, author = {Su, Lizhong and Wang, Dongyang and Wang, Sining and Qin, Bingchao and Wang, Yuping and Qin, Yongxin and Jin, Yang and Chang, Cheng and Zhao, Li Dong}, issn = {1095-9203}, journal = {Science}, number = {6587}, pages = {1385--1389}, publisher = {American Association for the Advancement of Science}, title = {{High thermoelectric performance realized through manipulating layered phonon-electron decoupling}}, doi = {10.1126/science.abn8997}, volume = {375}, year = {2022}, } @inproceedings{11145, abstract = {List-decodability of Reed-Solomon codes has re-ceived a lot of attention, but the best-possible dependence between the parameters is still not well-understood. In this work, we focus on the case where the list-decoding radius is of the form r=1−ε for ε tending to zero. Our main result states that there exist Reed-Solomon codes with rate Ω(ε) which are (1−ε,O(1/ε) -list-decodable, meaning that any Hamming ball of radius 1−ε contains at most O(1/ε) codewords. This trade-off between rate and list-decoding radius is best-possible for any code with list size less than exponential in the block length. By achieving this trade-off between rate and list-decoding radius we improve a recent result of Guo, Li, Shangguan, Tamo, and Wootters, and resolve the main motivating question of their work. Moreover, while their result requires the field to be exponentially large in the block length, we only need the field size to be polynomially large (and in fact, almost-linear suffices). We deduce our main result from a more general theorem, in which we prove good list-decodability properties of random puncturings of any given code with very large distance.}, author = {Ferber, Asaf and Kwan, Matthew Alan and Sauermann, Lisa}, booktitle = {62nd Annual IEEE Symposium on Foundations of Computer Science}, isbn = {9781665420556}, issn = {0272-5428}, location = {Denver, CO, United States}, pages = {720--726}, publisher = {IEEE}, title = {{List-decodability with large radius for Reed-Solomon codes}}, doi = {10.1109/FOCS52979.2021.00075}, volume = {2022}, year = {2022}, } @article{11155, abstract = {The potential of energy filtering and direct electron detection for cryo-electron microscopy (cryo-EM) has been well documented. Here, we assess the performance of recently introduced hardware for cryo-electron tomography (cryo-ET) and subtomogram averaging (STA), an increasingly popular structural determination method for complex 3D specimens. We acquired cryo-ET datasets of EIAV virus-like particles (VLPs) on two contemporary cryo-EM systems equipped with different energy filters and direct electron detectors (DED), specifically a Krios G4, equipped with a cold field emission gun (CFEG), Thermo Fisher Scientific Selectris X energy filter, and a Falcon 4 DED; and a Krios G3i, with a Schottky field emission gun (XFEG), a Gatan Bioquantum energy filter, and a K3 DED. We performed constrained cross-correlation-based STA on equally sized datasets acquired on the respective systems. The resulting EIAV CA hexamer reconstructions show that both systems perform comparably in the 4–6 Å resolution range based on Fourier-Shell correlation (FSC). In addition, by employing a recently introduced multiparticle refinement approach, we obtained a reconstruction of the EIAV CA hexamer at 2.9 Å. Our results demonstrate the potential of the new generation of energy filters and DEDs for STA, and the effects of using different processing pipelines on their STA outcomes.}, author = {Obr, Martin and Hagen, Wim J.H. and Dick, Robert A. and Yu, Lingbo and Kotecha, Abhay and Schur, Florian KM}, issn = {1047-8477}, journal = {Journal of Structural Biology}, keywords = {Structural Biology}, number = {2}, publisher = {Elsevier}, title = {{Exploring high-resolution cryo-ET and subtomogram averaging capabilities of contemporary DEDs}}, doi = {10.1016/j.jsb.2022.107852}, volume = {214}, year = {2022}, } @article{11160, abstract = {Mutations in the chromodomain helicase DNA-binding 8 (CHD8) gene are a frequent cause of autism spectrum disorder (ASD). While its phenotypic spectrum often encompasses macrocephaly, implicating cortical abnormalities, how CHD8 haploinsufficiency affects neurodevelopmental is unclear. Here, employing human cerebral organoids, we find that CHD8 haploinsufficiency disrupted neurodevelopmental trajectories with an accelerated and delayed generation of, respectively, inhibitory and excitatory neurons that yields, at days 60 and 120, symmetrically opposite expansions in their proportions. This imbalance is consistent with an enlargement of cerebral organoids as an in vitro correlate of patients’ macrocephaly. Through an isogenic design of patient-specific mutations and mosaic organoids, we define genotype-phenotype relationships and uncover their cell-autonomous nature. Our results define cell-type-specific CHD8-dependent molecular defects related to an abnormal program of proliferation and alternative splicing. By identifying cell-type-specific effects of CHD8 mutations, our study uncovers reproducible developmental alterations that may be employed for neurodevelopmental disease modeling.}, author = {Villa, Carlo Emanuele and Cheroni, Cristina and Dotter, Christoph and López-Tóbon, Alejandro and Oliveira, Bárbara and Sacco, Roberto and Yahya, Aysan Çerağ and Morandell, Jasmin and Gabriele, Michele and Tavakoli, Mojtaba and Lyudchik, Julia and Sommer, Christoph M and Gabitto, Mariano and Danzl, Johann G and Testa, Giuseppe and Novarino, Gaia}, issn = {2211-1247}, journal = {Cell Reports}, keywords = {General Biochemistry, Genetics and Molecular Biology}, number = {1}, publisher = {Elsevier}, title = {{CHD8 haploinsufficiency links autism to transient alterations in excitatory and inhibitory trajectories}}, doi = {10.1016/j.celrep.2022.110615}, volume = {39}, year = {2022}, } @article{11167, abstract = {Complex I is one of the major respiratory complexes, conserved from bacteria to mammals. It oxidises NADH, reduces quinone and pumps protons across the membrane, thus playing a central role in the oxidative energy metabolism. In this review we discuss our current state of understanding the structure of complex I from various species of mammals, plants, fungi, and bacteria, as well as of several complex I-related proteins. By comparing the structural evidence from these systems in different redox states and data from mutagenesis and molecular simulations, we formulate the mechanisms of electron transfer and proton pumping and explain how they are conformationally and electrostatically coupled. Finally, we discuss the structural basis of the deactivation phenomenon in mammalian complex I.}, author = {Kampjut, Domen and Sazanov, Leonid A}, issn = {0959-440X}, journal = {Current Opinion in Structural Biology}, keywords = {Molecular Biology, Structural Biology}, publisher = {Elsevier}, title = {{Structure of respiratory complex I – An emerging blueprint for the mechanism}}, doi = {10.1016/j.sbi.2022.102350}, volume = {74}, year = {2022}, } @article{11179, abstract = {Large oligomeric enzymes control a myriad of cellular processes, from protein synthesis and degradation to metabolism. The 0.5 MDa large TET2 aminopeptidase, a prototypical protease important for cellular homeostasis, degrades peptides within a ca. 60 Å wide tetrahedral chamber with four lateral openings. The mechanisms of substrate trafficking and processing remain debated. Here, we integrate magic-angle spinning (MAS) NMR, mutagenesis, co-evolution analysis and molecular dynamics simulations and reveal that a loop in the catalytic chamber is a key element for enzymatic function. The loop is able to stabilize ligands in the active site and may additionally have a direct role in activating the catalytic water molecule whereby a conserved histidine plays a key role. Our data provide a strong case for the functional importance of highly dynamic - and often overlooked - parts of an enzyme, and the potential of MAS NMR to investigate their dynamics at atomic resolution.}, author = {Gauto, Diego F. and Macek, Pavel and Malinverni, Duccio and Fraga, Hugo and Paloni, Matteo and Sučec, Iva and Hessel, Audrey and Bustamante, Juan Pablo and Barducci, Alessandro and Schanda, Paul}, issn = {2041-1723}, journal = {Nature Communications}, publisher = {Springer Nature}, title = {{Functional control of a 0.5 MDa TET aminopeptidase by a flexible loop revealed by MAS NMR}}, doi = {10.1038/s41467-022-29423-0}, volume = {13}, year = {2022}, } @inproceedings{11180, abstract = {Designing and implementing efficient parallel priority schedulers is an active research area. An intriguing proposed design is the Multi-Queue: given n threads and m ≥ n distinct priority queues, task insertions are performed uniformly at random, while, to delete, a thread picks two queues uniformly at random, and removes the observed task of higher priority. This approach scales well, and has probabilistic rank guarantees: roughly, the rank of each task removed, relative to remaining tasks in all other queues, is O (m) in expectation. Yet, the performance of this pattern is below that of well-engineered schedulers, which eschew theoretical guarantees for practical efficiency. We investigate whether it is possible to design and implement a Multi-Queue-based task scheduler that is both highly-efficient and has analytical guarantees. We propose a new variant called the Stealing Multi-Queue (SMQ), a cache-efficient variant of the Multi-Queue, which leverages both queue affinity---each thread has a local queue, from which tasks are usually removed; but, with some probability, threads also attempt to steal higher-priority tasks from the other queues---and task batching, that is, the processing of several tasks in a single insert / remove step. These ideas are well-known for task scheduling without priorities; our theoretical contribution is showing that, despite relaxations, this design can still provide rank guarantees, which in turn implies bounds on total work performed. We provide a general SMQ implementation which can surpass state-of-the-art schedulers such as OBIM and PMOD in terms of performance on popular graph-processing benchmarks. Notably, the performance improvement comes mainly from the superior rank guarantees provided by our scheduler, confirming that analytically-reasoned approaches can still provide performance improvements for priority task scheduling.}, author = {Postnikova, Anastasiia and Koval, Nikita and Nadiradze, Giorgi and Alistarh, Dan-Adrian}, booktitle = {Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming}, isbn = {9781450392044}, location = {Seoul, Republic of Korea}, pages = {353--367}, publisher = {Association for Computing Machinery}, title = {{Multi-queues can be state-of-the-art priority schedulers}}, doi = {10.1145/3503221.3508432}, year = {2022}, } @inproceedings{11181, abstract = {To maximize the performance of concurrent data structures, researchers have often turned to highly complex fine-grained techniques, resulting in efficient and elegant algorithms, which can however be often difficult to understand and prove correct. While simpler techniques exist, such as transactional memory, they can have limited performance or portability relative to their fine-grained counterparts. Approaches at both ends of this complexity-performance spectrum have been extensively explored, but relatively less is known about the middle ground: approaches that are willing to sacrifice some performance for simplicity, while remaining competitive with state-of-the-art handcrafted designs. In this paper, we explore this middle ground, and present PathCAS, a primitive that combines ideas from multi-word CAS (KCAS) and transactional memory approaches, while carefully avoiding overhead. We show how PathCAS can be used to implement efficient search data structures relatively simply, using an internal binary search tree as an example, then extending this to an AVL tree. Our best implementations outperform many handcrafted search trees: in search-heavy workloads, it rivals the BCCO tree [5], the fastest known concurrent binary tree in terms of search performance [3]. Our results suggest that PathCAS can yield concurrent data structures that are relatively easy to build and prove correct, while offering surprisingly high performance.}, author = {Brown, Trevor A and Sigouin, William and Alistarh, Dan-Adrian}, booktitle = {Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming}, isbn = {9781450392044}, location = {Seoul, Republic of Korea}, pages = {385--399}, publisher = {Association for Computing Machinery}, title = {{PathCAS: An efficient middle ground for concurrent search data structures}}, doi = {10.1145/3503221.3508410}, year = {2022}, } @article{11182, abstract = {Immune cells are constantly on the move through multicellular organisms to explore and respond to pathogens and other harmful insults. While moving, immune cells efficiently traverse microenvironments composed of tissue cells and extracellular fibers, which together form complex environments of various porosity, stiffness, topography, and chemical composition. In this protocol we describe experimental procedures to investigate immune cell migration through microenvironments of heterogeneous porosity. In particular, we describe micro-channels, micro-pillars, and collagen networks as cell migration paths with alternative pore size choices. Employing micro-channels or micro-pillars that divide at junctions into alternative paths with initially differentially sized pores allows us to precisely (1) measure the cellular translocation time through these porous path junctions, (2) quantify the cellular preference for individual pore sizes, and (3) image cellular components like the nucleus and the cytoskeleton. This reductionistic experimental setup thus can elucidate how immune cells perform decisions in complex microenvironments of various porosity like the interstitium. The setup further allows investigation of the underlying forces of cellular squeezing and the consequences of cellular deformation on the integrity of the cell and its organelles. As a complementary approach that does not require any micro-engineering expertise, we describe the usage of three-dimensional collagen networks with different pore sizes. Whereas we here focus on dendritic cells as a model for motile immune cells, the described protocols are versatile as they are also applicable for other immune cell types like neutrophils and non-immune cell types such as mesenchymal and cancer cells. In summary, we here describe protocols to identify the mechanisms and principles of cellular probing, decision making, and squeezing during cellular movement through microenvironments of heterogeneous porosity.}, author = {Kroll, Janina and Ruiz-Fernandez, Mauricio J.A. and Braun, Malte B. and Merrin, Jack and Renkawitz, Jörg}, issn = {2691-1299}, journal = {Current Protocols}, number = {4}, publisher = {Wiley}, title = {{Quantifying the probing and selection of microenvironmental pores by motile immune cells}}, doi = {10.1002/cpz1.407}, volume = {2}, year = {2022}, } @inproceedings{11183, abstract = {Subgraph detection has recently been one of the most studied problems in the CONGEST model of distributed computing. In this work, we study the distributed complexity of problems closely related to subgraph detection, mainly focusing on induced subgraph detection. The main line of this work presents lower bounds and parameterized algorithms w.r.t structural parameters of the input graph: - On general graphs, we give unconditional lower bounds for induced detection of cycles and patterns of treewidth 2 in CONGEST. Moreover, by adapting reductions from centralized parameterized complexity, we prove lower bounds in CONGEST for detecting patterns with a 4-clique, and for induced path detection conditional on the hardness of triangle detection in the congested clique. - On graphs of bounded degeneracy, we show that induced paths can be detected fast in CONGEST using techniques from parameterized algorithms, while detecting cycles and patterns of treewidth 2 is hard. - On graphs of bounded vertex cover number, we show that induced subgraph detection is easy in CONGEST for any pattern graph. More specifically, we adapt a centralized parameterized algorithm for a more general maximum common induced subgraph detection problem to the distributed setting. In addition to these induced subgraph detection results, we study various related problems in the CONGEST and congested clique models, including for multicolored versions of subgraph-detection-like problems.}, author = {Nikabadi, Amir and Korhonen, Janne}, booktitle = {25th International Conference on Principles of Distributed Systems}, editor = {Bramas, Quentin and Gramoli, Vincent and Milani, Alessia}, isbn = {9783959772198}, issn = {1868-8969}, location = {Strasbourg, France}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters}}, doi = {10.4230/LIPIcs.OPODIS.2021.15}, volume = {217}, year = {2022}, }