TY - JOUR AB - We have made an extensive allozyme survey of 21 enzyme and protein loci in populations of the alpine grasshopper Podisma pedestris. This species occurs in two races, differing by a chromosomal fusion which separates the ancestral XO/XX race from a derived neo-XY race. These races also differ in DNA content, and hybrids between them have reduced viability. Electrophoresis reveals that the amount of genetic differentiation between these races is no greater than the variation among populations within each race. Both larger-scale surveys and a detailed survey of an area where the races hybridize, show that the chromosomal change is not correlated with gene frequency changes at any of the 21 loci studied. These findings are consistent with recently developed theory concerning the strength of the barrier to gene flow posed by a hybrid zone with characteristics such as those measured experimentally in Podisma. It is argued that hybrid zones in other species which involve allozymic differences do so because of stronger selection against hybrids rather than through mating isolation. AU - Halliday, Bruce AU - Barton, Nicholas H AU - Hewitt, Godfrey ID - 3666 IS - 1 JF - Biological Journal of the Linnean Society KW - Hybrid zone KW - Electrophoresis KW - Podisma pedestris KW - Polymorphism SN - 0024-4066 TI - Electrophoretic analysis of a chromosomal hybrid zone in the grasshopper Podisma pedestris VL - 19 ER - TY - JOUR AB - When two populations which differ at many loci meet, the degree of introgression of alleles across the boundary will depend on the selection acting on each locus (s), the rate of recombination between adjacent loci (r), and the number of loci involved (n). Simple scaling arguments suggest that the behavior of the system should depend on the ratio of selection to recombination (θ = s/r), and on n. This is borne out by mathematical analysis of two demes which exchange individuals at a low rate; when selection is stronger than recombination (θ > 1), the effective selection on each locus is comparable to the total selection over the whole genome (s* ∼ ns). When selection is weaker than recombination (θ < 1), the effective selection is much weaker, but is still stronger than the selection on each locus alone (s* \sim sn20 for small θ). When n is very large, these two regimes are separated by a sharp threshold at θ = 1. The results are extended to two taxa which meet in a continuous habitat; the effective selection pressure, which determines the width of the hybrid zone, behaves in the same way as for the simpler case above. Even when selection is weak compared to recombination, multilocus clines have a sharp step at their center, flanked by tails of introgression in which the alleles behave independently of each other. The set of clines acts as a barrier to gene flow, and it is shown that the barrier is strongest when selection is spread over many loci. The implications of the results for divergence and speciation are discussed. AU - Barton, Nicholas H ID - 3668 IS - 3 JF - Evolution; International Journal of Organic Evolution SN - 0014-3820 TI - Multilocus clines VL - 37 ER - TY - JOUR AB - Populations of the grasshopper Podisma pedestris were collected from two ends of a zone of hybridization between two chromosome races, at Seyne and Tende in southern France. 21 enzyme and protein loci were detected by gel electrophoresis. Six of these loci showed widespread polymorphism, and a further eleven had very little or no variation. Two loci (Idh, 6Pgd) had rare alleles in different frequencies in the two areas surveyed. The remaining two loci (Mdh-1, Mdh-2) showed a marked increase in the frequency of rare variants, from 1 per cent outside the hybrid zone, up to 5 per cent at its centre. This region of increased electrophoretic variation coincided with the chromosomal cline between the two races, and with a region of decreased viability. It was spread over about the same width as the chromosomal cline. Possible explanations for this extra variation include intragenic recombination and elevated mutation rates. AU - Barton, Nicholas H AU - Halliday, Bruce AU - Hewitt, Godfrey ID - 3667 IS - 2 JF - Heredity SN - 0018-067X TI - Rare electrophoretic variants in a hybrid zone VL - 50 ER - TY - CONF AU - Edelsbrunner, Herbert AU - Welzl, Emo ID - 4124 KW - Voronoi diagram KW - Asymptotic bound KW - Straightforward counting KW - Affine trans KW - Neighbor Voronoi diagram T2 - International Colloquium on Automata, Languages, and Programming TI - On the number of equal-sized semispaces of a set of points in the plane VL - 154 ER - TY - JOUR AB - Let S denote a set of n points in the plane such that each point p has assigned a positive weight w(p) which expresses its capability to influence its neighbourhood. In this sense, the weighted distance of an arbitrary point x from p is given by de(x,p)/w(p) where de denotes the Euclidean distance function. The weighted Voronoi diagram for S is a subdivision of the plane such that each point p in S is associated with a region consisting of all points x in the plane for which p is a weighted nearest point of S. An algorithm which constructs the weighted Voronoi diagram for S in O(n2) time is outlined in this paper. The method is optimal as the diagram can consist of Θ(n2) faces, edges and vertices. AU - Aurenhammer, Franz AU - Edelsbrunner, Herbert ID - 4125 IS - 2 JF - Pattern Recognition SN - 0031-3203 TI - An optimal algorithm for constructing the weighted Voronoi diagram in the plane VL - 17 ER - TY - JOUR AB - A generalization of the convex hull of a finite set of points in the plane is introduced and analyzed. This generalization leads to a family of straight-line graphs, " \alpha -shapes," which seem to capture the intuitive notions of "fine shape" and "crude shape" of point sets. It is shown that a-shapes are subgraphs of the closest point or furthest point Delaunay triangulation. Relying on this result an optimal O(n \log n) algorithm that constructs \alpha -shapes is developed. AU - Edelsbrunner, Herbert AU - Kirkpatrick, David AU - Seidel, Raimund ID - 4128 IS - 4 JF - IEEE Transactions on Information Theory SN - 0018-9162 TI - On the shape of a set of points in the plane VL - 29 ER - TY - JOUR AB - Rectangle intersections involving rectilinearly-oriented (hyper-) rectangles in d-dimensional real space are examined from two points of view. First, a data structure is developed which is efficient in time and space and allows us to report all d-dimensional rectangles stored which intersect a d-dimensional query rectangle. Second, in Part II, a slightly modified version of this new data structure is applied to report all intersecting pairs of rectangles of a given set. This approach yields a solution which is optimal in time and space for planar rectangles and reasonable in higher dimensions. AU - Edelsbrunner, Herbert ID - 4126 IS - 3-4 JF - International Journal of Computer Mathematics SN - 0020-7160 TI - A new approach to rectangle intersections part 1 VL - 13 ER - TY - JOUR AB - The study begun in Part I is completed by providing an algorithm which reports all intersecting pairs of a set of rectangles in d dimensions. This approach yields a solution which is optimal in time and space for planar rectangles and reasonable in higher dimensions. AU - Edelsbrunner, Herbert ID - 4127 IS - 3-4 JF - International Journal of Computer Mathematics SN - 0020-7160 TI - A new approach to rectangle intersections part 2 VL - 13 ER - TY - CHAP AB - Usually in computer graphics, a two-dimensional view of a set of three-dimensional objects is considered. In this article we reduce the dimensionality by one in each case. In other words we study what, for obvious reasons, we call Flatland graphics. This forms the beginning of a mathematical investigation of computer graphics and, at the same time, provides uniform solutions for a number of computational geometry problems. In particular we study the maintenance of a view during insertion and deletion of objects and the "frame-to-frame" coherence while walking around a set of objects. Both parallel and perspective projections are considered. Our major concern is convex objects that are simple—in a sense, made precise in this article. However, we will close this article by discussing some possible extensions to nonconvex objects and/or to higher dimensions. The investigation also serves to demonstrate a number of tools that have been developed recently in the context of computational geometry. For example. dynamization and searching. AU - Edelsbrunner, Herbert AU - Overmars, Mark AU - Wood, Derick ED - Preparata, Franco ID - 3563 SN - 0-89232-356-6 T2 - Computational Geometry: Theory and Applications TI - Graphics in Flatland: a case study VL - 1 ER - TY - CHAP AB - The segment tree is a data structure for storing and maintaining a set of intervals on the real line. It has been used for an efficient algorithmic approach in a variety of geometric problems including the problem of deter-mining intersections among axis-parallel rectangles, computing the measure of a set of axis-parallel rectangles, and locating a point in a planar subdivision. A segment tree for n intervals requires 0(n) space in the best case and 0(n log n) space in the worst case. It is shown that segment trees require 0(n log n) space even in the expected case. Additionally, the worst-case upper bound on the space requirement of segment trees is improved over the previously known bound. Surprisingly, the space requirements in the expected and in the worst case differ only little. AU - Bucher, W. AU - Edelsbrunner, Herbert ED - Preparata, Franco ID - 3562 T2 - Computational Geometry: Theory and Applications TI - On expected- and worst-case segment trees VL - 1 ER - TY - CHAP AU - Edelsbrunner, Herbert ED - Maurer, Hermann ID - 3564 SN - 9783411016587 T2 - Überblicke Informationsverarbeitung TI - Neue Entwicklungen im Bereich Datenstrukturen ER - TY - JOUR AU - Barton, Nicholas H AU - Jones, Steve ID - 3598 JF - Nature SN - 0028-0836 TI - Mitochondrial DNA: new clues about evolution VL - 306 ER - TY - CHAP AB - The hybrid zone which forms when two partially incompatible populations meet acts as a barrier to gene flow. We discuss electrophoretic and theoretical evidence on the strength of such barriers. Hybrid zones generally involve considerable electrophoretic divergence. The enzyme clines are consistent in position and width; in some cases, they show consistently asymmetric patterns of introgression. This consistency suggests that the clines are maintained primarily by the indirect effects of selection at linked loci, rather than by the effect of each individual locus on fitness. A cline at a single locus will present some barrier, regardless of the selective mechanism which maintains it. However, unless the locus induces virtually complete assortment or hybrid unfitness, the barrier will be weak. Spreading the same selection over more clines gives a stronger barrier. If the clines are staggered, this barrier is still unlikely to be significant; if they coincide, and if selection is stronger than recombination, then the barrier will be very strong; its strength and asymmetry will be consistent over different loci. Thus, the taxonomic status of divergent populations cannot be inferred just from the total amount of pre- or post-mating isolation; the number of genetic differences, and the interactions between them are equally important in determining rates of gene flow. AU - Barton, Nicholas H AU - Hewitt, Godfrey ED - Oxford, Geoffrey ED - Rollinson, David ID - 4328 KW - chemotaxonomy SN - 0309-2593 T2 - Protein polymorphism: Adaptive and taxonomic significance TI - Hybrid zones as barriers to gene flow VL - 24 ER - TY - GEN AU - Barton, Nicholas H ID - 4330 SN - 0018-067X T2 - Heredity TI - Gene flow and speciation (abstract) VL - 50 ER - TY - GEN AU - Barton, Nicholas H ID - 4329 IS - 2 SN - 0003-3472 T2 - Animal Behaviour TI - The extended phenotype: the gene as the unit of selection (review of Dawkins R 1982) VL - 31 ER -