Dataset Information

Structator: fast index-based search for RNA sequence-structure patterns.

ABSTRACT: BACKGROUND: The secondary structure of RNA molecules is intimately related to their function and often more conserved than the sequence. Hence, the important task of searching databases for RNAs requires to match sequence-structure patterns. Unfortunately, current tools for this task have, in the best case, a running time that is only linear in the size of sequence databases. Furthermore, established index data structures for fast sequence matching, like suffix trees or arrays, cannot benefit from the complementarity constraints introduced by the secondary structure of RNAs. RESULTS: We present a novel method and readily applicable software for time efficient matching of RNA sequence-structure patterns in sequence databases. Our approach is based on affix arrays, a recently introduced index data structure, preprocessed from the target database. Affix arrays support bidirectional pattern search, which is required for efficiently handling the structural constraints of the pattern. Structural patterns like stem-loops can be matched inside out, such that the loop region is matched first and then the pairing bases on the boundaries are matched consecutively. This allows to exploit base pairing information for search space reduction and leads to an expected running time that is sublinear in the size of the sequence database. The incorporation of a new chaining approach in the search of RNA sequence-structure patterns enables the description of molecules folding into complex secondary structures with multiple ordered patterns. The chaining approach removes spurious matches from the set of intermediate results, in particular of patterns with little specificity. In benchmark experiments on the Rfam database, our method runs up to two orders of magnitude faster than previous methods. CONCLUSIONS: The presented method's sublinear expected running time makes it well suited for RNA sequence-structure pattern matching in large sequence databases. RNA molecules containing several stem-loop substructures can be described by multiple sequence-structure patterns and their matches are efficiently handled by a novel chaining method. Beyond our algorithmic contributions, we provide with Structator a complete and robust open-source software solution for index-based search of RNA sequence-structure patterns. The Structator software is available at http://www.zbh.uni-hamburg.de/Structator.

SUBMITTER: Meyer F

PROVIDER: S-EPMC3154205 | biostudies-literature | 2011

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Structator: fast index-based search for RNA sequence-structure patterns.

Meyer Fernando F Kurtz Stefan S Backofen Rolf R Will Sebastian S Beckstette Michael M

BMC bioinformatics 20110527

<h4>Background</h4>The secondary structure of RNA molecules is intimately related to their function and often more conserved than the sequence. Hence, the important task of searching databases for RNAs requires to match sequence-structure patterns. Unfortunately, current tools for this task have, in the best case, a running time that is only linear in the size of sequence databases. Furthermore, established index data structures for fast sequence matching, like suffix trees or arrays, cannot ben ...[more]

PMID: 21619640

Similar Datasets

Project description:BackgroundIt is well known that the search for homologous RNAs is more effective if both sequence and structure information is incorporated into the search. However, current tools for searching with RNA sequence-structure patterns cannot fully handle mutations occurring on both these levels or are simply not fast enough for searching large sequence databases because of the high computational costs of the underlying sequence-structure alignment problem.ResultsWe present new fast index-based and online algorithms for approximate matching of RNA sequence-structure patterns supporting a full set of edit operations on single bases and base pairs. Our methods efficiently compute semi-global alignments of structural RNA patterns and substrings of the target sequence whose costs satisfy a user-defined sequence-structure edit distance threshold. For this purpose, we introduce a new computing scheme to optimally reuse the entries of the required dynamic programming matrices for all substrings and combine it with a technique for avoiding the alignment computation of non-matching substrings. Our new index-based methods exploit suffix arrays preprocessed from the target database and achieve running times that are sublinear in the size of the searched sequences. To support the description of RNA molecules that fold into complex secondary structures with multiple ordered sequence-structure patterns, we use fast algorithms for the local or global chaining of approximate sequence-structure pattern matches. The chaining step removes spurious matches from the set of intermediate results, in particular of patterns with little specificity. In benchmark experiments on the Rfam database, our improved online algorithm is faster than the best previous method by up to factor 45. Our best new index-based algorithm achieves a speedup of factor 560.ConclusionsThe presented methods achieve considerable speedups compared to the best previous method. This, together with the expected sublinear running time of the presented index-based algorithms, allows for the first time approximate matching of RNA sequence-structure patterns in large sequence databases. Beyond the algorithmic contributions, we provide with RaligNAtor a robust and well documented open-source software package implementing the algorithms presented in this manuscript. The RaligNAtor software is available at http://www.zbh.uni-hamburg.de/ralignator.

