@article{3651, abstract = {It is widely held that each gene typically affects many characters, and that each character is affected by many genes. Moreover, strong stabilizing selection cannot act on an indefinitely large number of independent traits. This makes it likely that heritable variation in any one trait is maintained as a side effect of polymorphisms which have nothing to do with selection on that trait. This paper examines the idea that variation is maintained as the pleiotropic side effect of either deleterious mutation, or balancing selection. If mutation is responsible, it must produce alleles which are only mildly deleterious (s & 10(-3)), but nevertheless have significant effects on the trait. Balancing selection can readily maintain high heritabilities; however, selection must be spread over many weakly selected polymorphisms if large responses to artificial selection are to be possible. In both classes of pleiotropic model, extreme phenotypes are less fit, giving the appearance of stabilizing selection on the trait. However, it is shown that this effect is weak (of the same order as the selection on each gene): the strong stabilizing selection which is often observed is likely to be caused by correlations with a limited number of directly selected traits. Possible experiments for distinguishing the alternatives are discussed.}, author = {Barton, Nicholas H}, issn = {0016-6731}, journal = {Genetics}, number = {3}, pages = {773 -- 782}, publisher = {Genetics Society of America}, title = {{Pleiotropic models of quantitative variation}}, doi = {10.1093/genetics/124.3.773 }, volume = {124}, year = {1990}, } @article{4060, abstract = {This paper offers combinatorial results on extremum problems concerning the number of tetrahedra in a tetrahedrization of n points in general position in three dimensions, i.e. such that no four points are co-planar, It also presents an algorithm that in O(n log n) time constructs a tetrahedrization of a set of n points consisting of at most 3n-11 tetrahedra.}, author = {Edelsbrunner, Herbert and Preparata, Franco and West, Douglas}, issn = {1095-855X}, journal = {Journal of Symbolic Computation}, number = {3-4}, pages = {335 -- 347}, publisher = {Elsevier}, title = {{Tetrahedrizing point sets in three dimensions}}, doi = {10.1016/S0747-7171(08)80068-5}, volume = {10}, year = {1990}, } @article{2525, abstract = {This paper describes the amino acid sequence of the rat substance P receptor and its comparison with that of the rat substance K receptor on the basis of molecular cloning and sequence analysis. From a rat brain cDNA library constructed with an RNA expression vector, we identified a cDNA mixture containing a functional substance P receptor cDNA by examining electrophysiologically a receptor expression following injection of the mRNAs synthesized in vitro into Xenopus oocytes. A receptor cDNA clone was then isolated by cross-hybridization with the bovine substance K receptor DNA. The clone was confirmed by selective binding of substance P to the cloned receptor expressed in mammalian COS cells. The deduced amino acid sequence (407 amino acid residues) possesses seven putative membrane spanning domains and shows a sequence similarity to the members of G-protein-coupled receptors. The rat substance P and substance K receptor are very similar in both size and amino acid sequences, particularly in the putative transmembrane similarity is in marked contrast to the sequence divergence in the amino- and carboxyl-terminal regions and the third cytoplasmic loop. The observed sequence similarytity and divergence would thus contribute to the expression of similar but pharmacological regions and the first and second cytoplasmic loops. This distinguishable activities of the two tachykinin receptors.}, author = {Yokota, Yoshifumi and Sasai, Yoshiki and Tanaka, Kohichi and Fujiwara, Tsutomu and Tsuchida, Kunihiro and Shigemoto, Ryuichi and Kakizuka, Akira and Ohkubo, Hiroaki and Nakanishi, Shigetada}, issn = {1083-351X}, journal = {Journal of Biological Chemistry}, number = {30}, pages = {17649 -- 17652}, publisher = {American Society for Biochemistry and Molecular Biology}, title = {{Molecular characterization of a functional cDNA for rat substance P receptor}}, doi = {doi.org/10.1016/S0021-9258(19)84619-7}, volume = {264}, year = {1989}, } @article{3466, abstract = {Amphibian myelinated nerve fibers were treated with collagenase and protease. Axons with retraction of the myelin sheath were patch-clamped in the nodal and paranodal region. One type of Na channel was found. It has a single-channel conductance of 11 pS (15 degrees C) and is blocked by tetrodotoxin. Averaged events show the typical activation and inactivation kinetics of macroscopic Na current. Three potential-dependent K channels were identified (I, F, and S channel). The I channel, being the most frequent type, has a single-channel conductance of 23 pS (inward current, 105 mM K on both sides of the membrane), activates between -60 and -30 mV, deactivates with intermediate kinetics, and is sensitive to dendrotoxin. The F channel has a conductance of 30 pS, activates between -40 and 60 mV, and deactivates with fast kinetics. The former inactivates within tens of seconds; the latter inactivates within seconds. The third type, the S channel, has a conductance of 7 pS and deactivates slowly. All three channels can be blocked by external tetraethylammonium chloride. We suggest that these distinct K channel types form the basis for the different components of macroscopic K current described previously.}, author = {Jonas, Peter M and Bräu, Michael and Hermsteiner, Markus and Vogel, Werner}, issn = {1091-6490}, journal = {PNAS}, number = {18}, pages = {7238 -- 7242}, publisher = {National Academy of Sciences}, title = {{Single-channel recording in myelinated nerve fibers reveals one type of Na channel but different K channels}}, doi = {10.1073/pnas.86.18.7238}, volume = {86}, year = {1989}, } @article{3652, abstract = {Frequency-dependent selection against rare forms can maintain clines. For weak selection, s, in simple linear models of frequency-dependence, single locus clines are stabilized with a maximum slope of between square root of s/square root of 8 sigma and square root of s/square root of 12 delta, where sigma is the dispersal distance. These clines are similar to those maintained by heterozygote disadvantage. Using computer simulations, the weak-selection analytical results are extended to higher selection pressures with up to three unlinked genes. Graphs are used to display the effect of selection, migration, dominance, and number of loci on cline widths, speeds of cline movements, two-way gametic correlations ("linkage disequilibria"), and heterozygote deficits. The effects of changing the order of reproduction, migration, and selection, are also briefly explored. Epistasis can also maintain tension zones. We show that epistatic selection is similar in its effects to frequency-dependent selection, except that the disequilibria produced in the zone will be higher for a given level of selection. If selection consists of a mixture of frequency-dependence and epistasis, as is likely in nature, the error made in estimating selection is usually less than twofold. From the graphs, selection and migration can be estimated using knowledge of the dominance and number of genes, of gene frequencies and of gametic correlations from a hybrid zone.}, author = {Mallet, James and Barton, Nicholas H}, issn = {0016-6731}, journal = {Genetics}, number = {4}, pages = {967 -- 976}, publisher = {Genetics Society of America}, title = {{Inference from clines stabilized by frequency-dependent selection}}, doi = {10.1093/genetics/122.4.967}, volume = {122}, year = {1989}, } @article{4081, abstract = {This paper studies applications of envelopes of piecewise linear functions to problems in computational geometry. Among these applications we find problems involving hidden line/surface elimination, motion planning, transversals of polytopes, and a new type of Voronoi diagram for clusters of points. All results are either combinatorial or computational in nature. They are based on the combinatorial analysis in two companion papers [PS] and [E2] and a divide-and-conquer algorithm for computing envelopes described in this paper.}, author = {Edelsbrunner, Herbert and Guibas, Leonidas and Sharir, Micha}, issn = {1432-0444}, journal = {Discrete & Computational Geometry}, number = {1}, pages = {311 -- 336}, publisher = {Springer}, title = {{The upper envelope of piecewise linear functions: Algorithms and applications}}, doi = {10.1007/BF02187733}, volume = {4}, year = {1989}, } @article{4082, abstract = {Sweeping a collection of figures in the Euclidean plane with a straight line is one of the novel algorithmic paradigms that have emerged in the field of computational geometry. In this paper we demonstrate the advantages of sweeping with a topological line that is not necessarily straight. We show how an arrangement of n lines in the plane can be swept over in O(n2) time and O(n) space by a such a line. In the process each element, i.e., vertex, edge, or region, is visited once in a consistent ordering. Our technique makes use of novel data structures which exhibit interesting amortized complexity behavior; the result is an algorithm that improves upon all its predecessors either in the space or the time bounds, as well as being eminently practical. Numerous applications of the technique to problems in computational geometry are given—many through the use of duality transforms. Examples include solving visibility problems, detecting degeneracies in configurations, computing the extremal shadows of convex polytopes, and others. Even though our basic technique solves a planar problem, its applications include several problems in higher dimensions.}, author = {Edelsbrunner, Herbert and Guibas, Leonidas}, issn = {1090-2724}, journal = {Journal of Computer and System Sciences}, number = {1}, pages = {165 -- 194}, publisher = {Elsevier}, title = {{Topologically sweeping an arrangement}}, doi = {10.1016/0022-0000(89)90038-X}, volume = {38}, year = {1989}, } @article{4083, abstract = {It is shown that, given a set S of n points in $R^3 $, one can always find three planes that form an eight-partition of S, that is, a partition where at most ${n / 8}$ points of S lie in each of the eight open regions. This theorem is used to define a data structure, called an octant tree, for representing any point set in $R^3 $. An octant tree for n points occupies $O(n)$ space and can be constructed in polynomial time. With this data structure and its refinements, efficient solutions to various range query problems in two and three dimensions can be obtained, including (1) half-space queries: find all points of S that lie to one side of any given plane; (2) polyhedron queries: find all points that lie inside (outside) any given polyhedron; and (3) circle queries in $R^2 $: for a planar set S, find all points that lie inside (outside) any given circle. The retrieval time for all these queries is $T(n) = O(n^\alpha + m)$, where $\alpha = 0.8988$ (or 0.8471 in case (3)), and m is the size of the output. This performance is the best currently known for linear-space data structures that can be deterministically constructed in polynomial time.}, author = {Yao, F. and Dobkin, David and Edelsbrunner, Herbert and Paterson, Michael}, issn = {1095-7111}, journal = {SIAM Journal on Computing}, number = {2}, pages = {371 -- 384}, publisher = {SIAM}, title = {{Partitioning space for range queries}}, doi = {10.1137/0218025}, volume = {18}, year = {1989}, } @article{4084, abstract = {A tour of a finite set P of points is a necklace-tour if there are disks with the points in P as centers such that two disks intersect if and only if their centers are adjacent in . It has been observed by Sanders that a necklace-tour is an optimal traveling salesman tour. In this paper, we present an algorithm that either reports that no necklace-tour exists or outputs a necklace-tour of a given set of n points in O(n2 log n) time. If a tour is given, then we can test in O(n2) time whether or not this tour is a necklace-tour. Both algorithms can be generalized to ƒ-factors of point sets in the plane. The complexity results rely on a combinatorial analysis of certain intersection graphs of disks defined for finite sets of points in the plane.}, author = {Edelsbrunner, Herbert and Rote, Günter and Welzl, Emo}, issn = {1879-2294}, journal = {Theoretical Computer Science}, number = {2}, pages = {157 -- 180}, publisher = {Elsevier}, title = {{Testing the necklace condition for shortest tours and optimal factors in the plane}}, doi = {10.1016/0304-3975(89)90133-3}, volume = {66}, year = {1989}, } @article{4086, abstract = {This note proves that the maximum number of faces (of any dimension) of the upper envelope of a set ofn possibly intersectingd-simplices ind+1 dimensions is (n d (n)). This is an extension of a result of Pach and Sharir [PS] who prove the same bound for the number ofd-dimensional faces of the upper envelope.}, author = {Edelsbrunner, Herbert}, issn = {1432-0444}, journal = {Discrete & Computational Geometry}, number = {4}, pages = {337 -- 343}, publisher = {Springer}, title = {{The upper envelope of piecewise linear functions: Tight bounds on the number of faces }}, doi = {10.1007/BF02187734}, volume = {4}, year = {1989}, } @article{4088, abstract = {Anarrangement ofn lines (or line segments) in the plane is the partition of the plane defined by these objects. Such an arrangement consists ofO(n 2) regions, calledfaces. In this paper we study the problem of calculating and storing arrangementsimplicitly, using subquadratic space and preprocessing, so that, given any query pointp, we can calculate efficiently the face containingp. First, we consider the case of lines and show that with (n) space1 and (n 3/2) preprocessing time, we can answer face queries in (n)+O(K) time, whereK is the output size. (The query time is achieved with high probability.) In the process, we solve three interesting subproblems: (1) given a set ofn points, find a straight-edge spanning tree of these points such that any line intersects only a few edges of the tree, (2) given a simple polygonal path , form a data structure from which we can find the convex hull of any subpath of quickly, and (3) given a set of points, organize them so that the convex hull of their subset lying above a query line can be found quickly. Second, using random sampling, we give a tradeoff between increasing space and decreasing query time. Third, we extend our structure to report faces in an arrangement of line segments in (n 1/3)+O(K) time, given(n 4/3) space and (n 5/3) preprocessing time. Lastly, we note that our techniques allow us to computem faces in an arrangement ofn lines in time (m 2/3 n 2/3+n), which is nearly optimal.}, author = {Edelsbrunner, Herbert and Guibas, Leonidas and Hershberger, John and Seidel, Raimund and Sharir, Micha and Snoeyink, Jack and Welzl, Emo}, issn = {1432-0444}, journal = {Discrete & Computational Geometry}, number = {1}, pages = {433 -- 466}, publisher = {Springer}, title = {{Implicitly representing arrangements of lines or segments}}, doi = {10.1007/BF02187742}, volume = {4}, year = {1989}, } @article{4089, abstract = {Motivated by a number of motion-planning questions, we investigate in this paper some general topological and combinatorial properties of the boundary of the union ofn regions bounded by Jordan curves in the plane. We show that, under some fairly weak conditions, a simply connected surface can be constructed that exactly covers this union and whose boundary has combinatorial complexity that is nearly linear, even though the covered region can have quadratic complexity. In the case where our regions are delimited by Jordan acrs in the upper halfplane starting and ending on thex-axis such that any pair of arcs intersect in at most three points, we prove that the total number of subarcs that appear on the boundary of the union is only (n(n)), where(n) is the extremely slowly growing functional inverse of Ackermann's function.}, author = {Edelsbrunner, Herbert and Guibas, Leonidas and Hershberger, John and Pach, János and Pollack, Richard and Seidel, Raimund and Sharir, Micha and Snoeyink, Jack}, issn = {1432-0444}, journal = {Discrete & Computational Geometry}, number = {1}, pages = {523 -- 539}, publisher = {Springer}, title = {{On arrangements of Jordan arcs with three intersections per pair}}, doi = {10.1007/BF02187745}, volume = {4}, year = {1989}, } @article{3655, abstract = {The structural basis and distribution of variation in the ribosomal RNA multigene family ( rDNA) was studied in the X0 and neo-XY races of the Alpine grasshopper Podisma pedestris. Restriction-enzyme sites in the gene region of the rDNA repeat were identical in both races and homogeneous in the rDNA family. In contrast, sites for Hind111 and PvuII in the intergenic spacer (IGS) region showed racial divergence and variation within the rDNA family and within populations. A short insertion in the 28s gene region was present in a minority of repeats in both races. The distributions of four polymorphic IGS Hind111 fragments were surveyed at 43 locations in and around the hybrid zone. Two of these fragments appear to be distributed as clines, one of which is strongly associated with the neo-X chromosome. The other two fragments show considerable variation in both races and show negative association. It is proposed that the clinally distributed variants arise from processes of amplification and divergence of IGS sequence variants and that such divergence may contribute to hybrid inviability. }, author = {Dallas, John and Barton, Nicholas H and Dover, Gabriel}, issn = {1537-1719}, journal = {Molecular Biology and Evolution}, number = {6}, pages = {660 -- 674}, publisher = {Oxford University Press}, title = {{Interracial rDNA variation in the grasshopper Podisma Pedestris}}, doi = {10.1093/oxfordjournals.molbev.a040528}, volume = {5}, year = {1988}, } @article{4090, abstract = {In this paper we study the problem of polygonal separation in the plane, i.e., finding a convex polygon with minimum number k of sides separating two given finite point sets (k-separator), if it exists. We show that for k = Θ(n), is a lower bound to the running time of any algorithm for this problem, and exhibit two algorithms of distinctly different flavors. The first relies on an O(n log n)-time preprocessing task, which constructs the convex hull of the internal set and a nested star-shaped polygon determined by the external set; the k-separator is contained in the annulus between the boundaries of these two polygons and is constructed in additional linear time. The second algorithm adapts the prune-and-search approach, and constructs, in each iteration, one side of the separator; its running time is O(kn), but the separator may have one more side than the minimum.}, author = {Edelsbrunner, Herbert and Preparata, Franco}, issn = {0890-5401}, journal = {Information and Computation}, number = {3}, pages = {218 -- 232}, publisher = {Elsevier}, title = {{Minimum polygonal separation}}, doi = {10.1016/0890-5401(88)90049-1}, volume = {77}, year = {1988}, } @article{3658, abstract = {Females of the grasshopper Podisima pedestris were collected from the middle of a hybrid zone between two chromosomal races in the Alpes Maritimes. They had already mated in the field, and could therefore lay fertilised eggs in the laboratory. The embryos were karyotyped, and found to contain an excess of chromosomal homozygotes. No evidence of assortative mating was found from copulating pairs taken in the field. The excess appears to have been caused by a combination of multiple insemination and assortative fertilisation. The genetics of the assortment, and the implications for the evolution of reproductive isolation are discussed.}, author = {Hewitt, Godfrey and Nichols, R. and Barton, Nicholas H}, issn = {1365-2540}, journal = {Heredity}, number = {3}, pages = {457 -- 466}, publisher = {Nature Publishing Group}, title = {{Homogamy in a hybrid zone in the alpine grasshopper Podisma pedestris}}, doi = {10.1038/hdy.1987.156}, volume = {59}, year = {1987}, } @article{4319, abstract = {The grasshopper Podisma pedestris contains two chromosomal races, which differ by a Robertsonian fusion between the sex chromosome and an autosome, and which meet in a narrow hybrid zone in the Alpes Maritimes. DNA content variation across this hybrid zone was investigated by optical densitometry of Feulgen stained spermatids. Spermatids from males with the unfused sex chromosome stain more strongly than those from males with the fused chromosome. The difference between the karyotypes is greater in the centre of the hybrid zone, suggesting that it is not a pleiotropic effect of the fusion itself, but is due instead to differences at closely linked loci.}, author = {Westerman, Michael and Barton, Nicholas H and Hewitt, Godfrey}, issn = {1365-2540}, journal = {Heredity}, pages = {221 -- 228}, publisher = {Nature Publishing Group}, title = {{Differences in DNA content between two chromosomal races of the grasshopper Podisma pedestris}}, doi = {10.1038/hdy.1987.36}, volume = {58}, year = {1987}, } @article{3663, abstract = {The conditional average frequency of rare alleles has been shown in simulations to provide a simple and robust estimator of the number of individuals exchanged between local populations in an island model (Nm). This statistic is defined as the average frequency of an allele in those samples in which the allele is present. Here, we show that the conditional average frequency can be calculated from the distribution of allele frequencies. It is a measure of the spread of this distribution, and so is analogous to the standardised variance, FST. Analytic predictions for the island model of migration agree well with the corresponding simulation results. These predictions are based on the assumption that the rare alleles found in samples have reached a "quasi-equilibrium" distribution. As well as relating the conditional average frequency to the underlying allele frequency distribution, our results provide a more accurate method of estimating Nm from the conditional average frequency of private alleles in samples of different sizes.}, author = {Barton, Nicholas H and Slatkin, Montgomery}, issn = {1365-2540}, journal = {Heredity}, number = {3}, pages = {409 -- 416}, publisher = {Nature Publishing Group}, title = {{A quasi-equilibrium theory of the distribution of rare alleles in a subdivided population}}, doi = {10.1038/hdy.1986.63}, volume = {56}, year = {1986}, } @article{3664, abstract = {Suppose that selection acts at one or more loci to maintain genetic differences between hybridising populations. Then, the flow of alleles at a neutral marker locus which is linked to these selected loci will be impeded. We define and calculate measures of the barrier to gene flow between two distinct demes, and across a continuous habitat. In both cases, we find that in order for gene flow to be significantly reduced over much of the genome, hybrids must be substantially less fit, and the number of genes involved in building the barrier must be so large that the majority of other genes become closely linked to some locus which is under selection. This conclusion is not greatly affected by the pattern of epistasis, or the position of the marker locus along the chromosome.}, author = {Barton, Nicholas H and Bengtsson, Bengt}, issn = {1365-2540}, journal = {Heredity}, pages = {357 -- 376}, publisher = {Nature Publishing Group}, title = {{The barrier to genetic exchange between hybridising populations}}, volume = {57}, year = {1986}, } @article{3665, abstract = {The rate of gene flow across a hybrid zone may be reduced by the presence of a physical barrier, by a reduction of population density caused by reduced fitness of hybrids (the “hybrid sink” effect), and by linkage. If the reduction in hybrid fitness is not extreme, the strength of the barrier to gene flow caused by these effects is. Here, w is the width of the cline; ρ* is the carrying capacity; W̄* is the mean fitness of the population, excluding effects of density; R is the strength of density-dependent regulation; and r̄ is the harmonic mean recombination rate between the locus whose flow is being calculated, and loci under selection. +, 0 denote populations outside the hybrid zone, and at its centre, respectively. This relation is illustrated using data from hybrid ones in Bombina and Podisma, and its implications for interpretation of data from nature are discussed.}, author = {Barton, Nicholas H}, issn = {1365-2540}, journal = {Heredity}, pages = {415 -- 426}, publisher = {Nature Publishing Group}, title = {{The effects of linkage and density-dependent regulation on gene flow}}, volume = {57}, year = {1986}, } @article{4098, abstract = {To points p and q of a finite set S in d-dimensional Euclidean space Ed are extreme if {p, q} = S ∩ h, for some open halfspace h. Let e2(d)(n) be the maximum number of extreme pairs realized by any n points in Ed. We give geometric proofs of , if n⩾4, and e2(3)(n) = 3n−6, if n⩾6. These results settle the question since all other cases are trivial.}, author = {Edelsbrunner, Herbert and Stöckl, Gerd}, issn = {1096-0899}, journal = {Journal of Combinatorial Theory Series A}, number = {2}, pages = {344 -- 349}, publisher = {Elsevier}, title = {{The number of extreme pairs of finite point-sets in Euclidean spaces}}, doi = {10.1016/0097-3165(86)90075-0}, volume = {43}, year = {1986}, }