RNAscClust: clustering RNA sequences using structure conservation and graph based motifs.

MOTIVATION: Clustering RNA sequences with common secondary structure is an essential step towards studying RNA function. Whereas structural RNA alignment strategies typically identify common structure for orthologous structured RNAs, clustering seeks to group paralogous RNAs based on structural similarities. However, existing approaches for clustering paralogous RNAs, do not take the compensatory base pair changes obtained from structure conservation in orthologous sequences into account. RESULTS: Here, we present RNAscClust , the implementation of a new algorithm to cluster a set of structured RNAs taking their respective structural conservation into account. For a set of multiple structural alignments of RNA sequences, each containing a paralog sequence included in a structural alignment of its orthologs, RNAscClust computes minimum free-energy structures for each sequence using conserved base pairs as prior information for the folding. The paralogs are then clustered using a graph kernel-based strategy, which identifies common structural features. We show that the clustering accuracy clearly benefits from an increasing degree of compensatory base pair changes in the alignments. AVAILABILITY AND IMPLEMENTATION: RNAscClust is available at http://www.bioinf.uni-freiburg.de/Software/RNAscClust . CONTACT: gorodkin@rth.dk or backofen@informatik.uni-freiburg.de. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Alignment-free comparative genomic screen for structured RNAs using coarse-grained secondary structure dot plots.

BACKGROUND: Structured non-coding RNAs play many different roles in the cells, but the annotation of these RNAs is lacking even within the human genome. The currently available computational tools are either too computationally heavy for use in full genomic screens or rely on pre-aligned sequences. METHODS: Here we present a fast and efficient method, DotcodeR, for detecting structurally similar RNAs in genomic sequences by comparing their corresponding coarse-grained secondary structure dot plots at string level. This allows us to perform an all-against-all scan of all window pairs from two genomes without alignment. RESULTS: Our computational experiments with simulated data and real chromosomes demonstrate that the presented method has good sensitivity. CONCLUSIONS: DotcodeR can be useful as a pre-filter in a genomic comparative scan for structured RNAs.

Structural profiles of human miRNA families from pairwise clustering.

UNLABELLED: MicroRNAs (miRNAs) are a group of small, approximately 21 nt long, riboregulators inhibiting gene expression at a post-transcriptional level. Their most distinctive structural feature is the foldback hairpin of their precursor pre-miRNAs. Even though each pre-miRNA deposited in miRBase has its secondary structure already predicted, little is known about the patterns of structural conservation among pre-miRNAs. We address this issue by clustering the human pre-miRNA sequences based on pairwise, sequence and secondary structure alignment using FOLDALIGN, followed by global multiple alignment of obtained clusters by WAR. As a result, the common secondary structure was successfully determined for four FOLDALIGN clusters: the RF00027 structural family of the Rfam database and three clusters with previously undescribed consensus structures. AVAILABILITY: http://genome.ku.dk/resources/mirclust

CRISPR-Cas9 off-targeting assessment with nucleic acid duplex energy parameters.

BACKGROUND: Recent experimental efforts of CRISPR-Cas9 systems have shown that off-target binding and cleavage are a concern for the system and that this is highly dependent on the selected guide RNA (gRNA) design. Computational predictions of off-targets have been proposed as an attractive and more feasible alternative to tedious experimental efforts. However, accurate scoring of the high number of putative off-targets plays a key role for the success of computational off-targeting assessment. RESULTS: We present an approximate binding energy model for the Cas9-gRNA-DNA complex, which systematically combines the energy parameters obtained for RNA-RNA, DNA-DNA, and RNA-DNA duplexes. Based on this model, two novel off-target assessment methods for gRNA selection in CRISPR-Cas9 applications are introduced: CRISPRoff to assign confidence scores to predicted off-targets and CRISPRspec to measure the specificity of the gRNA. We benchmark the methods against current state-of-the-art methods and show that both are in better agreement with experimental results. Furthermore, we show significant evidence supporting the inverse relationship between the on-target cleavage efficiency and specificity of the system, in which introduced binding energies are key components. CONCLUSIONS: The impact of the binding energies provides a direction for further studies of off-targeting mechanisms. The performance of CRISPRoff and CRISPRspec enables more accurate off-target evaluation for gRNA selections, prior to any CRISPR-Cas9 genome-editing application. For given gRNA sequences or all potential gRNAs in a given target region, CRISPRoff-based off-target predictions and CRISPRspec-based specificity evaluations can be carried out through our webserver at https://rth.dk/resources/crispr/ .

