We study counting problems for several types of orientations of chordal graphs: source-sink-free orientations, sink-free orientations, acyclic orientations, and bipolar orientations, and, for the latter two, we also present linear-time uniform samplers. Counting sink-free, acyclic, or bipolar orientations are known to be #P-complete for general graphs,
motivating our study on a restricted, yet well-studied, graph class. Our
main focus is source-sink-free orientations, a natural restricted version of
sink-free orientations related to strong orientations, which we introduce
in this work. These orientations are intriguing, since despite their similarity,
currently known FPRAS and sampling techniques (such as Markov
chains or sink-popping) that apply to sink-free orientations do not seem
to apply to source-sink-free orientations. We present fast polynomialtime
algorithms counting these orientations on chordal graphs. Our approach
combines dynamic programming with inclusion-exclusion (going
two levels deep for source-sink-free orientations and one level for sinkfree
orientations) throughout the computation. Dynamic programming
counting algorithms can be typically used to produce a uniformly random
sample. However, due to the negative terms of the inclusion-exclusion,
the typical approach to obtain a polynomial-time sampling algorithm
does not apply in our case. Obtaining such an almost uniform sampling
algorithm for source-sink-free orientations in chordal graphs remains an
open problem.
Little is known about counting or sampling of acyclic or bipolar orientations,
even on restricted graph classes. We design efficient (linear-time)
exact uniform sampling algorithms for these orientations on chordal
graphs. These algorithms are a byproduct of our counting algorithms,
but unlike in other works that provide dynamic-programming-based samplers,
we produce a random orientation without computing the corresponding
count, which leads to a faster running time than the counting
algorithm (since it avoids manipulation of large integers).
more »
« less
From foraging trails to transport networks: how the quality-distance trade-off shapes network structure
Biological systems are typically dependent on transportation networks for the efficient distribution of resources and information. Revealing the decentralized mechanisms underlying the generative process of these networks is key in our global understanding of their functions and is of interest to design, manage and improve human transport systems. Ants are a particularly interesting taxon to address these issues because some species build multi-sink multi-source transport networks analogous to human ones. Here, by combining empirical field data and modelling at several scales of description, we show that pre-existing mechanisms of recruitment with positive feedback involved in foraging can account for the structure of complex ant transport networks. Specifically, we find that emergent group-level properties of these empirical networks, such as robustness, efficiency and cost, can arise from models built on simple individual-level behaviour addressing a quality-distance trade-off by the means of pheromone trails. Our work represents a first step in developing a theory for the generation of effective multi-source multi-sink transport networks based on combining exploration and positive reinforcement of best sources.
more »
« less
- NSF-PAR ID:
- 10232292
- Date Published:
- Journal Name:
- Proceedings of the Royal Society B: Biological Sciences
- Volume:
- 288
- Issue:
- 1949
- ISSN:
- 0962-8452
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Ryan, Michael (Ed.)Abstract Increasing evidence suggests that tree growth is sink-limited by environmental and internal controls rather than by carbon availability. However, the mechanisms underlying sink-limitations are not fully understood and thus not represented in large-scale vegetation models. We develop a simple, analytically solved, mechanistic, turgor-driven growth model (TDGM) and a phloem transport model (PTM) to explore the mechanics of phloem transport and evaluate three hypotheses. First, phloem transport must be explicitly considered to accurately predict turgor distributions and thus growth. Second, turgor-limitations can explain growth-scaling with size (metabolic scaling). Third, turgor can explain realistic growth rates and increments. We show that mechanistic, sink-limited growth schemes based on plant turgor limitations are feasible for large-scale model implementations with minimal computational demands. Our PTM predicted nearly uniform sugar concentrations along the phloem transport path regardless of phloem conductance, stem water potential gradients and the strength of sink-demands contrary to our first hypothesis, suggesting that phloem transport is not limited generally by phloem transport capacity per se but rather by carbon demand for growth and respiration. These results enabled TDGM implementation without explicit coupling to the PTM, further simplifying computation. We test the TDGM by comparing predictions of whole-tree growth rate to well-established observations (site indices) and allometric theory. Our simple TDGM predicts realistic tree heights, growth rates and metabolic scaling over decadal to centurial timescales, suggesting that tree growth is generally sink and turgor limited. Like observed trees, our TDGM captures tree-size- and resource-based deviations from the classical ¾ power-law metabolic scaling for which turgor is responsible.more » « less
-
more » « less
Abstract Rigorous understanding of how environmental conditions impact population dynamics is essential for species conservation, especially in mixed‐use landscapes where source–sink dynamics may be at play. Conservation of large carnivore populations in fragmented, human‐dominated landscapes is critical for their long‐term persistence. However, living in human‐dominated landscapes comes with myriad costs, including direct anthropogenic mortality and sublethal energetic costs. How these costs impact individual fitness and population dynamics are not fully understood, partly due to the difficulty in collecting long‐term demographic data for these species. Here, we analyzed an 11‐year dataset on puma (
Puma concolor ) space use, mortality, and reproduction in the Santa Cruz Mountains, California, USA, to quantify how living in a fragmented landscape impacts individual survival and population dynamics. Long‐term exposure to housing density drove mortality risk for female pumas, resulting in an 18‐percentage‐point reduction in annual survival for females in exurban versus remote areas. While the overall population growth rate appeared stable, reduced female survival in more developed areas resulted in source–sink dynamics across the study area, with 42.1% of the Santa Cruz Mountains exhibiting estimated population growth rates <1. Since habitat selection is often used as a proxy for habitat quality, we also assessed whether puma habitat selection predicted source and sink areas. Patterns of daytime puma habitat selection predicted source areas, while time‐of‐day‐independent habitat selection performed less well as a proxy. These results illuminate the individual‐ and population‐level consequences of habitat fragmentation for large carnivores, illustrating that habitat fragmentation can produce source–sink dynamics that may not be apparent from other metrics of habitat quality. Locally, conserving high‐quality source habitat within the Santa Cruz Mountains is necessary to support long‐term puma population persistence. More broadly, source–sink dynamics may at play for other carnivore populations in similar fragmented systems, and linking landscape conditions to population dynamics is essential for effective conservation. Caution should be used in inferring habitat quality from habitat selection alone, but these results shed light on metrics of selection that may be better or worse proxies to identify source areas for large carnivores. -
Dovrolis, Constantine (Ed.)more » « less
A preemptive multi-hop contact tracing scheme that tracks not only the direct contacts of those who tested positive for COVID-19, but also secondary or tertiary contacts has been proposed and deployed in practice with some success. We propose a mathematical methodology for evaluating this preemptive contact tracing strategy that combines the contact tracing dynamics and the virus transmission mechanism in a single framework using microscopic Markov Chain approach (MMCA). We perform Monte Carlo (MC) simulations to validate our model and show that the output of our model provides a reasonable match with the result of MC simulations. Utilizing the formulation under a human contact network generated from real-world data, we show that the cost-benefit tradeoff can be significantly enhanced through an implementation of the multi-hop contact tracing as compared to traditional contact tracing. We further shed light on the mechanisms behind the effectiveness of the multi-hop testing strategy using the framework. We show that our mathematical framework allows significantly faster computation of key attributes for multi-hop contact tracing as compared to MC simulations. This in turn enables the investigation of these attributes for large contact networks, and constitutes a significant strength of our approach as the contact networks that arise in practice are typically large.
-
more » « less
Large-pore channels permeable to small molecules such as ATP, in addition to atomic ions, are emerging as important regulators in health and disease. Nonetheless, their mechanisms of molecular permeation and selectivity remain mostly unexplored. Combining fluorescence microscopy and electrophysiology, we developed a novel technique that allows kinetic analysis of molecular permeation through connexin and CALHM1 channels in Xenopus oocytes rendered translucent. Using this methodology, we found that (1) molecular flux through these channels saturates at low micromolar concentrations, (2) kinetic parameters of molecular transport are sensitive to modulators of channel gating, (3) molecular transport and ionic currents can be differentially affected by mutation and gating, and (4) N-terminal regions of these channels control transport kinetics and permselectivity. Our methodology allows analysis of how human disease–causing mutations affect kinetic properties and permselectivity of molecular signaling and enables the study of molecular mechanisms, including selectivity and saturability, of molecular transport in other large-pore channels.
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1098/rspb.2021.0430
