GraphClust: alignment-free structural clustering of local RNA secondary structures.
BACKGROUND
Clustering according to sequence-structure similarity has now become a generally accepted scheme for ncRNA annotation. Its application to complete genomic sequences as well as whole transcriptomes is therefore desirable but hindered by extremely high computational costs.


RESULTS
We present a novel linear-time, alignment-free method for comparing and clustering RNAs according to sequence and structure. The approach scales to datasets of hundreds of thousands of sequences. The quality of the retrieved clusters has been benchmarked against known ncRNA datasets and is comparable to state-of-the-art sequence-structure methods although achieving speedups of several orders of magnitude. A selection of applications aiming at the detection of novel structural ncRNAs are presented. Exemplarily, we predicted local structural elements specific to lincRNAs likely functionally associating involved transcripts to vital processes of the human nervous system. In total, we predicted 349 local structural RNA elements.


BACKGROUND
The GraphClust pipeline is available on request.
Bioinformatics Group, Department of Computer Science, University of Freiburg,Georges-Köhler-Allee 106, D-79110 Freiburg, Germany.
Steffen
S
Heyne
Fabrizio
F
Costa
Dominic
D
Rose
Rolf
R
Backofen
D000465:Algorithms; D000818:Animals; D001483:Base Sequence; D016000:Cluster Analysis; D019295:Computational Biology / Q000379:methods*; D006801:Humans; D008962:Models, Theoretical; D009690:Nucleic Acid Conformation; D059372:Nucleotide Motifs; D062085:RNA, Long Noncoding / Q000737:chemistry*; D016415:Sequence Alignment; D017423:Sequence Analysis, RNA / Q000379:methods*
D062085:RNA, Long Noncoding