Search

Background: Multiple viruses including HIV, MERS-CoV (coronavirus responsible for Middle East Respiratory Syndrome, MERS), SARS-CoV (coronavirus responsible for SARS) and SARS-CoV-2 (coronavirus responsible for COVID-19) use a mechanism known as -1 programmed ribosomal frameshifting (-1 PRF) to successfully replicate. SARS-CoV-2 possesses a unique RNA pseudoknotted structure that stimulates -1 PRF. Recent experiments identified small molecules as antiviral agents that can bind to the pseudoknot and disrupt its stimulation of -1 PRF. Targeting -1 PRF in SARS-CoV-2 to impair viral replication can improve patients' prognoses.Crucial to developing these successful therapies is modeling the structure of the SARS-CoV-2 -1 PRF pseudoknot.Our goal is to expand knowledge of possible pseudoknot conformations. Results: Following a structural alignment approach, we identify similarities in -1 PRF pseudoknots of SARS-CoV-2, SARS-CoV, and MERS-CoV. We introduce Shapify, a novel algorithm that given an RNA sequence incorporates structural reactivity (SHAPE) data and partial structure information to output an RNA secondary structure prediction within a biologically sound hierarchical folding approach. Shapify helps us to better understand non-native SARS-CoV-2 -1 PRF pseudoknot conformations that are relevant to structure function and may correlate with -1 PRF efficiency. We provide in-depth analysis by investigating the structural landscape for the SARS-CoV-2 -1 PRF pseudoknot, including reference and mutated sequences. To better understand the impact of mutations, we provide insight on SARS-CoV-2 -1 PRF pseudoknot sequence mutations and their effect on the resulting structure. Conclusion: We identify the consensus structure for SARS-CoV, SARS-CoV-2, and MERS-CoV -1 PRF pseudoknots; this similarity in functional RNA structures aids treatment preparation for existing and emergent viruses. Shapify predictions are guided both by SHAPE data and partial structure information. Applied to the SARS-CoV-2 -1 PRF pseudoknot, Shapify unveiled previously unknown pathways from initial stems to pseudoknotted secondary structures. Where SHAPE data is unavailable we provide predictions for noteworthy SARS-CoV-2 -1 PRF mutated pseudoknot sequences. By contextualizing our work with available experimental data, our structure predictions motivate future RNA structure-function research and can aid 3-D modeling of pseudoknots.

Severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) has led to the COVID-19 pandemic; a pandemic of a scale that has not been seen in the modern era. Despite over 29 million reported cases and over 900, 000 deaths worldwide as of September 2020, herd immunity and widespread vaccination efforts by many experts are expected to be insufficient in addressing this crisis for the foreseeable future. Thus, there is an urgent need for treatments that can lessen the effects of SARS-CoV-2 in patients who become seriously affected. Many viruses including HIV, the common cold, SARS-CoV and SARS-CoV-2 use a unique mechanism known as −1 programmed ribosomal frameshifting (−1 PRF) to successfully replicate and infect cells in the human host. SARS-CoV (the coronavirus responsible for SARS) and SARS-CoV-2 possess a unique RNA structure, a three-stemmed pseudoknot, that stimulates −1 PRF. Recent experiments identified that small molecules can be introduced as antiviral agents to bind with the pseudoknot and disrupt its stimulation of −1 PRF. If successfully developed, small molecule therapy that targets −1 PRF in SARS-CoV-2 is an excellent strategy to improve patients’ prognoses. Crucial to developing these successful therapies is modeling the structure of the SARS-CoV-2 −1 PRF pseudoknot. Following a structural alignment approach, we identify similarities in the −1 PRF pseudoknots of the novel coronavirus SARS-CoV-2, the original SARS-CoV, as well as a third coronavirus: MERS-CoV, the coronavirus responsible for Middle East Respiratory Syndrome (MERS). In addition, we provide a better understanding of the SARS-CoV-2 −1 PRF pseudoknot by comprehensively investigating the structural landscape using a hierarchical folding approach. Since understanding the impact of mutations is vital to long-term success of treatments that are based on predicted RNA functional structures, we provide insight on SARS-CoV-2 −1 PRF pseudoknot sequence mutations and their effect on the resulting structure and its function.

We present a framework for using linear programming to solve a challenging problem in surface science, the elucidation of the structure and composition of adsorbed molecules from a mixture, using simulated data from polarized Raman experiments. In the past, methods applied in order to interpret such spectroscopic information were combinatorial approaches that are limited in scalability or accuracy. Quantum mechanical electronic structure calculations yield the optical response of a single molecule, from which spectra of a mixture can be determined by appropriate weighting. Furthermore, spectral obtained in different beam polarizations provide projections of the signal in the laboratory frame. We demonstrate that linear programming is an ideal tool for utilizing all of this information in order to provide the sought structural picture.

Vibrational spectroscopy is a valuable quantitative tool for the determination of structure at surfaces. Various techniques may be applicable and useful, depending on what is available, the transparency of the substrates, the need for in situ probes, and the degree of interfacial specificity required. We examine and compare signals in infrared absorption, Raman scattering, and vibrational sum-frequency generation spectroscopy to the underlying molecular response. In all of these experiments, varying the beam polarizations enables the orientation of specific chemical functional groups to be determined. However, the sensitivity of each technique is directly connected to the manner in which the molecular response manifests itself in the measured signal. Starting with simple distributions of a single vibrational mode, leading up to multiple vibrational bands in more complex orientation distributions, we compare these three techniques in terms of their sensitivity to features of the molecular orientat...

