Background
Correctly aligning RNAs in terms of sequence and structure is a notoriously difficult problem.
Unfortunately, the solution proposed by Sankoff [1] 20 years ago has a complexity of O(n3m) in time, and O(n2m) in space, for m sequences of length n. Thus, most structure alignment programs (e.g. DYNALIGN [2], FOLDALIGN [3], PMCOMP [4], or STEMLOC [5]) implement lightweight variants of Sankoff's algorithm, but are still computationally demanding. Consequently, researchers often create an initial sequence alignment that is afterwards corrected manually or by the aid of RNA alignment editors (e. g. CONSTRUCT [6], JPHYDIT [7], RALEE [8], or SARSE [9]) to satisfy known structural constraints. The question which alignment technique and/or program performs best under which conditions has been extensively investigated for proteins. The first exhaustive protein alignment benchmark [10] used the so called BAliBASE (Benchmark Alignment dataBASE) [11]. BAliBASE is widely used and has been updated twice since the original publication (BAliBASE 2 and 3, [12,13]). There are a number of other protein alignment databases for example HOMSTRAD [14], OXBench [15], PREFAB [16], SABmark [17], or SMART [18].
These databases contain only sets of protein sequences and, as a reference, high quality alignments of these sets. As a result, emerging alignment tools are generally not tested on non-coding RNA (ncRNA), despite the availability of rather reliable RNA alignments from databases like 5S Ribosomal RNA Database [19], SRPDB [20], or the tRNA database [21].
The BRAliBase (Benchmark RNA Alignment dataBase) dataset used in the first comprehensive RNA alignment benchmark published so far [22] was constructed using alignments from release 5.0 of the Rfam database [23], a large collection of hand-curated multiple RNA sequence alignments. The dataset consists of two parts: the first, which contains RNA sets of five sequences from Group I introns, 5S rRNA, tRNA and U5 spliceosomal RNA, was used for assessing the quality of sequence alignment programs such as CLUSTALW. The other part, consisting of only pairwise tRNA alignments, was used to test a selection of structural alignment programs such as FOLDALIGN, DYNALIGN and PMCOMP. The single sets have an average pairwise sequence identity (APSI) ranging from 20 to 100 %.
Here we extend the previous reference alignment sets significantly in terms of the number and diversity of alignments and the number of sequences per alignment. We present an updated benchmark on the formerly identified "good aligners" and (fast) sequence alignment programs using new or optimized program versions. The performance of programs is rated by Friedman rank sum and Wilcoxon tests. We restricted our selection of alignment programs to multiple "sequence" alignment programs because – at least for the computing resources available to us – most structural alignment programs are either too time and memory demanding, or they are restricted to pairwise alignment. Next, we demonstrate for several programs that default program parameters are not optimal for RNA alignment, but can easily be optimized. Furthermore, we evaluate the influence of sequence number per alignment on program performance. One major conclusion is that iterative alignment programs clearly outperform progressive alignment programs, particularly when sequence identity is low and more than five sequences are aligned.