Bioinformatics Advance Access originally published online on April 13, 2006
Bioinformatics 2006 22(13):1593-1599; doi:10.1093/bioinformatics/btl142
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
STRAL: progressive alignment of non-coding RNA using base pairing probability vectors in quadratic time
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 was proposed 20 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 structure and/or only pairwise alignment. Thus, despite recent advances, the proper alignment of multiple structural RNA sequences 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 downstream pairing probability. To test the robustness of the algorithm and the performance of the program, we scored alignments produced by STRAL against a large set of published reference alignments. The quality of alignments predicted by STRAL is far better than that obtained by standard sequence alignment programs, especially when sequence homologies drop below 
65%; nevertheless STRAL’s runtime is comparable to that of CLUSTALW.
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/
Contact: stral{at}biophys.uni-duesseldorf.de
Supplementary information: Supplementary data available at Bioinformatics online.
Received on February 10, 2006; revised on April 10, 2006; accepted on April 10, 2006
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  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]
|
|