2D correlation analysis provides a powerful means of extracting structural and dynamical data from spectroscopic experiments. This has been successfully developed for techniques such as IR absorption spectroscopy, where the correlation has additionally been shown to increase the spectral resolution by observing the differing behavior of overlapping absorption bands in response to an external perturbation. Visible-infrared sum-frequency generation (SFG) spectroscopy combines many of the benefits of IR absorption and Raman scattering spectroscopy, and adds a unique structural perspective due to its surface specificity. Bringing the flexibility of 2D correlation analysis to SFG experiments would therefore further enhance the power and utility of this nonlinear vibrational spectroscopy. However, straightforward application of the correlation algorithms to homodyne SFG intensity data is not ideal as the SFG line shape often masks underlying spectral features, resulting in misleading correlation maps. We show that application of correlation analysis to heterodyne SFG experiments restores the qualitative utility of such analyses. An example is provided for the case of leucine adsorption onto surfaces of varying hydrophobicity.

Nowadays, textual databases are among the most rapidly growing collections of data. Some of these collections contain a new type of data that differs from classical numerical or textual data. These are long sequences of symbols, not divided into well-separated small tokens (words). The most prominent among such collections are databases of biological sequences, which are experiencing today an unprecedented growth rate. Starting in 2008, the "1000 Genomes Project" has been launched with the ultimate goal of collecting sequences of additional 1,500 Human genomes, 500 each of European, African, and East Asian origin. This will produce an extensive catalog of Human genetic variations. The size of just the raw sequences in this catalog would be about 5 terabytes. Querying strings without well-separated tokens poses a different set of challenges, typically addressed by building full-text indexes, which provide effective structures to index all the substrings of the given strings. Since full-text indexes occupy more space than the raw data, it is often necessary to use disk space for their construction. However, until recently, the construction of full-text indexes in secondary storage was considered impractical due to excessive I/O costs. Despite this, algorithms developed in the last decade demonstrated that efficient external construction of full-text indexes is indeed possible. This book is about large-scale construction and usage of full-text indexes. We focus mainly on suffix trees, and show efficient algorithms that can convert suffix trees to other kinds of full-text indexes and vice versa. There are four parts in this book. They are a mix of string searching theory with the reality of external memory constraints. The first part introduces general concepts of full-text indexes and shows the relationships between them. The second part presents the first series of external-memory construction algorithms that can handle the construction of full-text indexes for moderately large strings in the order of few gigabytes. The third part presents algorithms that scale for very large strings. The final part examines queries that can be facilitated by disk-resident full-text indexes. Table of Contents: Structures for Indexing Substrings / External Construction of Suffix Trees / Scaling Up: When the Input Exceeds the Main Memory / Queries for Disk-based Indexes / Conclusions and Open Problems

We describe the Ignite Distributed Collaborative Scientific Visualization System (IDCVS), a system which permits real-time interaction and visual collaboration around large data sets, with an initial emphasis on scientific data. The IDCVS offers such a collaborative environment, with real-time interaction on any device between users separated across the wide area. It provides seamless interaction and immediate updates even under heavy load and when users are widely separated: the design goal was to fetch a data set consisting of 30,000 points from a server and render it within 150ms, for a user anywhere in the world, and reflect changes made by a user in one location to all other users within a bound provided by network latency. The system was demonstrated successfully on a significant worldwide air pollution data set, with values on 10, 25, 50, and 100km worldwide grids, monthly over an 18-year period. It was demonstrated on a wide variety of clients, including laptop, tablet, and smartphone.

Recently there has been growing interest among psychologists in human performance on the Euclidean traveling salesperson problem (E-TSP). A debate has been initiated on what strategy people use in solving visually presented E-TSP instances. The most prominent hypothesis is the convex-hull hypothesis, originally proposed by MacGregor and Ormerod (1996). We argue that, in the literature so far, there is no evidence for this hypothesis. Alternatively we propose and motivate the hypothesis that people aim at avoiding crossings.

This article is concerned with how computer science, and more exactly computational complexity theory, can inform cognitive science. In particular, we suggest factors to be taken into account when investigating how people deal with computational hardness. This discussion will address the two upper levels of Marr’s Level Theory: the computational level and the algorithmic level. Our reasons for believing that humans indeed deal with hard cognitive functions are threefold: (1) Several computationally hard functions are suggested in the literature, e.g., in the areas of visual search, visual perception and analogical reasoning, linguistic processing, and decision making. (2) People appear to be attracted to computationally hard recreational puzzles and games. Examples of hard puzzles include Sudoku, Minesweeper, and the 15-Puzzle. (3) A number of research articles in the area of human problem solving suggest that humans are capable of solving hard computational problems, like the Euclidean Traveling Salesperson Problem, quickly and near-optimally. This article gives a brief introduction to some theories and foundations of complexity theory and motivates the use of computationally hard problems in human problem solving with a short survey of known results of human performance, a review of some computationally hard games and puzzles, and the connection between complexity theory and models of cognitive functions. We aim to illuminate the role that computer science, in particular complexity theory, can play in the study of human problem solving. Theoretical computer science can provide a wealth of interesting problems for human study, but it can also help to provide deep insight into these problems. In particular, we discuss the role that computer science can play when choosing computational problems for study and designing experiments to investigate human performance. Finally, we enumerate issues and pitfalls that can arise when choosing computationally hard problems as the subject of study, in turn motivating some interesting potential future lines of study. The pitfalls addressed include: choice of presentation and representation of problem instances, evaluation of problem comprehension, and the role of cognitive support in experiments. Our goal is not to exhaustively list all the ways in which these choices may impact experimental studies, but rather to provide a few simple examples in order to highlight possible pitfalls.