The frameshifting RNA element (FSE) in coronaviruses (CoVs) regulates the programmed −1 ribosomal frameshift (−1 PRF) mechanism common to many viruses. The FSE is of particular interest as a promising drug candidate. Its associated pseudoknot or stem loop structure is thought to play a large role in frameshifting and thus viral protein production. To investigate the FSE structural evolution, we use our graph theory-based methods for representing RNA secondary structures in the RNA-As-Graphs (RAG) framework to calculate conformational landscapes of viral FSEs with increasing sequence lengths for representative 10 Alpha and 13 Beta-CoVs. By following length-dependent conformational changes, we show that FSE sequences encode many possible competing stems which in turn favor certain FSE topologies, including a variety of pseudoknots, stem loops, and junctions. We explain alternative competing stems and topological FSE changes by recurring patterns of mutations. At the same time, FSE topology robustness can be understood by shifted stems within different sequence contexts and base pair coevolution. We further propose that the topology changes reflected by length-dependent conformations contribute to tuning the frameshifting efficiency. Our work provides tools to analyze virus sequence/structure correlations, explains how sequence and FSE structure have evolved for CoVs, and provides insights into potential mutations for therapeutic applications against a broad spectrum of CoV FSEs by targeting key sequence/structural transitions.
Asymptotic distribution-free changepoint detection for data with repeated observations
Summary A nonparametric framework for changepoint detection, based on scan statistics utilizing graphs that represent similarities among observations, is gaining attention owing to its flexibility and good performance for high-dimensional and non-Euclidean data sequences. However, this graph-based framework faces challenges when there are repeated observations in the sequence, which is often the case for discrete data such as network data. In this article we extend the graph-based framework to solve this problem by averaging or taking the union of all possible optimal graphs resulting from repeated observations. We consider both the single-changepoint alternative and the changed-interval alternative, and derive analytical formulas to control the Type I error for the new methods, making them readily applicable to large datasets. The extended methods are illustrated on an application in detecting changes in a sequence of dynamic networks over time. All proposed methods are implemented in an $\texttt{R}$ package $\texttt{gSeg}$ available on CRAN.
more »
« less
- NSF-PAR ID:
- 10334651
- Date Published:
- Journal Name:
- Biometrika
- ISSN:
- 0006-3444
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
-
null (Ed.)Most graph neural network models learn embeddings of nodes in static attributed graphs for predictive analysis. Recent attempts have been made to learn temporal proximity of the nodes. We find that real dynamic attributed graphs exhibit complex phenomenon of co-evolution between node attributes and graph structure. Learning node embeddings for forecasting change of node attributes and evolution of graph structure over time remains an open problem. In this work, we present a novel framework called CoEvoGNN for modeling dynamic attributed graph sequence. It preserves the impact of earlier graphs on the current graph by embedding generation through the sequence of attributed graphs. It has a temporal self-attention architecture to model long-range dependencies in the evolution. Moreover, CoEvoGNN optimizes model parameters jointly on two dynamic tasks, attribute inference and link prediction over time. So the model can capture the co-evolutionary patterns of attribute change and link formation. This framework can adapt to any graph neural algorithms so we implemented and investigated three methods based on it: CoEvoGCN, CoEvoGAT, and CoEvoSAGE. Experiments demonstrate the framework (and its methods) outperforms strong baseline methods on predicting an entire unseen graph snapshot of personal attributes and interpersonal links in dynamic social graphs and financial graphs.more » « less
-
Few-shot node classification is tasked to provide accurate predictions for nodes from novel classes with only few representative labeled nodes. This problem has drawn tremendous attention for its projection to prevailing real-world applications, such as product categorization for newly added commodity categories on an E-commerce platform with scarce records or diagnoses for rare diseases on a patient similarity graph. To tackle such challenging label scarcity issues in the non-Euclidean graph domain, meta-learning has become a successful and predominant paradigm. More recently, inspired by the development of graph self-supervised learning, transferring pretrained node embeddings for few-shot node classification could be a promising alternative to meta-learning but remains unexposed. In this work, we empirically demonstrate the potential of an alternative framework, \textit{Transductive Linear Probing}, that transfers pretrained node embeddings, which are learned from graph contrastive learning methods. We further extend the setting of few-shot node classification from standard fully supervised to a more realistic self-supervised setting, where meta-learning methods cannot be easily deployed due to the shortage of supervision from training classes. Surprisingly, even without any ground-truth labels, transductive linear probing with self-supervised graph contrastive pretraining can outperform the state-of-the-art fully supervised meta-learning based methods under the same protocol. We hope this work can shed new light on few-shot node classification problems and foster future research on learning from scarcely labeled instances on graphs.more » « less
-
null (Ed.)The key role of emotions in human life is undeniable. The question of whether there exists a brain pattern associated with a specific emotion is the theme of many affective neuroscience studies. In this work, we bring to bear graph signal processing (GSP) techniques to tackle the problem of automatic emotion recognition using brain signals. GSP is an extension of classical signal processing methods to complex networks where there exists an inherent relation graph. With the help of GSP, we propose a new framework for learning class-specific discriminative graphs. To that end, firstly we assume for each class of observations there exists a latent underlying graph representation. Secondly, we consider the observations are smooth on their corresponding class-specific sough graph while they are non-smooth on other classes’ graphs. The learned class-specific graph-based representations can act as sub-dictionaries and be utilized for the task of emotion classification. Applying the proposed method on an electroencephalogram (EEG) emotion recognition dataset indicates the superiority of our framework over other state-of-the-art methods.more » « less
-
Context-free language reachability (CFL-reachability) is a fundamental framework for program analysis. A large variety of static analyses can be formulated as CFL-reachability problems, which determines whether specific source-sink pairs in an edge-labeled graph are connected by a reachable path, i.e., a path whose edge labels form a string accepted by the given CFL. Computing CFL-reachability is expensive. The fastest algorithm exhibits a slightly subcubic time complexity with respect to the input graph size. Improving the scalability of CFL-reachability is of practical interest, but reducing the time complexity is inherently difficult. In this paper, we focus on improving the scalability of CFL-reachability from a more practical perspective---reducing the input graph size. Our idea arises from the existence of trivial edges, i.e., edges that do not affect any reachable path in CFL-reachability. We observe that two nodes joined by trivial edges can be folded---by merging the two nodes with all the edges joining them removed---without affecting the CFL-reachability result. By studying the characteristic of the recursive state machines (RSMs), an alternative form of CFLs, we propose an approach to identify foldable node pairs without the need to verify the underlying reachable paths (which is equivalent to solving the CFL-reachability problem). In particular, given a CFL-reachability problem instance with an input graph G and an RSM, based on the correspondence between paths in G and state transitions in RSM, we propose a graph folding principle, which can determine whether two adjacent nodes are foldable by examining only their incoming and outgoing edges. On top of the graph folding principle, we propose an efficient graph folding algorithm GF. The time complexity of GF is linear with respect to the number of nodes in the input graph. Our evaluations on two clients (alias analysis and value-flow analysis) show that GF significantly accelerates RSM/CFL-reachability by reducing the input graph size. On average, for value-flow analysis, GF reduces 60.96% of nodes and 42.67% of edges of the input graphs, obtaining a speedup of 4.65× and a memory usage reduction of 57.35%. For alias analysis, GF reduces 38.93% of nodes and 35.61% of edges of the input graphs, obtaining a speedup of 3.21× and a memory usage reduction of 65.19%.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1093/biomet/asab048