Project description:BACKGROUND:The search for distant homologs has become an import issue in genome annotation. A particular difficulty is posed by divergent homologs that have lost recognizable sequence similarity. This same problem also arises in the recognition of novel members of large classes of RNAs such as snoRNAs or microRNAs that consist of families unrelated by common descent. Current homology search tools for structured RNAs are either based entirely on sequence similarity (such as blast or hmmer) or combine sequence and secondary structure. The most prominent example of the latter class of tools is Infernal. Alternatives are descriptor-based methods. In most practical applications published to-date, however, the information contained in covariance models or manually prescribed search patterns is dominated by sequence information. Here we ask two related questions: (1) Is secondary structure alone informative for homology search and the detection of novel members of RNA classes? (2) To what extent is the thermodynamic propensity of the target sequence to fold into the correct secondary structure helpful for this task? RESULTS:Sequence-structure alignment can be used as an alternative search strategy. In this scenario, the query consists of a base pairing probability matrix, which can be derived either from a single sequence or from a multiple alignment representing a set of known representatives. Sequence information can be optionally added to the query. The target sequence is pre-processed to obtain local base pairing probabilities. As a search engine we devised a semi-global scanning variant of LocARNA's algorithm for sequence-structure alignment. The LocARNAscan tool is optimized for speed and low memory consumption. In benchmarking experiments on artificial data we observe that the inclusion of thermodynamic stability is helpful, albeit only in a regime of extremely low sequence information in the query. We observe, furthermore, that the sensitivity is bounded in particular by the limited accuracy of the predicted local structures of the target sequence. CONCLUSIONS:Although we demonstrate that a purely structure-based homology search is feasible in principle, it is unlikely to outperform tools such as Infernal in most application scenarios, where a substantial amount of sequence information is typically available. The LocARNAscan approach will profit, however, from high throughput methods to determine RNA secondary structure. In transcriptome-wide applications, such methods will provide accurate structure annotations on the target side. AVAILABILITY:Source code of the free software LocARNAscan 1.0 and supplementary data are available at http://www.bioinf.uni-leipzig.de/Software/LocARNAscan.

Project description:Parallels between phylogeny and ontogeny have been discussed since almost two centuries and a number of theories have been proposed to explain such patterns. Especially elusive is the so-called phylotypic stage, a phase during development where species within a phylum are particularly similar to each other. While this has formerly been interpreted as a recapitulation of phylogeny, it is nowadays thought to reflect an ontogenetic progression phase, where strong constraints on developmental regulation and gene interactions exist. Several studies have shown that genes expressed during this stage evolve slower, but it has so far not been possible to derive an unequivocal molecular signature associated with this stage. We use here a combination of phylostratigraphy and stage specific gene expression data to generate a cumulative index that reflects the evolutionary age of the transcriptome at given ontogenetic stages. Using zebrafish ontogeny and adult development as a model, we find that the phylotypic stage does indeed express the oldest transcriptome set and that younger sets are expressed during early and late development, thus faithfully mirroring the hourglass model of morphological divergence. Reproductively active animals show the youngest transcriptome, with major differences between males and females. Intriguingly, aging animals express also increasingly older genes. Comparisons with similar datasets from flies and nematodes show that this pattern occurs across phyla. Our results suggest that an old transcriptome marks the phylotypic phase and that phylogenetic differences at other ontogenetic stages correlate with the expression of newly evolved genes. Zebrafish (Danio rerio) were kept in 12L flow-through tanks at 26.5 °C (around 60 animals per tank). For accurate staging, fertilized eggs were collected within 15 min intervalls and incubated in Petri dishes at 28.5°C with water changes every 2-6 hours. After hatching, larvae were transferred to 1 liter tanks and kept at 28.5 °C. We took 72 samples in at least two biological replicates (147 experiments in total) that correspond to 61 stages across zebrafish ontogeny (50 stages before the sex could be clearly recognized plus 11 adult stages of males and females each). Staging was done according to post-fertilization time. Embryos were additionally staged under the dissecting microscope to check for the consistency of post-fertilization timing and morphological development at standard temperature (28.5 °C). Only healthy animals that showed the expected morphological features for a given post-fertilization time were sampled. Each sample contained around 50 individuals until the 1 day and 3 hour embryo stage, 15 individuals until the 10 day larval stage, 10 individuals until the 18 day larval stage, 5 individuals until the 45 days juvenile stage, while in later juvenile and adult stages we sampled males and females separately and each sample contained 2 individuals. All samples were snap frozen in liquid nitrogen and stored at -80 °C until RNA extraction. To avoid severe biases due to the excess of unfertilized eggs we squeezed eggs from adult females before freezing them in liquid nitrogen.

Dataset Information

Structator: fast index-based search for RNA sequence-structure patterns.

Publications

Structator: fast index-based search for RNA sequence-structure patterns.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets