title: STRAL: progressive alignment of non-coding RNA using base pairing probability vectors in quadratic time.
abstract: BACKGROUND
  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 approximately 65%; nevertheless StrAl's runtime is comparable to that of ClustalW.
authors.affiliation: Heinrich-Heine-Universität Düsseldorf, Institut für Physikalische Biologie D-40225 Düsseldorf, Germany.
authors.forename: Deniz
authors.initials: D
authors.lastname: Dalli
authors.forename: Andreas
authors.initials: A
authors.lastname: Wilm
authors.forename: Indra
authors.initials: I
authors.lastname: Mainz
authors.forename: Gerhard
authors.initials: G
authors.lastname: Steger
mesh_terms: D000465:Algorithms; D020029:Base Pairing; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods*; D015233:Models, Statistical; D008969:Molecular Sequence Data; D009690:Nucleic Acid Conformation; D010802:Phylogeny; D011336:Probability; D012313:RNA / Q000737:chemistry*; D022661:RNA, Untranslated / Q000737:chemistry*; D016415:Sequence Alignment; D012984:Software; D013995:Time
chemical_list: D022661:RNA, Untranslated; D012313:RNA