TY - JOUR
AB - One of the oldest hypotheses for the advantage of recombination is that recombination allo rvs beneficial mutations that arise in different individuals to be placed together on the same chromosome. Unless recombination occurs, one of the beneficial alleles is doomed to extinction, slowing the rate at which adaptive mutations are incorporated within a population. We model the effects of a modifier of recombination on the fixation probability of beneficial mutations when beneficial alleles are segregating at other loci. We find that modifier alleles that increase recombination do increase the fixation probability of beneficial mutants and subsequently hitchhike along as the mutants rise in frequency. The strength of selection favoring a modifier that increases recombination is proportional to lambda(2)S delta r/r when linkage is tight and lambda(2)S(3) delta r/N when linkage is loose, where lambda is the beneficial mutation rate per genome per generation throughout a population of size N, S is the average mutant effect, r is the average recombination rate, and delta ris the amount that recombination is modified. We conclude that selection for recombination will be substantial only if there is tight linkage within the genome or if many loci are subject to directional selection as during periods of rapid evolutionary change.
AU - Otto, Sarah P
AU - Nicholas Barton
ID - 4285
IS - 2
JF - Genetics
TI - The evolution of recombination: Removing the limits to natural selection
VL - 147
ER -
TY - JOUR
AB - A local barrier to gene flow will delay the spread of an advantageous allele. Exact calculations for the deterministic case show that an allele that is favorable when rare is delayed very little even by a strong barrier; its spread is allowed by a time proportional to log((B/σ)√2S)/S, where B is the barrier strength, σ the dispersal range, and fitnesses are 1:1 + S:1 + 2S. However, when there is selection against heterozytes, such that the allele cannot increase from low frequency, a barrier can cause a much greater delay. If gene flow is reduced below a critical value, spread is entirely prevented. Stochastic simulations show that with additive selection, random drift slows down the spread of the allele, below the deterministic speed of σ√2S. The delay to the advance of an advantageous allele caused by a strong barrier can be substantially increased by random drift and increases with B/(2Sρσ2) in a one-dimensional habitat of density ρ. However, with selection against heterozygotes, drift can facilitate the spread and can free an allele that would otherwise be trapped indefinitely by a strong barrier. We discuss the implications of these results for the evolution of chromosome rearrangements.
AU - Piálek, Jaroslav
AU - Nicholas Barton
ID - 4286
IS - 2
JF - Genetics
TI - The spread of an advantageous allele across a barrier: the effects of random drift and selection against heterozygotes
VL - 145
ER -
TY - GEN
AB - We evaluate Sewall Wright's three-phase 'shifting balance' theory of evolution, examining both the theoretical issues and the relevant data from nature and the laboratory. We conclude that while phases I and II of Wright's theory (the movement of populations from one 'adaptive peak' to another via drift and selection) can occur under some conditions, genetic drift is often unnecessary for movement between peaks. Phase III of the shifting balance, in which adaptations spread from particular populations to the entire species, faces two major theoretical obstacles: (1) unlike adaptations favored by simple directional selection, adaptations whose fixation requires some genetic drift are often prevented from spreading by barriers to gene flow; and (2) it is difficult to assemble complex adaptations whose constituent parts arise via peak shifts in different demes. Our review of the data from nature shows that although there is some evidence for individual phases of the shifting balance process, there are few empirical observations explained better by Wright's three-phase mechanism than by simple mass selection. Similarly, artificial selection experiments fail to show that selection in subdivided populations produces greater response than does mass selection in large populations. The complexity of the shifting balance process and the difficulty of establishing that adaptive valleys have been crossed by genetic drift make it impossible to test Wright's claim that adaptations commonly originate by this process. In view of these problems, it seems unreasonable to consider the shifting balance process as an important explanation for the evolution of adaptations.
AU - Coyne, Jerry A
AU - Nicholas Barton
AU - Turelli, Michael
ID - 4287
IS - 3
T2 - Evolution; International Journal of Organic Evolution
TI - Perspective: A critique of Sewall Wright's shifting balance theory of evolutionight's shifting balance theory of evolution
VL - 51
ER -
TY - JOUR
AB - We measured the heterozygous effects on net fitness of a sample of 12 wild-type third chromosomes in D. melanogaster. Effects on fitness were assessed by competing the wild-type chromosomes against balancer chromosomes, to prevent the production of recombinants. The measurements were carried out in the population cage environment in which the life history had been evolving, in an undisturbed population with overlapping generations, and replicated measurements were made on each chromosome to control for confounding effects such as mutation accumulation. We found significant variation among the wild type chromosomes in their additive genetic effect on net fitness. The system provides an opportunity to obtain an accurate estimate of the distribution of heterozygous effects on net fitness, the contribution of different fitness components including male mating success, and the role of intra-chromosomal epistasis in fitness variation.
AU - Fowler, Kevin
AU - Semple, Colin
AU - Nicholas Barton
AU - Partridge, Linda
ID - 4288
IS - 1379
JF - Proceedings of the Royal Society of London Series B Biological Sciences
TI - Genetic variation for total fitness in Drosophila melanogaster
VL - 264
ER -
TY - GEN
AB - A worldwide survey of polymorphic molecular markers shows that the human population is genetically homogeneous, in close agreement with evidence from quite different genes and traits.
AU - Nicholas Barton
ID - 4289
IS - 12
T2 - Current Biology
TI - Population genetics: A new apportionment of human diversity
VL - 7
ER -
TY - GEN
AU - Nicholas Barton
ID - 4290
IS - 2
T2 - Genetical Research
TI - Natural hybridization and evolution
VL - 70
ER -
TY - GEN
AU - Nicholas Barton
ID - 4291
IS - 2
T2 - Genetical Research
TI - The ccological detective: Confronting models with data
VL - 70
ER -
TY - CHAP
AB - Natural populations differ from the simplest models in ways which can significantly affect their evolution. Real populations are rarely all of the same size; the rates of migration into and out of populations vary in space and time; some populations go extinct, and new ones are established, while all populations fluctuate in size. Furthermore, the genetic properties of real species are not like those assumed in simple models. Alleles are exposed to a wide variety of selection mutation rarely creates novel genotypes with each mutation event, generations overlap, and environments vary from place to place. Evolution in a metapopulation can be substantially different from the predictions of single-population models and, indeed, very different from the simplest models of subdivided species.
AU - Nicholas Barton
AU - Whitlock, Michael
ID - 4293
T2 - Metapopulation Biology
TI - The evolution of metapopulations
ER -
TY - CONF
AB - In temporal-logic model checking, we verify the correctness of a program with respect to a desired behavior by checking whether a structure that models the program satisfies a temporal-logic formula that specifies the behavior. The model-checking problem for the branching-time temporal logic CTL can be solved in linear running time, and model-checking tools for CTL are used successfully in industrial applications. The development of programs that must meet rigid real-time constraints has brought with it a need for real-time temporal logics that enable quantitative reference to time. Early research on real-time temporal logics uses the discrete domain of the integers to model time. Present research on real-time temporal logics focuses on continuous time and uses the dense domain of the reals to model time. There, model checking becomes significantly more complicated. For example, the model-checking problem for TCTL, a continuous-time extension of the logic CTL, is PSPACE-complete.
In this paper we suggest a reduction from TCTL model checking to CTL model checking. The contribution of such a reduction is twofold. Theoretically, while it has long been known that model-checking methods for untimed temporal logics can be extended quite easily to handle discrete time, it was not clear whether and how untimed methods can handle the reset quantifier of TCTL, which resets a realvalued clock. Practically, our reduction enables anyone who has a tool for CTL model checking to use it for TCTL model checking. The TCTL model-checking algorithm that follows from our reduction is in PSPACE, matching the known bound for this problem. In addition, it enjoys the wide distribution of CTL model-checking tools and the extensive and fruitful research efforts and heuristics that have been put into these tools.
AU - Thomas Henzinger
AU - Kupferman, Orna
ID - 4438
TI - From quantity to quality
VL - 1201
ER -
TY - CONF
AB - Rectangular hybrid automata model digital control programs of analog plant environments. We study rectangular hybrid automata where the plant state evolves continuously in real-numbered time, and the controller samples the plant state and changes the control state discretely, only at the integer points in time. We prove that rectangular hybrid automata have finite bisimilarity quotients when all control transitions happen at integer times, even if the constraints on the derivatives of the variables vary between control states. This is sharply in contrast with the conventional model where control transitions may happen at any real time, and already the reachability problem is undecidable. Based on the finite bisimilarity quotients, we give an exponential algorithm for the symbolic sampling-controller synthesis of rectangular automata. We show our algorithm to be optimal by proving the problem to be EXPTIME-hard. We also show that rectangular automata form a maximal class of systems for which the sampling-controller synthesis problem can be solved algorithmically.
AU - Thomas Henzinger
AU - Kopke, Peter W
ID - 4441
TI - Discrete-time control for rectangular hybrid automata
VL - 1256
ER -
TY - JOUR
AU - Thomas Henzinger
AU - Ho, Pei-Hsin
AU - Wong-Toi, Howard
ID - 4493
IS - 1-2
JF - Software Tools For Technology Transfer
TI - HyTech: A model checker for hybrid systems
VL - 1
ER -
TY - CONF
AB - A hybrid system consists of a collection of digital programs that interact with each other and with an analog environment. Examples of hybrid systems include medical equipment, manufacturing controllers, automotive controllers, and robots. The formal analysis of the mixed digital-analog nature of these systems requires a model that incorporates the discrete behavior of computer programs with the continuous behavior of environment variables, such as temperature and pressure. Hybrid automata capture both types of behavior by combining finite automata with differential inclusions (i.e. differential inequalities). HyTech is a symbolic model checker for linear hybrid automata, an expressive, yet automatically analyzable, subclass of hybrid automata. A key feature of HyTech is its ability to perform parametric analysis, i.e. to determine the values of design parameters for which a linear hybrid automaton satisfies a temporal requirement.
AU - Thomas Henzinger
AU - Ho, Pei-Hsin
AU - Wong-Toi, Howard
ID - 4494
TI - HyTech: A model checker for hybrid systems
VL - 1254
ER -
TY - CONF
AB - The simulation preorder for labeled transition systems is defined locally as a game that relates states with their immediate successor states. Liveness assumptions about transition systems are typically modeled using fairness constraints. Existing notions of simulation for fair transition systems, however, are not local, and as a result, many appealing properties of the simulation preorder are lost. We extend the local definition of simulation to account for fairness: system S fairly simulates system I iff in the simulation game, there is a strategy that matches with each fair computation of I a fair computation of S. Our definition enjoys a fully abstract semantics and has a logical characterization: S fairly simulates I iff every fair computation tree embedded in the unrolling of I can be embedded also in the unrolling of S or, equivalently, iff every Fair-AFMC formula satisfied by I is satisfied also by S (AFMC is the universal fragment of the alternation-free -calculus). The locality of the definition leads us to a polynomial-time algorithm for checking fair simulation for finite-state systems with weak and strong fairness constraints. Finally, fair simulation implies fair trace-containment, and is therefore useful as an efficientlycomputable local criterion for proving linear-time abstraction hierarchies.
AU - Thomas Henzinger
AU - Kupferman, Orna
AU - Rajamani, Sriram K
ID - 4496
TI - Fair simulation
VL - 1243
ER -
TY - CONF
AB - We define robust timed automata, which are timed automata that accept all trajectories robustly: if a robust timed automaton accepts a trajectory, then it must accept neighboring trajectories also; and if a robust timed automaton rejects a trajectory, then it must reject neighboring trajectories also. We show that the emptiness problem for robust timed automata is still decidable, by modifying the region construction for timed automata. We then show that, like timed automata, robust timed automata cannot be determinized. This result is somewhat unexpected, given that in temporal logic, the removal of realtime equality constraints is known to lead to a decidable theory that is closed under all boolean operations.
AU - Gupta, Vineet
AU - Thomas Henzinger
AU - Jagadeesan, Radha
ID - 4520
TI - Robust timed automata
VL - 1201
ER -
TY - CONF
AB - In a trace-based world, the modular specification, verification, and control of live systems require each module to be receptive; that is, each module must be able to meet its liveness assumptions no matter how the other modules behave. In a real-time world, liveness is automatically present in the form of diverging time. The receptiveness condition, then, translates to the requirement that a module must be able to let time diverge no matter how the environment behaves. We study the receptiveness condition for real-time systems by extending the model of reactive modules to timed and hybrid modules. We define the receptiveness of such a module as the existence of a winning strategy in a game of the module against its environment. By solving the game on region graphs, we present an (optimal) Exptime algorithm for checking the receptiveness of prepositional timed modules. By giving a fixpoint characterization of the game, we present a symbolic procedure for checking the receptiveness of linear hybrid modules. Finally, we present an assume-guarantee principle for reasoning about timed and hybrid modules, and a method for synthesizing receptive controllers of timed and hybrid modules.
AU - Alur, Rajeev
AU - Thomas Henzinger
ID - 4583
TI - Modularity for timed and hybrid systems
VL - 1243
ER -
TY - JOUR
AB - This paper introduces, gently but rigorously, the clock approach to real-time programming. We present with mathematical precision, assuming no prerequisites other than familiarity with logical and programming notations, the concepts that are necessary for understanding, writing, and executing clock programs. In keeping with an expository style, all references are clustered in bibliographic remarks at the end of each section. The first appendix presents proof rules for verifying temporal properties of clock programs. The second appendix points to selected literature on formal methods and tools for programming with clocks. In particular, the timed automaton, which is a finite-state machine equipped with clocks, has become a standard paradigm for real-time model checking; it underlies the tools HyTech, Kronos, and Uppaal, which are discussed elsewhere in this volume.
AU - Alur, Rajeev
AU - Thomas Henzinger
ID - 4584
IS - 1-2
JF - Software Tools For Technology Transfer
TI - Real-time system = discrete system + clock variables
VL - 1
ER -
TY - CONF
AB - A hybrid system is a dynamical system whose behavior exhibits both discrete and continuous change. A hybrid automaton is a mathematical model for hybrid systems, which combines, in a single formalism, automaton transitions for capturing discrete change with differential equations for capturing continuous change. In this survey, we demonstrate symbolic algorithms for the verification of and controller synthesis for linear hybrid automata, a subclass of hybrid automata that can be analyzed automatically
AU - Alur, Rajeev
AU - Thomas Henzinger
AU - Wong-Toi, Howard
ID - 4605
TI - Symbolic analysis of hybrid systems
ER -
TY - JOUR
AB - We present a verification algorithm for duration properties of real-time systems. While simple real-time properties constrain the total elapsed time between events, duration properties constrain the accumulated satisfaction time of state predicates. We formalize the concept of durations by introducing duration measures for timed automata. A duration measure assigns to each finite run of a timed automaton a real number —the duration of the run— which may be the accumulated satisfaction time of a state predicate along the run. Given a timed automaton with a duration measure, an initial and a final state, and an arithmetic constraint, the duration-bounded reachability problem asks if there is a run of the automaton from the initial state to the final state such that the duration of the run satisfies the constraint. Our main result is an (optimal) PSPACE decision procedure for the duration-bounded reachability problem.
AU - Alur, Rajeev
AU - Courcoubetis, Costas
AU - Thomas Henzinger
ID - 4607
IS - 2
JF - Formal Methods in System Design
TI - Computing accumulated delays in real-time systems
VL - 11
ER -
TY - CONF
AB - State space explosion is a fundamental obstacle in formal verification of designs and protocols. Several techniques for combating this problem have emerged in the past few years, among which two are significant: partial-order reductions and symbolic state space search. In asynchronous systems, interleavings of independent concurrent events are equivalent, and only a representative interleaving needs to be explored to verify local properties. Partial-order methods exploit this redundancy and visit only a subset of the reachable states. Symbolic techniques, on the other hand, capture the transition relation of a system and the set of reachable states as boolean functions. In many cases, these functions can be represented compactly using binary decision diagrams (BDDs). Traditionally, the two techniques have been practiced by two different schools—partial-order methods with enumerative depth-first search for the analysis of asynchronous network protocols, and symbolic breadth-first search for the analysis of synchronous hardware designs. We combine both approaches and develop a method for using partial-order reduction techniques in symbolic BDD-based invariant checking. We present theoretical results to prove the correctness of the method, and experimental results to demonstrate its efficacy.
AU - Alur, Rajeev
AU - Brayton, Robert K
AU - Thomas Henzinger
AU - Qadeer,Shaz
AU - Rajamani, Sriram K
ID - 4608
TI - Partial-order reduction in symbolic state-space exploration
VL - 1254
ER -
TY - CONF
AB - Temporal logic comes in two varieties: linear-time temporal logic assumes implicit universal quantification over all paths that are generated by system moves; branching-time temporal logic allows explicit existential and universal quantification over all paths. We introduce a third, more general variety of temporal logic: alternating-time temporal logic offers selective quantification over those paths that are possible outcomes of games, such as the game in which the system and the environment alternate moves. While linear-time and branching-time logics are natural specification languages for closed systems, alternating-time logics are natural specification languages for open systems. For example, by preceding the temporal operator “eventually” with a selective path quantifier, we can specify that in the game between the system and the environment, the system has a strategy to reach a certain state. Also the problems of receptiveness, realizability, and controllability can be formulated as model-checking problems for alternating-time formulas
AU - Alur, Rajeev
AU - Thomas Henzinger
AU - Kupferman, Orna
ID - 4609
TI - Alternating-time temporal logic
ER -