TY - JOUR
AB - Vertebrate gastrulation involves the specification and coordinated movement of large populations of cells that give rise to the ectodermal, mesodermal and endodermal germ layers. Although many of the genes involved in the specification of cell identity during this process have been identified, little is known of the genes that coordinate cell movement. Here we show that the zebrafish silberblick (slb) locus(1) encodes Wnt11 and that Slb/Wnt11 activity is required for cells to undergo correct convergent extension movements during gastrulation. In the absence of Slb/Wnt11 function, abnormal extension of axial tissue results in cyclopia and other midline defects in the head(2). The requirement for Slb/Wnt11 is cell non-autonomous, and our results indicate that the correct extension of axial tissue is at least partly dependent on medio-lateral cell intercalation in paraxial tissue. We also show that the slb phenotype is rescued by a truncated form of Dishevelled that does not signal through the canonical Wnt pathway(3), suggesting that, as in flies(4), Wnt signalling might mediate morphogenetic events through a divergent signal transduction cascade. Our results provide genetic and experimental evidence that Wnt activity in lateral tissues has a crucial role in driving the convergent extension movements underlying vertebrate gastrulation.
AU - Heisenberg, Carl-Philipp J
AU - Tada, Masazumi
AU - Rauch, Gerd
AU - Saúde, Leonor
AU - Concha, Miguel
AU - Geisler, Robert
AU - Stemple, Derek
AU - Smith, James
AU - Wilson, Stephen
ID - 4197
IS - 6782
JF - Nature
TI - Silberblick/Wnt11 mediates convergent extension movements during zebrafish gastrulation
VL - 405
ER -
TY - GEN
AB - In yeast, a modified protein known as a prion generates variation in growth rate across diverse environments. Is this an example of an agent that has evolved in order to promote its possessor's adaptability?
AU - Partridge, Linda
AU - Nicholas Barton
ID - 4268
IS - 6803
T2 - Nature
TI - Evolving evolvability
VL - 407
ER -
TY - JOUR
AU - Coyne, Jerry A
AU - Nicholas Barton
AU - Turelli, Michael
ID - 4269
IS - 1
JF - Evolution; International Journal of Organic Evolution
TI - Is Wright’s shifting balance process important in evolution?
VL - 54
ER -
TY - JOUR
AB - A coalescence-based maximum-likelihood method is presented that aims to (i) detect diversity-reducing events in the recent history of a population and (ii) distinguish between demographic (e.g., bottlenecks) and selective causes (selective sweep) of a recent reduction of genetic variability. The former goal is achieved by taking account of the distortion in the shape of gene genealogies generated by diversity-reducing events: gene trees tend to be more star-like than under the standard coalescent. The latter issue is addressed by comparing patterns between loci: demographic events apply to the whole genome whereas selective events affect distinct regions of the genome to a varying extent. The maximum-likelihood approach allows one to estimate the time and strength of diversity-reducing events and to choose among competing hypotheses. An application to sequence data from an African population of Drosophila melanogaster shows that the bottleneck hypothesis is unlikely and that one or several selective sweeps probably occurred in the recent history of this population.
AU - Galtier, Nicolas
AU - Depaulis, Frantz
AU - Nicholas Barton
ID - 4270
IS - 2
JF - Genetics
TI - Detecting bottlenecks and selective sweeps from DNA sequence polymorphism
VL - 155
ER -
TY - JOUR
AB - Within hybrid zones that are maintained by a balance between selection and dispersal, linkage disequilibrium is generated by the mixing of divergent populations. This linkage disequilibrium causes selection on each locus to act on all other loci, thereby steepening dines, and generating a barrier to gene flow. Diffusion models predict simple relations between the strength of linkage disequilibrium and the dispersal rate, σ, and between the barrier to gene flow, B, and the reduction in mean fitness, W̄. The aim of this paper is to test the accuracy of these predictions by comparison with an exact deterministic model of unlinked loci (r = 0.5). Disruptive selection acts on the proportion of alleles from the parental populations (p, q): W = exp[-S(4pq)(β)], such that the least fit genotype has fitness e(-S). Where β << 1, fitness is reduced for a wide range of intermediate genotypes; where β >> 1, fitness is only reduced for those genotypes close to p = 0.5. Even with strong epistasis, linkage disequilibria are close to σ2p'(i)p'(j)/r(ij), where p'(i), p'(j) are the gradients in allele frequency at loci i, j. The barrier to gene flow, which is reflected in the steepening of neutral dines, is given by B = ∫(-∞)(∞) (W̄(1/r̄)-1) dx, where r̄, the harmonic mean recombination rate between the neural and selected loci, is here 0.5. This is a close approximation for weak selection, but underestimates B for strong selection. The barrier is stronger for small β, because hybrid fitness is then reduced over a wider range of p. The widths of the selected dines are harder to predict: though simple approximations are accurate for β = 1, they become inaccurate for extreme β because, then, fitness changes sharply with p. Estimates of gene number, made from neutral dines on the assumption that selection acts against heterozygotes, are accurate for weak selection when β = 1; however, for strong selection, gene number is overestimated. For β > 1, gene number is systematically overestimated and, conversely, when β < 1, it is underestimated.
AU - Nicholas Barton
AU - Shpak, Max
ID - 4271
IS - 2
JF - Genetical Research
TI - The effects of epistasis on the structure of hybrid zones
VL - 75
ER -
TY - JOUR
AB - Analysis of multilocus evolution is usually intractable for more than n ~ 10 genes, because the frequencies of very large numbers of genotypes must be followed. An exact analysis of up to n ~ 100 loci is feasible for a symmetrical model, in which a set of unlinked loci segregate for two alleles (labeled '0' and '1') with interchangeable effects on fitness. All haploid genotypes with the same number of 1 alleles can then remain equally frequent. However, such a symmetrical solution may be unstable: for example, under stabilizing selection, populations tend to fix any one genotype which approaches the optimum. Here, we show how the 2' x 2' stability matrix can be decomposed into a set of matrices, each no larger than n x n. This allows the stability of symmetrical solutions to be determined. We apply the method to stabilizing and disruptive selection in a single deme and to selection against heterozygotes in a linear cline. (C) 2000 Academic Press.
AU - Nicholas Barton
AU - Shpak, Max
ID - 4272
IS - 3
JF - Theoretical Population Biology
TI - The stability of symmetrical solutions to polygenic models
VL - 57
ER -
TY - JOUR
AB - We review the various factors that limit adaptation by natural selection. Recent discussion of constraints on selection and, conversely, of the factors that enhance 'evolvability', have concentrated on the kinds of variation that can be produced. Here, we emphasise that adaptation depends on how the various evolutionary processes shape variation in populations. We survey the limits that population genetics places on adaptive evolution, and discuss the relationship between disparate literatures. BioEssays 22:1075-1084, 2000. (C) 2000 John Wiley and Sons, Inc.
AU - Nicholas Barton
AU - Partridge, Linda
ID - 4273
IS - 12
JF - Bioessays : News and Reviews in Molecular, Cellular and Developmental Biology
TI - Limits to natural selection
VL - 22
ER -
TY - JOUR
AB - Selection on one or more genes inevitably perturbs other genes, even when those genes have no direct effect on fitness. This article reviews the theory of such genetic hitchhiking, concentrating on effects on neutral loci. Maynard Smith and Haigh introduced the classical case where the perturbation is due to a single favourable mutation. This is contrasted with the apparently distinct effects of inherited variation in fitness due to loosely linked loci. A model of fluctuating selection is analysed which bridges these alternative treatments. When alleles sweep between extreme frequencies at a rate λ, the rate of drift is increased by a factor (1 + E[1/pq]λ/(2(2λ + r))), where the recombination rate r is much smaller than the strength of selection. In spatially structured populations, the effects of any one substitution are weaker, and only cause a local increase in the frequency of a neutral allele. This increase depends primarily on the rate of recombination relative to selection (r/s), and more weakly, on the neighbourhood size, Nb = 4πρσ2. Spatial subdivision may allow local selective sweeps to occur more frequently than is indicated by the overall rate of molecular evolution. However, it seems unlikely that such sweeps can be sufficiently frequent to increase significantly the drift of neutral alleles.
AU - Nicholas Barton
ID - 4274
IS - 1403
JF - Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences
TI - Genetic hitchhiking
VL - 355
ER -
TY - CHAP
AU - Nicholas Barton
ID - 4275
T2 - Encyclopedia of Biodiversity
TI - Differentiation
ER -
TY - GEN
AU - Nicholas Barton
ID - 4276
IS - 3
T2 - Genetical Research
TI - Population genetics of multiple loci
VL - 75
ER -
TY - CONF
AB - Bisimulations enjoy numerous applications in the analysis of labeled transition systems. Many of these applications are based on two central observations: first, bisimilar systems satisfy the same branching-time properties; second, bisimilarity can be checked efficiently for finite-state systems. The local character of bisimulation, however, makes it difficult to address liveness concerns. Indeed, the definitions of fair bisimulation that have been proposed in the literature sacrifice locality, and with it, also efficient checkability. We put forward a new definition of fair bisimulation which does not suffer from this drawback.
The bisimilarity of two systems can be viewed in terms of a game played between a protagonist and an adversary. In each step of the infinite bisimulation game, the adversary chooses one system, makes a move, and the protagonist matches it with a move of the other system. Consistent with this game-based view, we call two fair transition systems bisimilar if in the bisimulation game, the infinite path produced in the first system is fair iff the infinite path produced in the second system is fair.
We show that this notion of fair bisimulation enjoys the following properties. First, fairly bisimilar systems satisfy the same formulas of the logics Fair-AFMC (the fair alternation-free μ-calculus) and Fair-CTL*. Therefore, fair bisimulations can serve as property-preserving abstractions for these logics and weaker ones, such as Fair-CTL and LTL. Indeed, Fair-AFMC provides an exact logical characterization of fair bisimilarity. Second, it can be checked in time polynomial in the number of states if two systems are fairly bisimilar. This is in stark contrast to all trace-based equivalences, which are traditionally used for addressing liveness but require exponential time for checking.
AU - Thomas Henzinger
AU - Rajamani, Sriram K
ID - 4433
TI - Fair bisimulation
VL - 1785
ER -
TY - CONF
AB - The algorithmic approach to the analysis of timed and hybrid systems is fundamentally limited by undecidability, of universality in the timed case (where all continuous variables are clocks), and of emptiness in the rectangular case (which includes drifting clocks). Traditional proofs of undecidability encode a single Turing computation by a single timed trajectory. These proofs have nurtured the hope that the introduction of “fuzziness” into timed and hybrid models (in the sense that a system cannot distinguish between trajectories that are sufficiently similar) may lead to decidability. We show that this is not the case, by sharpening both fundamental undecidability results. Besides the obvious blow our results deal to the algorithmic method, they also prove that the standard model of timed and hybrid systems, while not “robust” in its definition of trajectory acceptance (which is affected by tiny perturbations in the timing of events), is quite robust in its mathematical properties: the undecidability barriers are not affected by reasonable perturbations of the model.
AU - Thomas Henzinger
AU - Raskin, Jean-François
ID - 4434
TI - Robust undecidability of timed and hybrid systems
VL - 1790
ER -
TY - CONF
AB - An important case of hybrid systems are the rectangular automata. First, rectangular dynamics can naturally and arbitrarily closely approximate more general, nonlinear dynamics. Second, rectangular automata are the most general type of hybrid systems for which model checking -in particular, Ltl model checking- is decidable. However, on one hand, the original proofs of decidability did not suggest practical algorithms and, on the other hand, practical symbolic model-checking procedures -such as those implemented in HyTech- were not known to terminate on rectangular automata. We remedy this unsatisfactory situation: we present a symbolic method for Ltl model checking which can be performed by HyTech and is guaranteed to terminate on all rectangular automata. We do so by proving that our method for symbolic Ltl model checking terminates on an infinite-state transition system if the trace-equivalence relation of the system has finite index, which is the case for all rectangular automata.
AU - Thomas Henzinger
AU - Majumdar, Ritankar S
ID - 4435
TI - Symbolic model checking for rectangular hybrid systems
VL - 1785
ER -
TY - CONF
AB - We define five increasingly comprehensive classes of infinite-state systems, called STS1–5, whose state spaces have finitary structure. For four of these classes, we provide examples from hybrid systems.
STS1 These are the systems with finite bisimilarity quotients. They can be analyzed symbolically by (1) iterating the predecessor and boolean operations starting from a finite set of observable state sets, and (2) terminating when no new state sets are generated. This enables model checking of the μ-calculus.
STS2 These are the systems with finite similarity quotients. They can be analyzed symbolically by iterating the predecessor and positive boolean operations. This enables model checking of the existential and universal fragments of the μ-calculus.
STS3 These are the systems with finite trace-equivalence quotients. They can be analyzed symbolically by iterating the predecessor operation and a restricted form of positive boolean operations (intersection is restricted to intersection with observables). This enables model checking of linear temporal logic.
STS4 These are the systems with finite distance-equivalence quotients (two states are equivalent if for every distance d, the same observables can be reached in d transitions). The systems in this class can be analyzed symbolically by iterating the predecessor operation and terminating when no new state sets are generated. This enables model checking of the existential conjunction-free and universal disjunction-free fragments of the μ-calculus.
STS5 These are the systems with finite bounded-reachability quotients (two states are equivalent if for every distance d, the same observables can be reached in d or fewer transitions). The systems in this class can be analyzed symbolically by iterating the predecessor operation and terminating when no new states are encountered. This enables model checking of reachability properties.
AU - Thomas Henzinger
AU - Majumdar, Ritankar S
ID - 4439
TI - A classification of symbolic transition systems
VL - 1770
ER -
TY - CONF
AB - Since hybrid embedded systems are pervasive and often safety-critical, guarantees about their correct performance are desirable. The hybrid systems model checker HyTech provides such guarantees and has successfully verified some systems. However, HyTech severely restricts the continuous dynamics of the system being analyzed and, therefore, often forces the use of prohibitively expensive discrete and polyhedral abstractions. We have designed a new algorithm, which is capable of directly verifying hybrid systems with general continuous dynamics, such as linear and nonlinear differential equations. The new algorithm conservatively overapproximates the reachable states of a hybrid automaton by using interval numerical methods. Interval numerical methods return sets of points that enclose the true result of numerical computation and, thus, avoid distortions due to the accumulation of round-off errors. We have implemented the new algorithm in a successor tool to HyTech called HyperTech. We consider three examples: a thermostat with delay, a two-tank water system, and an air-traffic collision avoidance protocol. HyperTech enables the direct, fully automatic analysis of these systems, which is also more accurate than the use of polyhedral abstractions.
AU - Thomas Henzinger
AU - Horowitz, Benjamin
AU - Majumdar, Ritankar S
AU - Wong-Toi, Howard
ID - 4481
TI - Beyond HyTech: Hybrid systems analysis using interval numerical methods
VL - 1790
ER -
TY - CONF
AB - We apply the theory of abstract interpretation to the verification of game properties for reactive systems. Unlike properties expressed in standard temporal logics, game properties can distinguish adversarial from collaborative relationships between the processes of a concurrent program, or the components of a parallel system. We consider two-player concurrent games –say, component vs. environment– and specify properties of such games –say, the component has a winning strategy to obtain a resource, no matter how the environment behaves– in the alternating-time μ-calculus (Aμ ). A sound abstraction of such a game must at the same time restrict the behaviors of the component and increase the behaviors of the environment: if a less powerful component can win against a more powerful environment, then surely the original component can win against the original environment.
We formalize the concrete semantics of a concurrent game in terms of controllable and uncontrollable predecessor predicates, which suffice for model checking all Aμ properties by applying boolean operations and iteration. We then define the abstract semantics of a concurrent game in terms of abstractions for the controllable and uncontrollable predecessor predicates. This allows us to give general characterizations for the soundness and completeness of abstract games with respect to Aμ properties. We also present a simple programming language for multi-process programs, and show how approximations of the maximal abstraction (w.r.t. Aμ properties) can be obtained from the program text. We apply the theory to two practical verification examples, a communication protocol developed at the Berkeley Wireless Research Center, and a protocol converter. In the wireless protocol, both the use of a game property for specification and the use of abstraction for automatic verification were instrumental to uncover a subtle bug.
AU - Thomas Henzinger
AU - Majumdar, Ritankar S
AU - Mang, Freddy Y
AU - Raskin, Jean-François
ID - 4482
TI - Abstract interpretation of game properties
VL - 1824
ER -
TY - CONF
AB - Model-checking algorithms can be used to verify, formally and automatically, if a low-level description of a design conforms with a high-level description. However, for designs with very large state spaces, prior to the application of an algorithm, the refinement-checking task needs to be decomposed into subtasks of manageable complexity. It is natural to decompose the task following the component structure of the design. However, an individual component often does not satisfy its requirements unless the component is put into the right context, which constrains the inputs to the component. Thus, in order to verify each component individually, we need to make assumptions about its inputs, which are provided by the other components of the design. This reasoning is circular: component A is verified under the assumption that context B behaves correctly, and symmetrically, B is verified assuming the correctness of A. The assume-guarantee paradigm provides a systematic theory and methodology for ensuring the soundness of the circular style of postulating and discharging assumptions in component-based reasoning.We give a tutorial introduction to the assume-guarantee paradigm for decomposing refinement-checking tasks. To illustrate the method, we step in detail through the formal verification of a processor pipeline against an instruction set architecture. In this example, the verification of a three-stage pipeline is broken up into three subtasks, one for each stage of the pipeline.
AU - Thomas Henzinger
AU - Qadeer,Shaz
AU - Rajamani, Sriram K
ID - 4483
TI - Decomposing refinement proofs using assume-guarantee reasoning
ER -
TY - CONF
AB - Masaccio is a formal model for hybrid dynamical systems which are built from atomic discrete components (difference equations) and atomic continuous components (differential equations) by parallel and serial composition, arbitrarily nested. Each system component consists of an interface, which determines the possible ways of using the component, and a set of executions, which define the possible behaviors of the component in real time.
Version 1.0 (May 2000).
AU - Thomas Henzinger
ID - 4512
TI - Masaccio: A formal model for embedded components
VL - 1872
ER -
TY - CHAP
AU - Thomas Henzinger
ED - Inan, M. Kemal
ED - Kurshan, Robert P.
ID - 4513
T2 - Verification of Digital and Hybrid Systems
TI - The theory of hybrid automata
VL - 170
ER -
TY - JOUR
AB - A hybrid system is a dynamical system with both discrete and continuous state changes. For analysis purposes, it is often useful to abstract a system in a way that preserves the properties being analyzed while hiding the details that are of no interest. We show that interesting classes of hybrid systems can be abstracted to purely discrete systems while preserving all properties that are definable in temporal logic. The classes that permit discrete abstractions fall into two categories. Either the continuous dynamics must be restricted, as is the case for timed and rectangular hybrid systems, or the discrete dynamics must be restricted, as is the case for o-minimal hybrid systems. In this paper, we survey and unify results from both areas.
AU - Alur, Rajeev
AU - Thomas Henzinger
AU - Lafferriere, Gerardo
AU - Pappas, George J.
ID - 4598
IS - 7
JF - Proceedings of the IEEE
TI - Discrete abstractions of hybrid systems
VL - 88
ER -