TY - JOUR AB - We develop fast algorithms for computing the linking number of a simplicial complex within a filtration.We give experimental results in applying our work toward the detection of non-trivial tangling in biomolecules, modeled as alpha complexes. AU - Edelsbrunner, Herbert AU - Zomorodian, Afra ID - 3584 IS - 2 JF - Homology, Homotopy and Applications TI - Computing linking numbers of a filtration VL - 5 ER - TY - JOUR AB - Stable hybrid zones in which ecologically divergent taxa give rise to a range of recombinants are natural laboratories in which the genetic basis of adaptation and reproductive isolation can be unraveled. One such hybrid zone is formed by the fire-bellied toads Bombina bombina and B. variegata (Anura: Discoglossidae). Adaptations to permanent and ephemeral breeding habitats, respectively, have shaped numerous phenotypic differences between the taxa. All of these are, in principle, candidates for a genetic dissection via QTL mapping. We present here a linkage map of 28 codominant and 10 dominant markers in the Bombina genome. In an F2 cross, markers that were mainly microsatellites, SSCPs or allozymes were mapped to 20 linkage groups. Among the 40 isolated CA microsatellites, we noted a preponderance of compound and frequently interleaved CA-TA repeats as well as a striking polarity at the 5′ end of the repeats. AU - Nürnberger, Beate AU - Hofman, Sebastian AU - Förg-Brey, Bqruni AU - Praetzel, Gabriele AU - Maclean, Alan W AU - Szymura, Jacek M AU - Abbott, Catherine M AU - Nicholas Barton ID - 3620 IS - 2 JF - Heredity TI - A linkage map for the hybridising toads Bombina bombina and B. variegata (Anura: Discoglossidae) VL - 91 ER - TY - JOUR AB - What is the chance that some part of a stretch of genome will survive? In a population of constant size, and with no selection, the probability of survival of some part of a stretch of map length y<1 approaches View the MathML source for View the MathML source. Thus, the whole genome is certain to be lost, but the rate of loss is extremely slow. This solution extends to give the whole distribution of surviving block sizes as a function of time. We show that the expected number of blocks at time t is 1+yt and give expressions for the moments of the number of blocks and the total amount of genome that survives for a given time. The solution is based on a branching process and assumes complete interference between crossovers, so that each descendant carries only a single block of ancestral material. We consider cases where most individuals carry multiple blocks, either because there are multiple crossovers in a long genetic map, or because enough time has passed that most individuals in the population are related to each other. For species such as ours, which have a long genetic map, the genome of any individual which leaves descendants (∼80% of the population for a Poisson offspring number with mean two) is likely to persist for an extremely long time, in the form of a few short blocks of genome. AU - Baird, Stuart J AU - Nicholas Barton AU - Etheridge, Alison M ID - 3619 IS - 4 JF - Theoretical Population Biology TI - The distribution of surviving blocks of an ancestral genome VL - 64 ER - TY - JOUR AB - There are several analyses in evolutionary ecology which assume that a family of offspring has come from only two parents. Here, we present a simple test for detecting when a batch involves two or more subfamilies. It is based on the fact that the mixing of families generates associations amongst unlinked marker loci. We also present simulations illustrating the power of our method for varying numbers of loci, alleles per locus and genotyped individuals. AU - Vines, Timothy H AU - Nicholas Barton ID - 3618 IS - 7 JF - Molecular Ecology TI - A new approach to detecting mixed families VL - 12 ER - TY - JOUR AB - We use the lac operon in Escherichia coli as a prototype system to illustrate the current state, applicability, and limitations of modeling the dynamics of cellular networks. We integrate three different levels of description (molecular, cellular, and that of cell population) into a single model, which seems to capture many experimental aspects of the system. AU - Vilar,Jose M AU - Calin Guet AU - Leibler, Stanislas ID - 3752 IS - 3 JF - Journal of Cell Biology TI - Modeling network dynamics: the lac operon, a case study VL - 161 ER - TY - JOUR AU - Bauer, Wolfgang AU - Kleine Berkenbusch, Marco AU - Bollenbach, Mark Tobias ID - 3797 IS - 4 JF - Revista Mexicana De Fisica TI - Breaking atomic nuclei into little pieces: evidence for a phase transition VL - 49 ER - TY - CONF AB - Many verification, planning, and control problems can be modeled as games played on state-transition graphs by one or two players whose conflicting goals are to form a path in the graph. The focus here is on simple stochastic parity games, that is, two-player games with turn-based probabilistic transitions and omega-regular objectives formalized as parity (Rabin chain) winning conditions. An efficient translation from simple stochastic parity games to nonstochastic parity games is given. As many algorithms are known for solving the latter, the translation yields efficient algorithms for computing the states of a simple stochastic parity game from which a player can win with probability 1. An important special case of simple stochastic parity games are the Markov decision processes with Buchi objectives. For this special case a first provably subquadratic algorithm is given for computing the states from which the single player has a strategy to achieve a Buchi objective with probability 1. For game graphs with m edges the algorithm works in time O(mrootm). Interestingly, a similar technique sheds light on the question of the computational complexity of solving simple Buchi games and yields the first provably subquadratic algorithm, with a running time of O(n(2)/log n) for game graphs with n vertices and O(n) edges. AU - Krishnendu Chatterjee AU - Jurdziński, Marcin AU - Thomas Henzinger ID - 3897 TI - Simple stochastic parity games VL - 2803 ER - TY - CONF AB - We study the problem of determining stack boundedness and the exact maximum stack size for three classes of interrupt-driven programs. Interrupt-driven programs axe used in many real-time applications that require responsive interrupt handling. In order to ensure responsiveness, programmers often enable interrupt processing in the body of lower-priority interrupt handlers. In such programs a programming error can allow interrupt handlers to be interrupted in cyclic fashion to lead to an unbounded stack, causing the system to crash. For a restricted class of interrupt-driven programs, we show that there is a polynomial-time procedure to check stack boundedness, while determining the exact maximum stack size is PSPACE-complete. For a larger class of programs, the two problems are both PSPACE-complete, and for the largest class of programs we consider, the two problems are PSPACE-hard and can be solved in exponential time. AU - Krishnendu Chatterjee AU - Ma, Di AU - Majumdar, Ritankar S AU - Zhao, Tian AU - Thomas Henzinger AU - Palsberg, Jens ID - 3898 TI - Stack size analysis for interrupt-driven programs VL - 2694 ER - TY - JOUR AB - We present algorithms for constructing a hierarchy of increasingly coarse Morse-Smale complexes that decompose a piecewise linear 2-manifold. While these complexes are defined only in the smooth category, we extend the construction to the piecewise linearcategory by ensuring structural integrity and simulating differentiability. We then simplify Morse-Smale complexes by canceling pairs of critical points in order of increasing persistence. AU - Herbert Edelsbrunner AU - Harer, John AU - Zomorodian, Afra ID - 3993 IS - 1 JF - Discrete & Computational Geometry TI - Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds VL - 30 ER - TY - JOUR AB - The body defined by a finite collection of disks is a subset of the plane bounded by a tangent continuous curve, which we call the skin. We give analytic formulas for the area, the perimeter, the area derivative, and the perimeter derivative of the body. Given the filtrations of the Delaunay triangulation and the Voronoi diagram of the disks, all formulas can be evaluated in time proportional to the number of disks. AU - Cheng, Ho-Lun AU - Herbert Edelsbrunner ID - 3994 IS - 2 JF - Computational Geometry: Theory and Applications TI - Area, perimeter and derivatives of a skin curve VL - 26 ER -