@article{11765, abstract = {This paper presents insertions-only algorithms for maintaining the exact and/or approximate size of the minimum edge cut and the minimum vertex cut of a graph. The algorithms output the approximate or exact sizekin timeO(1) and a cut of sizekin time linear in its size. For the minimum edge cut problem and for any 0 < ε ≤ 1, the amortized time per insertion isO(1/ε2) for a (2 + ε)-approximation,O((log λ)((log n)/ε)2) for a (1 + ε)-approximation, andO(λ log n) for the exact size, wherenis the number of nodes in the graph and λ is the size of the minimum cut. The (2 + ε)-approximation algorithm and the exact algorithm are deterministic; the (1 + ε)-approximation algorithm is randomized. We also present a static 2-approximation algorithm for the size κ of the minimum vertex cut in a graph, which takes time. This is a factor of κ faster than the best algorithm for computing the exact size, which takes time. We give an insertions-only algorithm for maintaining a (2 + ε)-approximation of the minimum vertex cut with amortized insertion timeO(n/ε).}, author = {Henzinger, Monika H}, issn = {0196-6774}, journal = {Journal of Algorithms}, number = {1}, pages = {194--220}, publisher = {Elsevier}, title = {{A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity}}, doi = {10.1006/jagm.1997.0855}, volume = {24}, year = {1997}, } @article{11767, abstract = {We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph with the source and sink on the same face. For the case where negative edge-lengths are allowed, we give an algorithm requiringO(n4/3 log(nL)) time, whereLis the absolute value of the most negative length. This algorithm can be used to obtain similar bounds for computing a feasible flow in a planar network, for finding a perfect matching in a planar bipartite graph, and for finding a maximum flow in a planar graph when the source and sink are not on the same face. We also give parallel and dynamic versions of these algorithms.}, author = {Henzinger, Monika H and Klein, Philip and Rao, Satish and Subramanian, Sairam}, issn = {0022-0000}, journal = {Journal of Computer and System Sciences}, number = {1}, pages = {3--23}, publisher = {Elsevier}, title = {{Faster shortest-path algorithms for planar graphs}}, doi = {10.1006/jcss.1997.1493}, volume = {55}, year = {1997}, } @inproceedings{11803, abstract = {We present the first fully dynamic algorithm for maintaining a minimum spanning tree in time o(√n) per operation. To be precise, the algorithm uses O(n 1/3 log n) amortized time per update operation. The algorithm is fairly simple and deterministic. An immediate consequence is the first fully dynamic deterministic algorithm for maintaining connectivity and, bipartiteness in amortized time O(n 1/3 log n) per update, with O(1) worst case time per query.}, author = {Henzinger, Monika H and King, Valerie}, booktitle = {24th International Colloquium on Automata, Languages and Programming}, isbn = {9783540631651}, issn = {1611-3349}, location = {Bologna, Italy}, pages = {594–604}, publisher = {Springer Nature}, title = {{Maintaining minimum spanning trees in dynamic graphs}}, doi = {10.1007/3-540-63165-8_214}, volume = {1256}, year = {1997}, } @article{11849, abstract = {This paper describes the DIGlTAL Continuous Profiling Infrastmcture, a sampling-based profiling system designed to run continuously on production systems. The system supports multiprocessors, works on unmodified executable& and collects profiles for entire systems, including user programs, shared libraries, and the operating system kernel. Samples are collected at a high rate (over 5200 samples/secper333-MHz processor), yet with low overhead (l-3% slowdown for most workloads). Analysis tools supplied with the profiling system use the sample data to produce an accurate accounting, down to the level of pipeline stalls incurred by individual instructions, of where time is being spent. When instructions incur stalls, the tools identify possible reasons, such as cache misses, branch mispredictions, and functional unit contention. The fine-grained instruction-level analysis guides users and automated optimizers to the causes of performance problems and provides important insights for fixing them. }, author = {Anderson, Jennifer M. and Berc, Lance M. and Dean, Jeffrey and Ghemawat, Sanjay and Henzinger, Monika H and Leung, Shun-Tak A. and Sites, Richard L. and Vandevoorde, Mark T. and Waldspurger, Carl A. and Weihl, William E.}, issn = {0163-5980}, journal = {ACM SIGOPS Operating Systems Review}, number = {5}, pages = {1--14}, publisher = {Association for Computing Machinery}, title = {{Continuous profiling: Where have all the cycles gone?}}, doi = {10.1145/269005.266637}, volume = {31}, year = {1997}, } @article{11883, abstract = {In dynamic graph algorithms the following provide-or-bound problem has to be solved quickly: Given a set S containing a subset R and a way of generating random elements from S testing for membership in R, either (i) provide an element of R, or (ii) give a (small) upper bound on the size of R that holds with high probability. We give an optimal algorithm for this problem. This algorithm improves the time per operation for various dynamic graph algorithms by a factor of O(log n). For example, it improves the time per update for fully dynamic connectivity from O(log3n) to O(log2n).}, author = {Henzinger, Monika H and Thorup, Mikkel}, issn = {1098-2418}, journal = {Random Structures and Algorithms}, number = {4}, pages = {369--379}, publisher = {Wiley}, title = {{Sampling to provide or to bound: With applications to fully dynamic graph algorithms}}, doi = {10.1002/(sici)1098-2418(199712)11:4<369::aid-rsa5>3.0.co;2-x}, volume = {11}, year = {1997}, } @inproceedings{1942, author = {Leonid Sazanov and Burrows, P and Nixon, P J}, pages = {705 -- 708}, publisher = {Kluwer}, title = {{Presence of a large protein complex containing the ndhK gene product and possessing NADH-specific dehydrogenase activity in thylakoid membranes of higher plant chloroplasts}}, volume = {2}, year = {1996}, } @article{1951, author = {Sazanov, Leonid A and Burrows, Paul and Nixon, Peter}, issn = {0300-5127}, journal = {Biochemical Society Transactions}, number = {3}, pages = {739 -- 743}, publisher = {Portland Press}, title = {{Detection and characterization of a complex I-like NADH-specific dehydrogenase from pea thylakoids}}, doi = {10.1042/bst0240739}, volume = {24}, year = {1996}, } @article{1952, abstract = {Two strains of Rhodospirillum rubrum were constructed in which, by a gene dosage effect, the transhydrogenase activity of isolated chromatophores was increased 7-10-fold and 15-20-fold, respectively. The H+/H- ratio (the ratio of protons translocated per hydride ion equivalent transferred from NADPH to an NAD+ analogue, acetyl pyridine adenine dinucleotide), determined by a spectroscopic technique, was approximately 1.0 for chromatophores from the over-expressing strains, but was only approximately 0.6 for wild-type chromatophores. Highly-coupled proteoliposomes were prepared containing purified transhydrogenase from beef-heart mitochondria. Using the same technique, the H+/H- ratio was close to 1.0 for these proteoliposomes. It is suggested that the mechanistic H+/H- ratio is indeed unity, but that a low ratio is obtained in wild-type chromatophores because of inhomogeneity in the vesicle population.}, author = {Bizouarn, Tania and Sazanov, Leonid A and Aubourg, Sébastien and Jackson, Julie}, issn = {0005-2728}, journal = {Biochimica et Biophysica Acta - Bioenergetics}, number = {1}, pages = {4 -- 12}, publisher = {Elsevier}, title = {{Estimation of the H+/H- ratio of the reaction catalysed by the nicotinamide nucleotide transhydrogenase in chromatophores from over-expressing strains of Rhodospirillum rubrum and in liposomes inlaid with the purified bovine enzyme}}, doi = {10.1016/0005-2728(95)00125-5}, volume = {1273}, year = {1996}, } @article{6161, abstract = {The tra-1 gene is a terminal regulator of somatic sex in Caenorhabditis elegans: high tra-1 activity elicits female development, low tra-1 activity elicits male development. To investigate the function and evolution of tra- 1, we examined the tra-1 gene from the closely related nematode C. briggsae. Ce-tra-1 and Cb-tra-1 are unusually divergent. Each gene generates two transcripts, but only one of these is present in both species. This common transcript encodes TRA-1A, which shows only 44% amino acid identity between the species, a figure much lower than that for previously compared genes. A Cb-tra-1 transgene rescues many tissues of tra-1(null) mutants of C. elegans but not the somatic gonad or germ line. This transgene also causes nongonadal feminization of XO animals, indicating incorrect sexual regulation. Alignment of Ce-TRA-1A and Cb-TRA-1A defined several conserved regions likely to be important for tra-1 function. The phenotype differences between Ce-tra- 1(null) mutants rescued by Cb-tra-1 transgenes and wild-type C. elegans indicate significant divergence of regulatory regions. These molecular and functional studies suggest that evolution of sex determination in nematodes is rapid and genetically complex.}, author = {de Bono, Mario and Hodgkin, J.}, issn = {00166731}, journal = {Genetics}, keywords = {amino acid sequence, article, caenorhabditis elegans, evolution, genetic variability, nonhuman, priority journal, sex determination, Amino Acid Sequence, Animals, Animals, Genetically Modified, Base Sequence, Caenorhabditis, Caenorhabditis elegans, Caenorhabditis elegans Proteins, DNA, Helminth, DNA-Binding Proteins, Evolution, Molecular, Female, Helminth Proteins, Membrane Proteins, Molecular Sequence Data, Mutagenesis, RNA, Messenger, Sequence Homology, Amino Acid, Sex Determination (Analysis), Transcription Factors, Transgenes, Turner Syndrome, Animalia, Caenorhabditis, Caenorhabditis briggsae, Caenorhabditis elegans, Nematoda}, number = {2}, pages = {587--595}, publisher = {Genetics Society of America}, title = {{Evolution of sex determination in Caenorhabditis: Unusually high divergence of tra-1 and its functional consequences}}, volume = {144}, year = {1996}, } @article{3462, author = {Melcher, Thorsten and Geiger, Jörg and Jonas, Peter M and Monyer, Hannah}, issn = {0197-0186}, journal = {Neurochemistry International}, number = {2}, pages = {141 -- 144}, publisher = {Elsevier}, title = {{Analysis of molecular determinants in native AMPA receptors}}, doi = {10.1016/0197-0186(95)00077-1}, volume = {28}, year = {1996}, } @inproceedings{3553, abstract = {Virtual environments open up new opportunities and challenges for geometric modeling systems. A general approach to geometric modeling suitable for the Cave Automatic Virtual Environment is described. The approach is based on alpha complexes, and some of its capabilities are demonstrated by applying it to the study of biomolecules.}, author = {Edelsbrunner, Herbert and Fu, Ping and Quian, Jiang}, booktitle = {Proceedings of the ACM Symposium on Virtual Reality Software and Technology}, isbn = {9780897918251}, location = {Hong Kong}, pages = {35--41 and -- 193--194}, publisher = {ACM}, title = {{Geometric modeling in CAVE}}, doi = {10.1145/3304181.3304190}, year = {1996}, } @article{3634, abstract = {The evolutionary processes responsible for adaptation and speciation on islands differ in several ways from those on the mainland. Most attention has been given to the random genetic drift that arises when a population is founded from just a few colonizing genomes. Theoretical obstacles to 'founder effect speciation' are discussed, together with recent proposals for avoiding them. It is argued that although certain kinds of epistasis can facilitate the evolution of strong reproductive isolation, this favours divergence by selection as much as by random drift.}, author = {Barton, Nicholas H and Mallet, James}, issn = {0962-8436}, journal = {Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences}, number = {1341}, pages = {785 -- 795}, publisher = {Royal Society of London}, title = {{Natural selection and random genetic drift as causes of evolution on islands}}, doi = {10.1098/rstb.1996.0073}, volume = {351}, year = {1996}, } @article{3635, abstract = {Experiments on Drosophila suggest that genetic recombination may result in lowered fitness of progeny (a 'recombination load'). This has been interpreted as evidence either for a direct effect of recombination on fitness, or for the maintenance of linkage disequilibria by epistatic selection. Here we show that such a recombination load is to be expected even if selection favours increased genetic recombination. This is because of the fact that, although a modifier may suffer an immediate loss of fitness if it increases recombination, it eventually becomes associated with a higher additive genetic variance in fitness, which allows a faster response to direction selection. This argument applies to mutation-selection balance with synergistic epistasis, directional selection on quantitative traits, and ectopic exchange among transposable elements. Further experiments are needed to determine whether the selection against recombination due to the immediate load is outweighed by the increased additive variance in fitness produced by recombination.}, author = {Charlesworth, Brian and Barton, Nicholas H}, issn = {0016-6723}, journal = {Genetical Research}, number = {1}, pages = {27 -- 41}, publisher = {Cambridge University Press}, title = {{Recombination load associated with selection for increased recombination}}, doi = {10.1017/S0016672300033450}, volume = {67}, year = {1996}, } @article{3756, abstract = {In many eukaryotic cells going through M-phase, a bipolar spindle is formed by microtubules nucleated from centrosomes. These microtubules, in addition to being `'captured” by kinetochores, may be stabilized by chromatin in two different ways: short-range stabilization effects may affect microtubules in close contact with the chromatin, while long-range stabilization effects may `'guide” microtubule growth towards the chromatin (e.g., by introducing a diffusive gradient of an enzymatic activity that affects microtubule assembly). Here, we use both meiotic and mitotic extracts from Xenopus laevis eggs to study microtubule aster formation and microtubule dynamics in the presence of chromatin. In `'low-speed” meiotic extracts, in the presence of salmon sperm chromatin, we find that short-range stabilization effects lead to a strong anisotropy of the microtubule asters. Analysis of the dynamic parameters of microtubule growth shows that this anisotropy arises from a decrease in the catastrophe frequency, an increase in the rescue frequency and a decrease in the growth velocity. In this system we also find evidence for long-range `'guidance” effects, which lead to a weak anisotropy of the asters. Statistically relevant results on these long-range effects are obtained in `'high-speed” mitotic extracts in the presence of artificially constructed chromatin stripes. We find that aster anisotropy is biased in the direction of the chromatin and that the catastrophe frequency is reduced in its vicinity. In this system we also find a surprising dependence of the catastrophe and the rescue frequencies on the length of microtubules nucleated from centrosomes: the catastrophe frequency increases and the rescue frequency decreases with microtubule length.}, author = {Dogterom, Marileen and Felix, M. and Guet, Calin C and Leibler, Stanislas}, issn = {0021-9525}, journal = {Journal of Cell Biology}, number = {1}, pages = {125 -- 140}, publisher = {Rockefeller University Press}, title = {{Influence of M-phase chromatin on the anisotropy of microtubule asters}}, doi = {doi: 10.1083/jcb.133.1.125 }, volume = {133}, year = {1996}, } @article{4024, abstract = {We have developed general modeling software for a Cave Automatic Virtual Environment (CAVE); one of its applications is modeling 3D protein structures, generating both outside-in and inside-out views of geometric models. An advantage of the CAVE over other virtual environments is that multiple viewers can observe the same scene at the same time and place. Our software is scalable-from high-end virtual environments such as the CAVE, to mid-range immersive desktop systems, down to low-end graphics workstations. In the current configuration, a parallel Silicon Graphics Power Challenge supercomputer architecture performs the computationally intensive construction of surface patches remotely, and sends the results through the I-WAY (Information Wide Area Year) using VBNS (Very-high-Bandwidth Network Systems) to the graphics machines that drive the CAVE and our graphics visualization software, Valvis (Virtual ALpha shapes VISualizer).}, author = {Akkiraju, Nataraj and Edelsbrunner, Herbert and Fu, Ping and Qian, Jiang}, issn = {0018-9162}, journal = {IEEE Computer Graphics and Applications}, number = {4}, pages = {58 -- 61}, publisher = {IEEE}, title = {{Viewing geometric protein structures from inside a CAVE}}, doi = {10.1109/38.511855}, volume = {16}, year = {1996}, } @article{4025, abstract = {Questions of chemical reactivity can often be cast as questions of molecular geometry. Common geometric models for proteins and other molecules are the space-filling diagram, the solvent accessible surface and the molecular surface. In this paper we present a new approach to triangulating the surface of a molecule under the three models, which is fast, robust, and results in topologically correct triangulations. Our computations are based on a simplicial complex dual to the molecule models. All proposed algorithms are parallelizable.}, author = {Akkiraju, Nataraj and Edelsbrunner, Herbert}, issn = {0166-218X}, journal = {Discrete Applied Mathematics}, number = {1-3}, pages = {5 -- 22}, publisher = {Elsevier}, title = {{Triangulating the surface of a molecule}}, doi = {10.1016/S0166-218X(96)00054-6}, volume = {71}, year = {1996}, } @article{4026, abstract = {A set of n weighted points in general position in R(d) defines a unique regular triangulation. This paper proves that if the points are added one by one, then flipping in a topological order will succeed in constructing this triangulation. If, in addition, the points are added in a random sequence and the history of the flips is used for locating the next point, then the algorithm takes expected time at most O(n log n + n(inverted left perpendicular d/2 inverted right perpendicular)). Under the assumption that the points and weights are independently and identically distributed, the expected running time is between proportional to and a factor log n more than the expected size of the regular triangulation. The expectation is over choosing the points and over independent coin-flips performed by the algorithm.}, author = {Edelsbrunner, Herbert and Shah, Nimish}, issn = {0178-4617}, journal = {Algorithmica}, number = {3}, pages = {223 -- 241}, publisher = {Springer}, title = {{Incremental topological flipping works for regular triangulations}}, doi = {10.1007/BF01975867}, volume = {15}, year = {1996}, } @article{4027, abstract = {Questions about lines in space arise frequently as subproblems in three-dimensional computational geometry. In this paper we study a number of fundamental combinatorial and algorithmic problems involving arrangements of n lines in three-dimensional space. Our main results include: 1. A tight Θ(n2) bound on the maximum combinatorial description complexity of the set of all oriented lines that have specified orientations relative to the n given lines. 2. A similar bound of Θ(n3) for the complexity of the set of all lines passing above the n given lines. 3. A preprocessing procedure using O(n2+ε) time and storage, for any ε > 0, that builds a structure supporting O(logn)-time queries for testing if a line lies above all the given lines. 4. An algorithm that tests the "towering property" in O(n4/3+ε) time, for any ε > 0: do n given red lines lie all above n given blue lines? The tools used to obtain these and other results include Plücker coordinates for lines in space and ε-nets for various geometric range spaces.}, author = {Chazelle, Bernard and Edelsbrunner, Herbert and Guibas, Leonidas and Sharir, Micha and Stolfi, Jorge}, issn = {0178-4617}, journal = {Algorithmica}, number = {5}, pages = {428 -- 447}, publisher = {Springer}, title = {{Lines in space: Combinatorics and algorithms}}, doi = {10.1007/BF01955043}, volume = {15}, year = {1996}, } @misc{4030, author = {Liang, Jie and Edelsbrunner, Herbert and Subramaniam, Shankar}, booktitle = {Fortieth Annual Meeting}, number = {2, Part 2}, pages = {A224 -- A224}, publisher = {Cell Press}, title = {{Effects of molecular shape representations on boundary element method for protein electrostatics computations}}, doi = {10.1016/S0006-3495(96)79664-9}, volume = {70}, year = {1996}, } @misc{4031, author = {Liang, Jie and Edelsbrunner, Herbert and Pamidghantam, Sudhakar and Subramaniam, Shankar}, booktitle = {Fortieth Annual Meeting}, number = {2, Part 2}, pages = {A377 -- A377}, publisher = {Cell Press}, title = {{Analytical method for molecular shapes: Area, volume, cavities, interface and pockets}}, doi = {10.1016/S0006-3495(96)79670-4}, volume = {70}, year = {1996}, }