Few-shot image classification has attracted extensive attention, which aims to recognize unseen classes given only a few labeled samples. Due to the large intraclass variances and interclass similarity of remote sensing scenes, the task under such circumstance is much more challenging than general few-shot image classification. Most existing prototype-based few-shot algorithms usually calculate prototypes directly from support samples and ignore the validity of prototypes, which results in a decline in the accuracy of subsequent inferences based on prototypes. To tackle this problem, we propose a Siamese-prototype network (SPNet) with prototype self-calibration (SC) and intercalibration (IC). First, to acquire more accurate prototypes, we utilize the supervision information from support labels to calibrate the prototypes generated from support features. This process is called SC. Second, we propose to consider the confidence scores of the query samples as another type of prototypes, which are then used to predict the support samples in the same way. Thus, the information interaction between support and query samples is implicitly a further calibration for prototypes (so-called IC). Our model is optimized with three losses, of which two additional losses help the model to learn more representative prototypes and make more accurate predictions. With no additional parameters to be learned, our model is very lightweight and convenient to employ. The experiments on three public remote sensing image datasets demonstrate competitive performance compared with other advanced few-shot image classification approaches. The source code is available athttps://github.com/zoraup/SPNet.

Software systems evolve throughout their life cycles. Many revisions are produced over time. Verifying each revision of the software is impractical. Regression verification suggests reusing intermediate results from the previous verification runs. This paper studies regression verification via summary reuse. Not only procedure summaries, but also loop summaries are proposed to be reused. This paper proposes a fully automatic regression verification technique in the context of CEGAR. A lazy counterexample analysis technique is developed to improve the efficiency of summary reuse. We performed extensive experiments on two large sets of industrial programs (3,675 revisions of 488 Linux kernel device drivers). Results show that our summary reuse technique saves 84 to 93 percent analysis time of the regression verification.

In this paper, we develop a novel graph theoretic approach for protein threading. In order to perform the protein sequence-structure alignment in threading both efficiently and accurately, we develop a graph model to describe the tertiary structure of a protein family and the alignment between a sequence and a family can be efficiently computed with a dynamic programming algorithm when the tree width of the graph model is a small integer. Our experiments show that this new approach is significantly faster than existing tools for threading and can achieve comparable prediction accuracy.

MOTIVATION: Given the importance of non-coding RNAs to cellular regulatory functions, it would be highly desirable to have accurate computational prediction of RNA 3D structure, a task which remains challenging. Even for a short RNA sequence, the space of tertiary conformations is immense; existing methods to identify native-like conformations mostly resort to random sampling of conformations to achieve computational feasibility. However, native conformations may not be examined and prediction accuracy may be compromised due to sampling. State-of-the-art methods have yet to deliver satisfactory predictions for RNAs of length beyond 50 nucleotides. RESULTS: This paper presents a method to tackle a key step in the RNA 3D structure prediction problem, the prediction of the nucleotide interactions that constitute the desired 3D structure. The research is based on a novel graph model, called a backbone k-tree, to tightly constrain the nucleotide interaction relationships considered for RNA 3D structures. It is shown that the new model makes it possible to efficiently predict the optimal set of nucleotide interactions (including the non-canonical interactions in all recently revealed families) from the query sequence along with known or predicted canonical basepairs. The preliminary results indicate that in most cases the new method can predict with a high accuracy the nucleotide interactions that constitute the 3D structure of the query sequence. It thus provides a useful tool for the accurate prediction of RNA 3D structure. AVAILABILITY AND IMPLEMENTATION: The source package for BkTree is available at http://rna-informatics.uga.edu/index.php?f=software&p=BkTree. CONTACT: [email protected] or [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

