Bioinformatics Advance Access published online on April 13, 2006
Bioinformatics, doi:10.1093/bioinformatics/btl142
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1 Heinrich-Heine-Universität Düsseldorf, Institut für Physikalische Biologie, D-40225 Düsseldorf, Germany
* To whom correspondence should be addressed.
Motivation: Alignment of RNA has a wide range of applications, for example in phylogeny inference, consensus structure prediction and homology searches. Yet, aligning structural or non-coding RNAs (ncRNAs) correctly is notoriously difficult as these RNA sequences may evolve by compensatory mutations, which maintain base pairing but destroy sequence homology. Ideally, alignment programs would take RNA structure into account. The Sankoff algorithm for the simultaneous solution of RNA structure prediction and RNA sequence alignment has been proposed twenty years ago, but suffers from its exponential complexity. A number of programs implement lightweight versions of the Sankoff algorithm by restricting its application to a limited type of structures and/or only pairwise alignment. Thus, despite recent advances, the proper alignment of multiple structural RNA sequences still remains a problem. Results: Here we present STRAL, a heuristic method for alignment of ncRNA that reduces sequence-structure alignment to a two-dimensional problem similar to standard multiple sequence alignment. The scoring function takes into account sequence similarity as well as up- and down-stream pairing probability. To test the robustness of the algorithm and the performance of the program, we scored alignments produced by STRAL in comparison to a large set of published reference alignments. Quality of alignments predicted by STRAL is far better than that obtained by standard sequence alignment programs, especially when sequence homologies drop below Availability: STRAL is implemented in C. Source code (under GNU Public License) as well as a precompiled Debian package can be downloaded at http://www.biophys.uni-duesseldorf.de/stral/.
Received February 10, 2006
Revised April 10, 2006
Accepted April 10, 2006
Article
STRAL: progressive alignment of non-coding RNA using base pairing probability vectors in quadratic time
Deniz Dalli 1,
Andreas Wilm 1,
Indra Mainz 1,
and
Gerhard Steger 1 *
Gerhard Steger, E-mail: stral{at}biophys.uni-duesseldorf.de
Abstract 
65 %; nevertheless STRAL's runtime is comparable to that of CLUSTALW.
Associate Editor: Alex Bateman
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  R. R. Stocsits, H. Letsch, J. Hertel, B. Misof, and P. F. Stadler Accurate and efficient reconstruction of deep phylogenies from structured RNAs Nucleic Acids Res., October 1, 2009; 37(18): 6184 - 6193. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 Y. Tabei and K. Asai A local multiple alignment method for detection of non-coding RNA sequences Bioinformatics, June 15, 2009; 25(12): 1498 - 1505. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
K. Morita, Y. Saito, K. Sato, K. Oka, K. Hotta, and Y. Sakakibara Genome-wide searching with base-pairing kernel functions for noncoding RNAs: computational and expression analysis of snoRNA families in Caenorhabditis elegans Nucleic Acids Res., February 1, 2009; 37(3): 999 - 1009. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 K. Katoh and H. Toh Recent developments in the MAFFT multiple sequence alignment program Brief Bioinform, July 1, 2008; 9(4): 286 - 298. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C. B. Do, C.-S. Foo, and S. Batzoglou A max-margin model for efficient simultaneous alignment and folding of RNA sequences Bioinformatics, July 1, 2008; 24(13): i68 - i76. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Moretti, A. Wilm, D. G. Higgins, I. Xenarios, and C. Notredame R-Coffee: a web server for accurately aligning noncoding RNA sequences Nucleic Acids Res., July 1, 2008; 36(suppl_2): W10 - W13. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. Wilm, D. G. Higgins, and C. Notredame R-Coffee: a method for multiple alignment of non-coding RNA Nucleic Acids Res., May 1, 2008; 36(9): e52 - e52. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
F. Ferre, Y. Ponty, W. A. Lorenz, and P. Clote DIAL: a web server for the pairwise alignment of two RNA three-dimensional structures using nucleotide, dihedral angle and base-pairing similarities Nucleic Acids Res., July 13, 2007; 35(suppl_2): W659 - W668. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
E. Torarinsson, J. H. Havgaard, and J. Gorodkin Multiple structural alignment and clustering of RNA sequences Bioinformatics, April 15, 2007; 23(8): 926 - 932. [Abstract] [Full Text] [PDF]
|
|