Assessing the miRNA sponge potential of RUNX1T1 in t(8;21) acute myeloid leukemia.

t(8;21) acute myeloid leukemia (AML) is characterized by a translocation between chromosomes 8 and 21 and formation of a distinctive RUNX1-RUNX1T1 fusion transcript. This translocation places RUNX1T1 under control of the RUNX1 promoter leading to a pronounced upregulation of RUNX1T1 transcripts in t(8;21) AML, compared to normal hematopoietic cells. We investigated the role of highly-upregulated RUNX1T1 under the hypothesis that it acts as competing endogenous RNA (ceRNA) titrating microRNAs (miRNAs) away from their target transcripts and thus contributes to AML formation. Using publicly available t(8;21) AML RNA-Seq and miRNA-Seq data available from The Cancer Genome Atlas (TCGA) project, we obtained a network consisting of 605 genes that may act as ceRNAs competing for miRNAs with the suggested RUNX1T1 miRNA sponge. Among the 605 ceRNA candidates, 121 have previously been implied in cancer development. Players in the integrin, cadherin, and Wnt signaling pathways affected by the RUNX1T1 sponge were overrepresented. Finally, among a set of 21 high interest RUNX1T1 ceRNAs we found multiple genes that have previously been linked to AML formation. In conclusion, our study offers a novel look at the role of the RUNX1-RUNX1T1 fusion transcript in t(8;21) AML beyond previously investigated genetic and epigenetic aberrations.

RNA structural alignments, part I: Sankoff-based approaches for structural alignments.

Simultaneous alignment and secondary structure prediction of RNA sequences is often referred to as "RNA structural alignment." A class of the methods for structural alignment is based on the principles proposed by Sankoff more than 25 years ago. The Sankoff algorithm simultaneously folds and aligns two or more sequences. The advantage of this algorithm over those that separate the folding and alignment steps is that it makes better predictions. The disadvantage is that it is slower and requires more computer memory to run. The amount of computational resources needed to run the Sankoff algorithm is so high that it took more than a decade before the first implementation of a Sankoff style algorithm was published. However, with the faster computers available today and the improved heuristics used in the implementations the Sankoff-based methods have become practical. This chapter describes the methods based on the Sankoff algorithm. All the practical implementations of the algorithm use heuristics to make them run in reasonable time and memory. These heuristics are also described in this chapter.

Pairwise local structural alignment of RNA sequences with sequence similarity less than 40%.

MOTIVATION: Searching for non-coding RNA (ncRNA) genes and structural RNA elements (eleRNA) are major challenges in gene finding today as these often are conserved in structure rather than in sequence. Even though the number of available methods is growing, it is still of interest to pairwise detect two genes with low sequence similarity, where the genes are part of a larger genomic region. RESULTS: Here we present such an approach for pairwise local alignment which is based on foldalign and the Sankoff algorithm for simultaneous structural alignment of multiple sequences. We include the ability to conduct mutual scans of two sequences of arbitrary length while searching for common local structural motifs of some maximum length. This drastically reduces the complexity of the algorithm. The scoring scheme includes structural parameters corresponding to those available for free energy as well as for substitution matrices similar to RIBOSUM. The new foldalign implementation is tested on a dataset where the ncRNAs and eleRNAs have sequence similarity <40% and where the ncRNAs and eleRNAs are energetically indistinguishable from the surrounding genomic sequence context. The method is tested in two ways: (1) its ability to find the common structure between the genes only and (2) its ability to locate ncRNAs and eleRNAs in a genomic context. In case (1), it makes sense to compare with methods like Dynalign, and the performances are very similar, but foldalign is substantially faster. The structure prediction performance for a family is typically around 0.7 using Matthews correlation coefficient. In case (2), the algorithm is successful at locating RNA families with an average sensitivity of 0.8 and a positive predictive value of 0.9 using a BLAST-like hit selection scheme. AVAILABILITY: The program is available online at http://foldalign.kvl.dk/