UNLABELLED: TRFolder-W is a web server capable of predicting core structures of telomerase RNA (TR) in yeast genomes. TRFolder is a command-line Python toolkit for TR-specific structure prediction. We developed a web-version built on the django web framework, leveraging the work done previously, to include enhancements to increase flexibility of usage. To date, there are five core sub-structures commonly found in TR of fungal species, which are the template region, downstream pseudoknot, boundary element, core-closing stem and triple helix. The aim of TRFolder-W is to use the five core structures as fundamental units to predict potential TR genes for yeast, and to provide a user-friendly interface. Moreover, the application of TRFolder-W can be extended to predict the characteristic structure on species other than fungal species. AVAILABILITY: The web server TRFolder-W is available at http://rna-informatics.uga.edu/?f=software&p=TRFolder-w.

BACKGROUND: The computational identification of RNAs in genomic sequences requires the identification of signals of RNA sequences. Shannon base pairing entropy is an indicator for RNA secondary structure fold certainty in detection of structural, non-coding RNAs (ncRNAs). Under the Boltzmann ensemble of secondary structures, the probability of a base pair is estimated from its frequency across all the alternative equilibrium structures. However, such an entropy has yet to deliver the desired performance for distinguishing ncRNAs from random sequences. Developing novel methods to improve the entropy measure performance may result in more effective ncRNA gene finding based on structure detection. RESULTS: This paper shows that the measuring performance of base pairing entropy can be significantly improved with a constrained secondary structure ensemble in which only canonical base pairs are assumed to occur in energetically stable stems in a fold. This constraint actually reduces the space of the secondary structure and may lower the probabilities of base pairs unfavorable to the native fold. Indeed, base pairing entropies computed with this constrained model demonstrate substantially narrowed gaps of Z-scores between ncRNAs, as well as drastic increases in the Z-score for all 13 tested ncRNA sets, compared to shuffled sequences. CONCLUSIONS: These results suggest the viability of developing effective structure-based ncRNA gene finding methods by investigating secondary structure ensembles of ncRNAs.

RNA secondary structure plays the scaffolding role for RNA tertiary conformation. Accurate secondary structure prediction can not only identify double-stranded helices and single stranded-loops but also help provide information for potential tertiary interaction motifs critical to the 3D conformation. The average accuracy in ab initio prediction remains 70%; performance improvement has only been limited to short RNA sequences. Due to intrinsic nucleotide interactions, prediction of tertiary interaction motifs is difficult without multiple, related sequences that are usually not available. This paper presents research that aims to improve the secondary structure prediction performance and to develop a capability to predict coaxial stacking between helices. Coaxial stacking positions two helices on the same axis, a tertiary motif present in almost all junctions that account for a high percentage of RNA tertiary structures. This research identified energetic rules for coaxial stacks and geometric constraints on stack combinations, which were applied to developing an efficient dynamic programming application for simultaneous prediction of secondary structure and coaxial stacking. Results on a number of non-coding RNA data sets, of short and moderately long lengths, show a performance improvement for secondary structure prediction when compared with existing methods. The program also demonstrates a capability for coaxial stacking prediction.

Abstract Summary: RNATOPS-W is a web server to search sequences for RNA secondary structures including pseudoknots. The server accepts an annotated RNA multiple structural alignment as a structural profile and genomic or other sequences to search. It is built upon RNATOPS, a command line C++software package for the same purpose, in which filters to speed up search are manually selected. RNATOPS-W improves upon RNATOPS by adding the function of automatic selection of a hidden Markov model (HMM) filter and also a friendly user interface for selection of a substructure filter by the user. In addition, RNATOPS-W complements existing RNA secondary structure search web servers that either use built-in structure profiles or are not able to detect pseudoknots. RNATOPS-W inherits the efficiency of RNATOPS in detecting large, complex RNA structures. Availability: The web server RNATOPS-W is available at the web site www.uga.edu/RNA-Informatics/?f=software&p=RNATOPS-w. The underlying search program RNATOPS can be downloaded at www.uga.edu/RNA-Informatics/?f=software&p=RNATOPS. Contact: [email protected] Supplementary information: Supplementary data are available at Bioinformatics online.

