@article{3150, abstract = {Tripartite G-protein-coupled receptors (GPCRs) represent one of the largest groups of signal transducers, transmitting signals from hormones, neuropeptides, odorants, food and light. Ligand-bound receptors catalyse GDP/GTP exchange on the G-protein α-subunit (Gα), leading to α-GTP separation from the βγ subunits and pathway activation. Activating mutations in the receptors or G proteins underlie many human diseases, including some cancers, dwarfism and premature puberty. Regulators of G-protein signalling (RGS proteins) are known to modulate the level and duration of ligand-induced signalling by accelerating the intrinsic GTPase activity of the Gα subunit, and thus reformation of the inactive GDP-bound Gα. Here we find that even in the absence of receptor, mutation of the RGS family member Sst2 (refs 6-9) permits spontaneous activation of the G-protein-coupled mating pathway in Saccharomyces cerevisiae at levels normally seen only in the presence of ligand. Our work demonstrates the occurence of spontaneous tripartite G-protein signalling in vivo and identifies a requirement for RGS proteins in preventing such receptor-independent activation.}, author = {Daria Siekhaus and Drubin, David G}, journal = {Nature Cell Biology}, number = {3}, pages = {231 -- 235}, publisher = {Nature Publishing Group}, title = {{Spontaneous receptor-independent heterotrimeric G-protein signalling in an RGS mutant}}, doi = {10.1038/ncb941}, volume = {5}, year = {2003}, } @article{3151, abstract = {Biosynthesis of most peptide hormones and neuropeptides requires proteolytic excision of the active peptide from inactive proprotein precursors, an activity carried out by subtilisin-like proprotein convertases (SPCs) in constitutive or regulated secretory pathways. The Drosophila amontillado (amon) gene encodes a homolog of the mammalian PC2 protein, an SPC that functions in the regulated secretory pathway in neuroendocrine tissues. We have identified amon mutants by isolating ethylmethanesulfonate (EMS)-induced lethal and visible mutations that define two complementation groups in the amon interval at 97D1 of the third chromosome. DNA sequencing identified the amon complementation group and the DNA sequence change for each of the nine amon alleles isolated. amon mutants display partial embryonic lethality, are defective in larval growth, and arrest during the first to second instar larval molt. Mutant larvae can be rescued by heat-shock-induced expression of the amon protein. Rescued larvae arrest at the subsequent larval molt, suggesting that amon is also required for the second to third instar larval molt. Our data indicate that the amon proprotein convertase is required during embryogenesis and larval development in Drosophila and support the hypothesis that AMON acts to proteolytically process peptide hormones that regulate hatching, larval growth, and larval ecdysis.}, author = {Rayburn, Lowell Y and Gooding, Holly C and Choksi, Semil P and Maloney, Dhea and Kidd, Ambrose R and Daria Siekhaus and Bender, Michael}, journal = {Genetics}, number = {1}, pages = {227 -- 237}, publisher = {Genetics Society of America}, title = {{Amontillado, the Drosophila homolog of the prohormone processing protease PC2, is required during embryogenesis and early larval development}}, volume = {163}, year = {2003}, } @inproceedings{3170, abstract = {Geodesic active contours and graph cuts are two standard image segmentation techniques. We introduce a new segmentation method combining some of their benefits. Our main intuition is that any cut on a graph embedded in some continuous space can be interpreted as a contour (in 2D) or a surface (in 3D). We show how to build a grid graph and set its edge weights so that the cost of cuts is arbitrarily close to the length (area) of the corresponding contours (surfaces) for any anisotropic Riemannian metric. There are two interesting consequences of this technical result. First, graph cut algorithms can be used to find globally minimum geodesic contours (minimal surfaces in 3D) under arbitrary Riemannian metric for a given set of boundary conditions. Second, we show how to minimize metrication artifacts in existing graph-cut based methods in vision. Theoretically speaking, our work provides an interesting link between several branches of mathematics -differential geometry, integral geometry, and combinatorial optimization. The main technical problem is solved using Cauchy-Crofton formula from integral geometry.}, author = {Boykov, Yuri and Vladimir Kolmogorov}, pages = {26 -- 33}, publisher = {IEEE}, title = {{Computing geodesics and minimal surfaces via graph cuts}}, doi = {10.1109/ICCV.2003.1238310}, volume = {1}, year = {2003}, } @inproceedings{3171, abstract = {Reconstructing a 3-D scene from more than one camera is a classical problem in computer vision. One of the major sources of difficulty is the fact that not all scene elements are visible from all cameras. In the last few years, two promising approaches have been developed 11,12 that formulate the scene reconstruction problem in terms of energy minimization, and minimize the energy using graph cuts. These energy minimization approaches treat the input images symmetrically, handle visibility constraints correctly, and allow spatial smoothness to be enforced. However, these algorithm propose different problem formulations, and handle a limited class of smoothness terms. One algorithm 11 uses a problem formulation that is restricted to two-camera stereo, and imposes smoothness between a pair of cameras. The other algorithm 12 can handle an arbitrary number of cameras, but imposes smoothness only with respect to a single camera. In this paper we give a more general energy minimization formulation for the problem, which allows a larger class of spatial smoothness constraints. We show that our formulation includes both of the previous approaches as special cases, as well as permitting new energy functions. Experimental results on real data with ground truth are also included. }, author = {Vladimir Kolmogorov and Zabih, Ramin and Gortler, Steven}, pages = {501 -- 516}, publisher = {Springer}, title = {{Generalized multi camera scene reconstruction using graph cuts}}, doi = {10.1007/978-3-540-45063-4_32}, volume = {2683}, year = {2003}, } @inproceedings{3174, abstract = {We address visual correspondence problems without assuming that scene points have similar intensities in different views. This situation is common, usually due to non-lambertian scenes or to differences between cameras. We use maximization of mutual information, a powerful technique for registering images that requires no a priori model of the relationship between scene intensities in different views. However, it has proven difficult to use mutual information to compute dense visual correspondence. Comparing fixed-size windows via mutual information suffers from the well-known problems of fixed windows, namely poor performance at discontinuities and in low-texture regions. In this paper, we show how to compute visual correspondence using mutual information without suffering from these problems. Using 'a simple approximation, mutual information can be incorporated into the standard energy minimization framework used in early vision. The energy can then be efficiently minimized using graph cuts, which preserve discontinuities and handle low-texture regions. The resulting algorithm combines the accurate disparity maps that come from graph cuts with the tolerance for intensity changes that comes from mutual information.}, author = {Kim, Junhwan and Vladimir Kolmogorov and Zabih, Ramin}, pages = {1033 -- 1040}, publisher = {IEEE}, title = {{Visual correspondence using energy minimization and mutual information}}, doi = {10.1109/ICCV.2003.1238463}, volume = {2}, year = {2003}, } @article{3209, abstract = {We show that the fixed alphabet shortest common supersequence (SCS) and the fixed alphabet longest common subsequence (LCS) problems parameterized in the number of strings are W[1]-hard. Unless W[1]=FPT, this rules out the existence of algorithms with time complexity of O(f(k)nα) for those problems. Here n is the size of the problem instance, α is constant, k is the number of strings and f is any function of k. The fixed alphabet version of the LCS problem is of particular interest considering the importance of sequence comparison (e.g. multiple sequence alignment) in the fixed length alphabet world of DNA and protein sequences.}, author = {Krzysztof Pietrzak}, journal = {Journal of Computer and System Sciences}, number = {4}, pages = {757 -- 771}, publisher = {Elsevier}, title = {{On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems}}, doi = {10.1016/S0022-0000(03)00078-3}, volume = {67}, year = {2003}, } @inproceedings{3210, abstract = {Luby and Rackoff showed how to construct a (super-)pseudo-random permutation {0,1}2n→ {0,1}2n from some number r of pseudo-random functions {0,1}n → {0,1}n. Their construction, motivated by DES, consists of a cascade of r Feistel permutations. A Feistel permutation 1for a pseudo-random function f is defined as (L, R) → (R,L ⊕ f (R)), where L and R are the left and right part of the input and ⊕ denotes bitwise XOR or, in this paper, any other group operation on {0,1}n. The only non-trivial step of the security proof consists of proving that the cascade of r Feistel permutations with independent uniform random functions {0,1}n → {0,1}n, denoted Ψ2nr is indistinguishable from a uniform random permutation {0,1}2n → {0,1}2n by any computationally unbounded adaptive distinguisher making at most O(2cn) combined chosen plaintext/ciphertext queries for any c < α, where a is a security parameter. Luby and Rackoff proved α = 1/2 for r = 4. A natural problem, proposed by Pieprzyk is to improve on α for larger r. The best known result, α = 3/4 for r = 6, is due to Patarin. In this paper we prove a = 1 -O(1/r), i.e., the trivial upper bound α = 1 can be approached. The proof uses some new techniques that can be of independent interest. }, author = {Maurer, Ueli M and Krzysztof Pietrzak}, pages = {544 -- 561}, publisher = {Springer}, title = {{The security of many round Luby Rackoff pseudo random permutations}}, doi = {10.1007/3-540-39200-9_34}, volume = {2656}, year = {2003}, } @article{11121, abstract = {In metazoa, the nuclear envelope breaks down and reforms during each cell cycle. Nuclear pore complexes (NPCs), which serve as channels for transport between the nucleus and cytoplasm1, assemble into the reforming nuclear envelope in a sequential process involving association of a subset of NPC proteins, nucleoporins, with chromatin followed by the formation of a closed nuclear envelope fenestrated by NPCs2,3,4,5,6,7. How chromatin recruitment of nucleoporins and NPC assembly are regulated is unknown. Here we demonstrate that RanGTP production is required to dissociate nucleoporins Nup107, Nup153 and Nup358 from Importin β, to target them to chromatin and to induce association between separate NPC subcomplexes. Additionally, either an excess of RanGTP or removal of Importin β induces formation of NPC-containing membrane structures—annulate lamellae—both in vitro in the absence of chromatin and in vivo. Annulate lamellae formation is strongly and specifically inhibited by an excess of Importin β. The data demonstrate that RanGTP triggers distinct steps of NPC assembly, and suggest a mechanism for the spatial restriction of NPC assembly to the surface of chromatin.}, author = {Walther, Tobias C. and Askjaer, Peter and Gentzel, Marc and Habermann, Anja and Griffiths, Gareth and Wilm, Matthias and Mattaj, Iain W. and HETZER, Martin W}, issn = {1476-4687}, journal = {Nature}, keywords = {Multidisciplinary}, number = {6949}, pages = {689--694}, publisher = {Springer Nature}, title = {{RanGTP mediates nuclear pore complex assembly}}, doi = {10.1038/nature01898}, volume = {424}, year = {2003}, } @article{11122, abstract = {Nuclear pore complexes (NPCs) are large multiprotein assemblies that allow traffic between the cytoplasm and the nucleus. During mitosis in higher eukaryotes, the Nuclear Envelope (NE) breaks down and NPCs disassemble. How NPCs reassemble and incorporate into the NE upon mitotic exit is poorly understood. We demonstrate a function for the conserved Nup107-160 complex in this process. Partial in vivo depletion of Nup133 or Nup107 via RNAi in HeLa cells resulted in reduced levels of multiple nucleoporins and decreased NPC density in the NE. Immunodepletion of the entire Nup107-160 complex from in vitro nuclear assembly reactions produced nuclei with a continuous NE but no NPCs. This phenotype was reversible only if Nup107-160 complex was readded before closed NE formation. Depletion also prevented association of FG-repeat nucleoporins with chromatin. We propose a stepwise model in which postmitotic NPC assembly initiates on chromatin via early recruitment of the Nup107-160 complex.}, author = {Walther, Tobias C. and Alves, Annabelle and Pickersgill, Helen and Loı̈odice, Isabelle and HETZER, Martin W and Galy, Vincent and Hülsmann, Bastian B. and Köcher, Thomas and Wilm, Matthias and Allen, Terry and Mattaj, Iain W. and Doye, Valérie}, issn = {0092-8674}, journal = {Cell}, keywords = {General Biochemistry, Genetics and Molecular Biology}, number = {2}, pages = {195--206}, publisher = {Elsevier}, title = {{The conserved Nup107-160 complex is critical for nuclear pore complex assembly}}, doi = {10.1016/s0092-8674(03)00235-6}, volume = {113}, year = {2003}, } @article{11764, abstract = {In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of the paper is a technique that leads to algorithms that optimize several natural metrics, such as max-stretch, total flow time, max flow time, and total completion time. In particular, we show how to achieve optimum total flow time and optimum max-stretch if we increase the capacity of the underlying network by a logarithmic factor. We show that the resource augmentation is necessary by proving polynomial lower bounds on the max-stretch and total flow time for the case where online and offline algorithms are using same-capacity edges. Moreover, we also give polylogarithmic lower bounds on the resource augmentation factor necessary in order to keep the total flow time and max-stretch within a constant factor of optimum.}, author = {Goel, Ashish and Henzinger, Monika H and Plotkin, Serge and Tardos, Eva}, issn = {0196-6774}, journal = {Journal of Algorithms}, number = {2}, pages = {314--332}, publisher = {Elsevier}, title = {{Scheduling data transfers in a network and the set scheduling problem}}, doi = {10.1016/s0196-6774(03)00054-3}, volume = {48}, year = {2003}, } @article{11766, abstract = {This paper studies the multicast routing and admission control problem on unit-capacity tree and mesh topologies in the throughput model. The problem is a generalization of the edge-disjoint paths problem and is NP-hard both on trees and meshes. We study both the offline and the online version of the problem: In the offline setting, we give the first constant-factor approximation algorithm for trees, and an -factor approximation algorithm for meshes. In the online setting, we give the first polylogarithmic competitive online algorithm for tree and mesh topologies. No polylogarithmic-competitive algorithm is possible on general network topologies (Lower bounds for on-line graph problems with application to on-line circuits and optical routing, in: Proceedings of the 28th ACM Symposium on Theory of Computing, 1996, pp. 531–540) and there exists a polylogarithmic lower bound on the competitive ratio of any online algorithm on tree topologies (Making commitments in the face of uncertainity: how to pick a winner almost every time, in: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 1996, pp. 519–530). We prove the same lower bound for meshes.}, author = {Henzinger, Monika H and Leonardi, Stefano}, issn = {0022-0000}, journal = {Journal of Computer and System Sciences}, number = {3}, pages = {567--611}, publisher = {Elsevier}, title = {{Scheduling multicasts on unit-capacity trees and meshes}}, doi = {10.1016/s0022-0000(03)00043-6}, volume = {66}, year = {2003}, } @article{847, abstract = {The accumulation of genome-wide information on single nucleotide polymorphisms in humans provides an unprecedented opportunity to detect the evolutionary forces responsible for heterogeneity of the level of genetic variability across loci. Previous studies have shown that history of recombination events has produced long haplotype blocks in the human genome, which contribute to this heterogeneity. Other factors, however, such as natural selection or the heterogeneity of mutation rates across loci, may also lead to heterogeneity of genetic variability. We compared synonymous and non-synonymous variability within human genes with their divergence from murine orthologs. We separately analyzed the non-synonymous variants predicted to damage protein structure or function and the variants predicted to be functionally benign. The predictions were based on comparative sequence analysis and, in some cases, on the analysis of protein structure. A strong correlation between non-synonymous, benign variability and non-synonymous human-mouse divergence suggests that selection played an important role in shaping the pattern of variability in coding regions of human genes. However, the lack of correlation between deleterious variability and evolutionary divergence shows that a substantial proportion of the observed non-synonymous single-nucleotide polymorphisms reduces fitness and never reaches fixation. Evolutionary and medical implications of the impact of selection on human polymorphisms are discussed.}, author = {Sunyaev, Shamil R and Fyodor Kondrashov and Bork, Peer and Ramensky, Vasily}, journal = {Human Molecular Genetics}, number = {24}, pages = {3325 -- 3330}, publisher = {Oxford University Press}, title = {{Impact of selection, mutation rate and genetic drift on human genetic variation}}, doi = {10.1093/hmg/ddg359}, volume = {12}, year = {2003}, } @article{8519, author = {Kaloshin, Vadim}, issn = {0020-9910}, journal = {Inventiones mathematicae}, keywords = {General Mathematics}, number = {3}, pages = {451--512}, publisher = {Springer Nature}, title = {{The existential Hilbert 16-th problem and an estimate for cyclicity of elementary polycycles}}, doi = {10.1007/s00222-002-0244-9}, volume = {151}, year = {2003}, } @article{876, abstract = {Alternative splicing is thought to be a major source of functional diversity in animal proteins. We analyzed the evolutionary conservation of proteins encoded by alternatively spliced genes and predicted the ancestral state for 73 cases of alternative splicing (25 insertions and 48 deletions). The amino acid sequences of most of the inserts in proteins produced by alternative splicing are as conserved as the surrounding sequences. Thus, alternative splicing often creates novel isoforms by the insertion of new, functional protein sequences that probably originated from noncoding sequences of introns.}, author = {Fyodor Kondrashov and Koonin, Eugene V}, journal = {Trends in Genetics}, number = {3}, pages = {115 -- 119}, publisher = {Elsevier}, title = {{Evolution of alternative splicing: Deletions, insertions and origin of functional parts of proteins from intron sequences}}, doi = {10.1016/S0168-9525(02)00029-X}, volume = {19}, year = {2003}, } @article{166, abstract = {For any number field k, upper bounds are established for the number of k-rational points of bounded height on non-singular del Pezzo surfaces defined over k, which are equipped with suitable conic bundle structures over k.}, author = {Browning, Timothy D and Swarbick Jones, M}, journal = {Proceedings of the Bonn session in analytic number theory and diophantine equations}, publisher = {Mathematisches Institut der Universität Bonn}, title = {{Counting rational points on del Pezzo surfaces of degree 5}}, volume = {360}, year = {2003}, } @article{1959, abstract = {The molecular organization of bacterial NADH: ubiquinone oxidoreductase (complex I or NDH-1) is not established, apart from a rough separation into dehydrogenase, connecting and membrane domains. In this work, complex I was purified from Escherichia coli and fragmented by replacing dodecylmaltoside with other detergents. Exchange into decyl maltoside led to the removal of the hydrophobic subunit NuoL from the otherwise intact complex. Diheptanoyl phosphocholine led to the loss of NuoL and NuoM subunits, whereas other subunits remained in the complex. The presence of N,N-dimethyldodecylamine N-oxide or Triton X-100 led to further disruption of the membrane domain into fragments containing NuoL/M/N, NuoA/K/N, and NuoH/J subunits. Among the hydrophilic subunits, NuoCD was most readily dissociated from the complex, whereas NuoB was partially dissociated from the peripheral arm assembly in N,N-dimethyldodecylamine N-oxide. A model of subunit arrangement in bacterial complex I based on these data is proposed. Subunits NuoL and NuoM, which are homologous to antiporters and are implicated in proton pumping, are located at the distal end of the membrane arm, spatially separated from the redox centers of the peripheral arm. This is consistent with proposals that the mechanism of proton pumping by complex I is likely to involve long range conformational changes.}, author = {Holt, Peter J and Morgan, David J and Leonid Sazanov}, journal = {Journal of Biological Chemistry}, number = {44}, pages = {43114 -- 43120}, publisher = {American Society for Biochemistry and Molecular Biology}, title = {{The location of NuoL and NuoM subunits in the membrane domain of the Escherichia coli Complex I: implications for the mechanism of proton pumping}}, doi = {10.1074/jbc.M308247200}, volume = {278}, year = {2003}, } @article{1960, abstract = {NADH-ubiquinone oxidoreductase (complex I or NDH-1) was purified from the BL21 strain of Escherichia coli using an improved procedure. The complex was effectively stabilized by addition of divalent cations and lipids, making the preparation suitable for structural studies. The ubiquinone reductase activity of the enzyme was fully restored by addition of native E. coli lipids. Two different two-dimensional crystal forms, with p2 and p3 symmetry, were obtained using lipids containing native E. coli extracts. Analysis of the crystals showed that they are formed by fully intact complex I in an L-shaped conformation. Activity assays and single particle analysis indicated that complex I maintains this structure in detergent solution and does not adopt a different conformation in the active state. Thus, we provide the first experimental evidence that complex I from E. coli has an L-shape in a lipid bilayer and confirm that this is also the case for the active enzyme in solution. This suggests strongly that bacterial complex I exists in an L-shaped conformation in vivo. Our results also indicate that native lipids play an important role in the activation, stabilization and, as a consequence, crystallization of purified complex I from E. coli.}, author = {Leonid Sazanov and Carroll, Joe D and Holt, Peter J and Toime, Laurence J and Fearnley, Ian M}, journal = {Journal of Biological Chemistry}, number = {21}, pages = {19483 -- 19491}, publisher = {American Society for Biochemistry and Molecular Biology}, title = {{A role for native lipids in the stabilization and two dimensional crystallization of the Escherichia coli NADH ubiquinone oxidoreductase (complex I)}}, doi = {10.1074/jbc.M208959200}, volume = {278}, year = {2003}, } @article{205, author = {Timothy Browning}, journal = {Acta Arithmetica}, number = {3}, pages = {275 -- 295}, publisher = {Instytut Matematyczny}, title = {{Counting rational points on cubic and quartic surfaces}}, doi = {10.4064/aa108-3-7}, volume = {108}, year = {2003}, } @article{206, abstract = {Let T ⊂ ℙ 4 be a non-singular threefold of degree at least four. Then we show that the number of points in T(ℚ), with height at most B, is o(B 3) or B → ∞.}, author = {Timothy Browning}, journal = {Quarterly Journal of Mathematics}, number = {1}, pages = {33 -- 39}, publisher = {Unknown}, title = {{A note on the distribution of rational points on threefolds}}, doi = {10.1093/qjmath/54.1.33}, volume = {54}, year = {2003}, } @article{207, author = {Browning, Timothy D}, journal = {Mathematical Proceedings of the Cambridge Philosophical Society}, number = {3}, pages = {385 -- 395}, publisher = {Cambridge University Press}, title = {{Sums of four biquadrates}}, doi = {10.1017/S0305004102006382}, volume = {134}, year = {2003}, }