@inproceedings{4561, abstract = {We present a formalism for specifying component interfaces that expose component requirements on limited resources. The formalism permits an algorithmic check if two or more components, when put together, exceed the available resources. Moreover, the formalism can be used to compute the quantity of resources necessary for satisfying the requirements of a collection of components. The formalism can be instantiated in several ways. For example, several components may draw power from the same source. Then, the formalism supports compatibility checks such as: can two components, when put together, achieve their tasks without ever exceeding the available amount of peak power? or, can they achieve their tasks by using no more than the initially available amount of energy (i.e., power accumulated over time)? The corresponding quantitative questions that our algorithms answer are the following: what is the amount of peak power needed for two components to be put together? what is the corresponding amount of initial energy? To solve these questions, we model interfaces with resource requirements as games with quantitative objectives. The games are played on state spaces where each state is labeled by a number (representing, e.g., power consumption), and a play produces an infinite path of labels. The objective may be, for example, to minimize the largest label that occurs during a play. We illustrate our approach by modeling compatibility questions for the components of robot control software, and of wireless sensor networks.}, author = {Chakrabarti, Arindam and De Alfaro, Luca and Henzinger, Thomas A and Stoelinga, Mariëlle}, booktitle = {Third International Conference on Embedded Software}, isbn = {9783540202233}, location = {Philadelphia, PA, USA}, pages = {117 -- 133}, publisher = {ACM}, title = {{Resource interfaces}}, doi = {10.1007/978-3-540-45212-6_9}, volume = {2855}, year = {2003}, } @inproceedings{4628, abstract = {Discounting the future means that the value, today, of a unit payoffis 1 if the payoffo ccurs today, a if it occurs tomorrow, a 2 if it occurs the day after tomorrow, and so on, for some real-valued discount factor 0 < a < 1. Discounting (or inflation) is a key paradigm in economics and has been studied in Markov decision processes as well as game theory. We submit that discounting also has a natural place in systems engineering: for nonterminating systems, a potential bug in the far-away future is less troubling than a potential bug today. We therefore develop a systems theory with discounting. Our theory includes several basic elements: discounted versions of system properties that correspond to the ω-regular properties, fixpoint-based algorithms for checking discounted properties, and a quantitative notion of bisimilarity for capturing the difference between two states with respect to discounted properties. We present the theory in a general form that applies to probabilistic systems as well as multicomponent systems (games), but it readily specializes to classical transition systems. We show that discounting, besides its natural practical appeal, has also several mathematical benefits. First, the resulting theory is robust, in that small perturbations of a system can cause only small changes in the properties of the system. Second, the theory is computational, in that the values of discounted properties, as well as the discounted bisimilarity distance between states, can be computed to any desired degree of precision.}, author = {De Alfaro, Luca and Henzinger, Thomas A and Majumdar, Ritankar}, booktitle = {Proceedings of the 30th International Colloquium on Automata, Languages and Programming}, isbn = {9783540404934}, location = {Eindhoven, The Netherlands}, pages = {1022 -- 1037}, publisher = {Springer}, title = {{Discounting the future in systems theory}}, doi = {10.1007/3-540-45061-0_79}, volume = {2719}, year = {2003}, } @inproceedings{4630, abstract = {We consider concurrent two-person games played in real time, in which the players decide both which action to play, and when to play it. Such timed games differ from untimed games in two essential ways. First, players can take each other by surprise, because actions are played with delays that cannot be anticipated by the opponent. Second, a player should not be able to win the game by preventing time from diverging. We present a model of timed games that preserves the element of surprise and accounts for time divergence in a way that treats both players symmetrically and applies to all ω-regular winning conditions. We prove that the ability to take each other by surprise adds extra power to the players. For the case that the games are specified in the style of timed automata, we provide symbolic algorithms for their solution with respect to all ω-regular winning conditions. We also show that for these timed games, memory strategies are more powerful than memoryless strategies already in the case of reachability objectives.}, author = {De Alfaro, Luca and Faella, Marco and Henzinger, Thomas A and Majumdar, Ritankar and Stoelinga, Mariëlle}, booktitle = {Proceedings of the 14th International Conference on Concurrency Theory}, isbn = {9783540407539}, location = {Marseille, France}, pages = {144 -- 158}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{The element of surprise in timed games}}, doi = {10.1007/978-3-540-45187-7_9}, volume = {2761}, year = {2003}, } @article{576, abstract = {We study the free expansion of a pancake-shaped Bose-condensed gas, which is initially trapped under harmonic confinement and containing a vortex at its centre. In the case of a radial expansion holding the axial confinement fixed we consider various models for the interactions, depending on the thickness of the condensate relative to the value of the scattering length. We are thus able to evaluate different scattering regimes ranging from quasi-three-dimensional (Q3D) to strictly two-dimensional (2D). We find that as the system goes from Q3D to 2D the expansion rate of the condensate increases whereas that of the vortex core decreases. In the Q3D scattering regime we also examine a fully free expansion in 3D and find oscillatory behaviour for the vortex core radius: an initial fast expansion of the vortex core is followed by a slowing down. Such a nonuniform expansion rate of the vortex core implies that the timing of its observation should be chosen appropriately.}, author = {Hosten, Onur and Vignolo, Patrizia and Minguzzi, Anna and Tanatar, Bilal and Tosi, Mario}, issn = {1361-6455}, journal = {Journal of Physics B: Atomic, Molecular and Optical Physics}, number = {12}, publisher = {IOP Publishing }, title = {{Free expansion of two-dimensional condensates with a vortex}}, doi = {10.1088/0953-4075/36/12/306}, volume = {36}, year = {2003}, } @article{6156, abstract = {Social and solitary feeding in natural Caenorhabditis elegans isolates are associated with two alleles of the orphan G-protein-coupled receptor (GPCR) NPR-1: social feeders contain NPR-1 215F, whereas solitary feeders contain NPR-1 215V. Here we identify FMRFamide-related neuropeptides (FaRPs) encoded by the flp-18 and flp-21 genes as NPR-1 ligands and show that these peptides can differentially activate the NPR-1 215F and NPR-1 215V receptors. Multicopy overexpression of flp-21 transformed wild social animals into solitary feeders. Conversely, a flp-21 deletion partially phenocopied the npr-1(null) phenotype, which is consistent with NPR-1 activation by FLP-21 in vivo but also implicates other ligands for NPR-1. Phylogenetic studies indicate that the dominant npr-1 215V allele likely arose from an ancestral npr-1 215F gene in C. elegans. Our data suggest a model in which solitary feeding evolved in an ancestral social strain of C. elegans by a gain-of-function mutation that modified the response of NPR-1 to FLP-18 and FLP-21 ligands.}, author = {Rogers, Candida and Reale, Vincenzina and Kim, Kyuhyung and Chatwin, Heather and Li, Chris and Evans, Peter and de Bono, Mario}, issn = {1097-6256}, journal = {Nature Neuroscience}, number = {11}, pages = {1178--1185}, publisher = {Springer Nature}, title = {{Inhibition of Caenorhabditis elegans social feeding by FMRFamide-related peptide activation of NPR-1}}, doi = {10.1038/nn1140}, volume = {6}, year = {2003}, } @article{6157, abstract = {In many animal species individuals aggregate to live in groups. A range of experimental approaches in different animals, including studies of social feeding in nematodes, maternal behavior in rats and sheep, and pair-bonding in voles, are providing insights into the neural bases for these behaviors. These studies are delineating multiple neural circuits and gene networks in the brain that interact in ways that are as yet poorly understood to coordinate social behavior.}, author = {de Bono, Mario}, issn = {0022-3034}, journal = {Journal of Neurobiology}, number = {1}, pages = {78--92}, publisher = {Wiley}, title = {{Molecular approaches to aggregation behavior and social attachment}}, doi = {10.1002/neu.10162}, volume = {54}, year = {2003}, } @article{205, author = {Browning, Timothy D}, issn = {1730-6264}, journal = {Acta Arithmetica}, 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 = {Browning, Timothy D}, issn = {1464-3847}, 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}, } @article{208, abstract = {For any ε > 0 and any diagonal quadratic form Q ∈ Z[x1, x2, x3, x4] with a square‐free discriminant of modulus ΔQ ≠ 0, we establish the uniform estimate ≪ε B3/2+ε + B2+ε/Δ1/6Q for the number of rational points of height at most B lying in the projective surface Q = 0. }, author = {Browning, Timothy D}, issn = {1464-3847}, journal = {Quarterly Journal of Mathematics}, number = {1}, pages = {11 -- 31}, publisher = {Oxford Academic}, title = {{Counting rational points on diagonal quadratic surfaces}}, doi = {doi/10.1093/qjmath/54.1.11}, volume = {54}, 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 and Kondrashov, Fyodor and Bork, Peer and Ramensky, Vasily}, issn = {1460-2083}, journal = {Human Molecular Genetics}, number = {24}, pages = {3325 -- 3330}, publisher = {Oxford Academic}, 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 = {Kondrashov, Fyodor and Koonin, Eugene}, issn = {1362-4555}, 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{9455, abstract = {Proteins of the ARGONAUTE family are important in diverse posttranscriptional RNA-mediated gene-silencing systems as well as in transcriptional gene silencing in Drosophila and fission yeast and in programmed DNA elimination in Tetrahymena. We cloned ARGONAUTE4 (AGO4) from a screen for mutants that suppress silencing of the Arabidopsis SUPERMAN(SUP) gene. The ago4-1 mutant reactivated silentSUP alleles and decreased CpNpG and asymmetric DNA methylation as well as histone H3 lysine-9 methylation. In addition,ago4-1 blocked histone and DNA methylation and the accumulation of 25-nucleotide small interfering RNAs (siRNAs) that correspond to the retroelement AtSN1. These results suggest that AGO4 and long siRNAs direct chromatin modifications, including histone methylation and non-CpG DNA methylation.}, author = {Zilberman, Daniel and Cao, Xiaofeng and Jacobsen, Steven E.}, issn = {1095-9203}, journal = {Science}, keywords = {Multidisciplinary}, number = {5607}, pages = {716--719}, publisher = {American Association for the Advancement of Science}, title = {{ARGONAUTE4 control of locus-specific siRNA accumulation and DNA and histone methylation}}, doi = {10.1126/science.1079695}, volume = {299}, year = {2003}, } @article{9495, abstract = {RNA interference is a conserved process in which double-stranded RNA is processed into 21–25 nucleotide siRNAs that trigger posttranscriptional gene silencing. In addition, plants display a phenomenon termed RNA-directed DNA methylation (RdDM) in which DNA with sequence identity to silenced RNA is de novo methylated at its cytosine residues. This methylation is not only at canonical CpG sites but also at cytosines in CpNpG and asymmetric sequence contexts. In this report, we study the role of the DRM and CMT3 DNA methyltransferase genes in the initiation and maintenance of RdDM. Neither drm nor cmt3 mutants affected the maintenance of preestablished RNA-directed CpG methylation. However, drm mutants showed a nearly complete loss of asymmetric methylation and a partial loss of CpNpG methylation. The remaining asymmetric and CpNpG methylation was dependent on the activity of CMT3, showing that DRM and CMT3 act redundantly to maintain non-CpG methylation. These DNA methyltransferases appear to act downstream of siRNAs, since drm1 drm2 cmt3 triple mutants show a lack of non-CpG methylation but elevated levels of siRNAs. Finally, we demonstrate that DRM activity is required for the initial establishment of RdDM in all sequence contexts including CpG, CpNpG, and asymmetric sites.}, author = {Cao, Xiaofeng and Aufsatz, Werner and Zilberman, Daniel and Mette, M.Florian and Huang, Michael S. and Matzke, Marjori and Jacobsen, Steven E.}, issn = {1879-0445}, journal = {Current Biology}, number = {24}, pages = {2212--2217}, publisher = {Elsevier}, title = {{Role of the DRM and CMT3 methyltransferases in RNA-directed DNA methylation}}, doi = {10.1016/j.cub.2003.11.052}, volume = {13}, year = {2003}, } @misc{3139, author = {Chen, Hsiao and Hippenmeyer, Simon and Arber, Silvia and Frank, Eric}, booktitle = {Current Opinion in Neurobiology}, issn = {1873-6882}, number = {1}, pages = {96 -- 102}, publisher = {Elsevier}, title = {{Development of the monosynaptic stretch reflex circuit}}, doi = {10.1016/S0959-4388(03)00006-0}, volume = {13}, year = {2003}, } @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 = {Siekhaus, Daria E and Drubin, David}, issn = {1476-4679}, journal = {Nature Cell Biology}, number = {3}, pages = {231 -- 235}, publisher = {Springer Nature}, 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 and Gooding, Holly and Choksi, Semil and Maloney, Dhea and Kidd, Ambrose and Siekhaus, Daria E and Bender, Michael}, issn = {1943-2631}, journal = {Genetics}, number = {1}, pages = {227 -- 237}, publisher = {Oxford Academic}, title = {{Amontillado, the Drosophila homolog of the prohormone processing protease PC2, is required during embryogenesis and early larval development}}, doi = {10.1093/genetics/163.1.227}, volume = {163}, 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 = {Kolmogorov, Vladimir and Zabih, Ramin and Gortler, Steven}, booktitle = {4th International Workshop}, isbn = {9783540404989}, location = {Lisbon, Portugal}, pages = {501 -- 516}, publisher = {Springer Nature}, title = {{Generalized multi camera scene reconstruction using graph cuts}}, doi = {10.1007/978-3-540-45063-4_32}, volume = {2683}, 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 = {Pietrzak, Krzysztof Z}, 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}, }