Abstract Motivation: Searching genomes for non-coding RNAs (ncRNAs) by their secondary structure has become an important goal for bioinformatics. For pseudoknot-free structures, ncRNA search can be effective based on the covariance model and CYK-type dynamic programming. However, the computational difficulty in aligning an RNA sequence to a pseudoknot has prohibited fast and accurate search of arbitrary RNA structures. Our previous work introduced a graph model for RNA pseudoknots and proposed to solve the structure–sequence alignment by graph optimization. Given k candidate regions in the target sequence for each of the n stems in the structure, we could compute a best alignment in time O(ktn) based upon a tree width t decomposition of the structure graph. However, to implement this method to programs that can routinely perform fast yet accurate RNA pseudoknot searches, we need novel heuristics to ensure that, without degrading the accuracy, only a small number of stem candidates need to be examined and a tree decomposition of a small tree width can always be found for the structure graph. Results: The current work builds on the previous one with newly developed preprocessing algorithms to reduce the values for parameters k and t and to implement the search method into a practical program, called RNATOPS, for RNA pseudoknot search. In particular, we introduce techniques, based on probabilistic profiling and distance penalty functions, which can identify for every stem just a small number k (e.g. k ≤ 10) of plausible regions in the target sequence to which the stem needs to align. We also devised a specialized tree decomposition algorithm that can yield tree decomposition of small tree width t (e.g. t ≤ 4) for almost all RNA structure graphs. Our experiments show that with RNATOPS it is possible to routinely search prokaryotic and eukaryotic genomes for specific RNA structures of medium to large sizes, including pseudoknots, with high sensitivity and high specificity, and in a reasonable amount of time. Availability: The source code in C++ for RNATOPS is available at www.uga.edu/RNA-Informatics/software/rnatops/ Contact: [email protected] Supplementary information: The online Supplementary Material contains all illustrative figures and tables referenced by this article.

The paper surveys parameterized algorithms and complexities for computational tasks on biopolymer sequences, including the problems of longest common subsequence, shortest common supersequence, pairwise sequence alignment, multiple sequencing alignment, structure–sequence alignment and structure–structure alignment. Algorithm techniques, built on the structural-unit level as well as on the residue level, are discussed.

Identifying operons at the whole genome scale of microbial organisms can facilitate deciphering of transcriptional regulation, biological networks and pathways. A number of computational methods, such as naive Bayesian and neural network approaches, have been employed for operon prediction to whole genome sequences of a number of prokaryotic organisms, based on features known to be associated with operons, such as intergenic distance, microarray expression data, phylogenetic profiles, clusters of orthologous groups (COG). In this paper, we introduce a decision tree approach to predict operon structures using three effective types of genomic data: intergenic distance, gene order conservation and COG. We calculated and analyzed frequency distributions of each attribute of known operons and non-operons of Escherichia coli (E. coli) K12 and Bacillus subtilis (R subtilis) 168, and constructed decision trees based on training examples to predict operons. The overall prediction accuracy is 94.1% for E. coli K12 and 91.0% for B. subtilis 168. We also applied four other classifiers, logistic regression, naive Bayesian, neural network and support vector machines on both organisms. The results indicate that the decision tree approach is the best classifier for operon prediction. The software package operonDT is freely available at http://www.cs.uga.edn/~che/OperonT

Computational alignment of a biopolymer sequence (e.g., an RNA or a protein) to a structure is an effective approach to predict and search for the structure of new sequences. To identify the structure of remote homologs, the structure-sequence alignment has to consider not only sequence similarity, but also spatially conserved conformations caused by residue interactions and, consequently, is computationally intractable. It is difficult to cope with the inefficiency without compromising alignment accuracy, especially for structure search in genomes or large databases. This paper introduces a novel method and a parameterized algorithm for structure-sequence alignment. Both the structure and the sequence are represented as graphs, where, in general, the graph for a biopolymer structure has a naturally small tree width. The algorithm constructs an optimal alignment by finding in the sequence graph the maximum valued subgraph isomorphic to the structure graph. It has the computational time complexity O[k(t)N(2)] for the structure of N residues and its tree decomposition of width t. Parameter k, small in nature, is determined by a statistical cutoff for the correspondence between the structure and the sequence. This paper demonstrates a successful application of the algorithm to RNA structure search used for noncoding RNA identification. An application to protein threading is also discussed.

