RNAscClust: clustering RNA sequences using structure conservation and graph based motifs.
BACKGROUND
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.


METHODS
RNAscClust is available at http://www.bioinf.uni-freiburg.de/Software/RNAscClust .


BACKGROUND
gorodkin@rth.dk or backofen@informatik.uni-freiburg.de.


BACKGROUND
Supplementary data are available at Bioinformatics online.
Bioinformatics Group, Department of Computer Science, University of Freiburg, Freiburg im Breisgau, Germany.
Milad
M
Miladi
Center for Non-coding RNA in Technology and Health, University of Copenhagen, Frederiksberg, Denmark.|Department of Veterinary and Animal Sciences, University of Copenhagen, Frederiksberg, Denmark.
Alexander
A
Junge
Bioinformatics Group, Department of Computer Science, University of Freiburg, Freiburg im Breisgau, Germany.
Fabrizio
F
Costa
Center for Non-coding RNA in Technology and Health, University of Copenhagen, Frederiksberg, Denmark.|Department of Veterinary and Animal Sciences, University of Copenhagen, Frederiksberg, Denmark.
Stefan E
SE
Seemann
Center for Non-coding RNA in Technology and Health, University of Copenhagen, Frederiksberg, Denmark.|Department of Veterinary and Animal Sciences, University of Copenhagen, Frederiksberg, Denmark.
Jakob Hull
JH
Havgaard
Center for Non-coding RNA in Technology and Health, University of Copenhagen, Frederiksberg, Denmark.|Department of Veterinary and Animal Sciences, University of Copenhagen, Frederiksberg, Denmark.
Jan
J
Gorodkin
Bioinformatics Group, Department of Computer Science, University of Freiburg, Freiburg im Breisgau, Germany.|Center for Non-coding RNA in Technology and Health, University of Copenhagen, Frederiksberg, Denmark.|Center for Biological Signalling Studies (BIOSS), Cluster of Excellence, University of Freiburg, Freiburg im Breisgau, Germany.
Rolf
R
Backofen
D000465:Algorithms; D016000:Cluster Analysis; D006801:Humans; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry*; D017423:Sequence Analysis, RNA / Q000379:methods*; D012984:Software
D012313:RNA