SUMMARY: The purpose of our Binding-site Estimation Suite of Tools (BEST) is two-fold: to provide a platform for using and comparing different motif-finding programs for transcription factor binding site prediction, and to improve the accuracy of these predictions by further optimization. Our software package BEST includes four commonly used motif-finding programs: AlignACE, BioProspector, CONSENSUS and MEME, as well as the optimization program BioOptimizer. BEST allows the user to run programs either separately or sequentially and manages all programs by automating the common inputs and the optimization procedure. The BEST system was implemented in Qt, a C++ application development framework, and was compiled and executed on Linux operating systems. AVAILABILITY: BEST is available for download at http://www.cs.uga.edu/~che/BEST and http://www.fas.harvard.edu/~junliu/BEST CONTACT: [email protected], [email protected].

Given a collection of biologically related protein or DNA sequences, the basic multiple sequence alignment problem is to determine the most biologically plausible alignment of these sequences. Under the assumption that the collection of sequences arose from some common ancestor, an alignment can be used to infer the evolutionary history among the sequences, i.e., the most likely pattern of insertions, deletions and mutations that transformed one sequence into another. The general multiple sequence alignment problem is known to be NP-hard, and hence the problem of finding the best possible multiple sequence alignment is intractable. However, this does not preclude the possibility of developing algorithms that produce near optimal multiple sequence alignments in polynomial time. We examine techniques to combine efficient algorithms for near optimal global and local multiple sequence alignment with evolutionary computation techniques to search for better near optimal sequence alignments. We describe our evolutionary computation approach to multiple sequence alignment and present preliminary simulation results on a set of 17 clusters of orthologous groups of proteins (COGs). We compare the fitness of the alignments given by the proposed techniques with the fitness of CLUSTAL W alignments given in the COG database.

We investigate the relationship between circuit bottom fan-in and circuit size when circuit depth is fixed. We show that in order to compute certain functions, a moderate reduction in circuit bottom fan-in will cause significant increase in circuit size. In particular, we prove that there are functions that are computable by circuits of linear size and depth k with bottom fan-in 2 but require exponential size for circuits of depth k with bottom fan-in 1. A general scheme is established to study the trade-off between circuit bottom fan-in and circuit size. Based on this scheme, we are able to prove, for example, that for any integer c, there are functions that are computable by circuits of linear size and depth k with bottom fan-in $O(\log n)$ but that require exponential size for circuits of depth k with bottom fan-in c, and that for any constant $\epsilon> 0$, there are functions that are computable by circuits of linear size and depth k with bottom fan-in $\log n$ but that require superpolynomial size for circuits of depth k with bottom fan-in $O(\log^{1-\epsilon} n)$. A consequence of these results is that the three input read-modes of alternating Turing machines proposed in the literature are all distinct.

We investigate the relationship between circuit bottom fan-in and circuit size when circuit depth is fixed. We show that in order to compute certain functions, a moderate reduction in circuit bottom fan-in will cause significant increase in circuit size. In particular, we prove that there are functions that are computable by circuits of linear size and depth k with bottom fan-in 2 but require exponential size for circuits of depth k with bottom fan-in 1. A general scheme is established to study the trade-off between circuit bottom fan-in and circuit size. Based on this scheme, we are able to prove, for example, that for any integer c, there are functions that are computable by circuits of linear size and depth k with bottom fan-in O(log n) but require exponential size for circuits of depth k with bottom fan-in c, and that for any constant /spl epsiv/>0, there are functions that are computable by circuits of linear size and depth k with bottom fan-in log n but require superpolynomial size for circuits of depth k with bottom fan-in O(log/sup 1-/spl epsiv//n). A consequence of these results is that the three input read-modes of alternating Turing machines proposed in the literature are all distinct.

The relationship between nondeterminism and other computational resources is investigated based on the "guess-then-check" model GC. Systematic techniques are developed to construct natural complete languages for the classes defined by this model. This improves a number of previous results in the study of limited nondeterminism. Connections of the model GC to computational optimization problems are exhibited.