Optimizing gap costs
With the existence of reference alignments specifically compiled for the purpose of RNA alignment benchmarks, program parameters can be specifically optimized for RNA alignments.
Parameters for MAFFT version 5 [25] have been optimized by K. Katoh using BRAliBase II's data-set1 [22]. The gap-cost values of MAFFT version 4 (gap-open penalty op = 0.51 and gap-extension penalty ep = 0.041) turned out to be far too low. Applying the improved values (op = 1.53 and ep = 0.123; these are the default in versions ≥ 5.667) to the new BRAliBase 2.1 datasets results in a dramatic performance gain (exemplified in Figure 1 for alignment sets with five sequences). Similarly, parameters for MUSCLE [16,26] have been optimized by its author.
Figure 1  MAFFT (FFT-NS-2) and ClustalW performance with optimized and old parameters. PROALIGN (earlier identified to be a good aligner [22]) is included as a reference. Performance is measured as BRALISCORE vs. reference APSI and exemplified for k = 5 sequences. MAFFT version 5.667 was used with optimized parameters, which are default in version 5.667, and with (old) parameters of version 4, respectively; CLUSTALW was used either with default parameters or with optimized parameters (see Table 2 and text). Motivated by the successful optimizations of MAFFT and MUSCLE parameters, we searched for optimal gap-costs of CLUSTALW [27,28]. We varied gap-open (go) and gap-extension (ge) penalties from 7.5 to 22.5 and from 3.33 to 9.99, respectively (default values of CLUSTALW for RNA/DNA sequences are go = 15.0 and ge = 6.66, respectively). Ranks derived by Friedman tests are averaged over all alignment sets, i. e. consisting of 2, 3, 5, 7, 10, and 15 sequences. Table 2 summarizes the results. Alignments created with higher gap-open penalties score significantly better. A combination of go = 22.5 and ge = 0.83 is optimal for the tested parameter range. It should be noted that this performance gain results mainly from a better SCI, whereas the SPS' remains almost the same.
Table 2  Averaged ranks derived from Friedman rank sum tests for ClustalW's gap parameter optimization.
ge
go  0.42  0.83  1.67  3.33  4.99  6.66  8.32  9.99
7.5  56.0  55.0  54.0  53.0  51.2  50.0  47.0  42.8
11.25  47.5  44.0  41.5  37.2  34.5  27.3  28.2  31.5
15.0  20.8  24.0  20.0  14.5  13.5   15.5  22.3  29.3
18.75  10.8  8.3  8.2  7.5  11.3  20.8  27.5  35.8
22.5  4.7   2.8  3.7  8.8  17.7  27.0  34.5  39.2
26.25  5.8  5.5  8.8  17.5  31.2  36.7  42.3  46.2
30.0  15.2  17.2  22.8  32.8  39.3  45.0  49.0  51.5
Ranks (smaller values mean better performance) for each gap-open (go)/gap-extension (ge) penalty combination are based on the BRALISCORE averaged over all alignment sets with k ∈ {2, 3, 5, 7, 10, 15} sequences and APSI ≤ 80 %. CLUSTALW's default and the optimized value combinations are given in bold-face. Similarly we optimized gap values for the recently published PRANK [29]. Average ranks can be found in Table 3. Default values (go = 0.025 and ge = 0.5) are too high. Due to time reasons we did not test all parameter combinations; optimal values found so far are 10 times lower than the default values. One should bear in mind that Friedman rank tests do not indicate to which degree a particular program or option works better, but that it consistently performs better. The actual performance gain can be visualized by plotting BRALISCORE vs. reference APSI (see Figure 1). For MAFFT the new options result in an extreme performance gain whereas CLUSTALW gap parameter optimization only yields a modest improvement indicating that CLUSTALW default options are already near optimal. In both cases the influence of optimized parameters has its greatest impact at sequence identities ≤ 55% APSI.
Table 3  Averaged ranks derived from Friedman rank sum tests for prank's gap parameter optimization.
ge
go  0.05  0.125  0.1875  0.25  0.375  0.5
0.0025  3.5  2.0  4.8  NA  NA  NA
0.00625  6.8  3.5  3.2  NA  NA  NA
0.00938  8.8  6.5  8.0  NA  NA  NA
0.0125  NA  NA  NA  8.2  11.0  13.5
0.01875  NA  NA  NA  12.8  12.5  15.8
0.025  NA  NA  NA  15.8  17.2   19.0
0.03125  NA  NA  NA  20.0  22.0  23.8
0.0375  NA  NA  NA  25.0  27.0  27.8
Ranks (smaller values mean better performance) for each gap-open (go)/gap-extension (ge) value combination are averaged over all alignment sets with k ∈ {5, 7, 10, 15} sequences and APSI ≤ 80 %. The default option for PRANK version 1508b is given in bold-face. Values for sets k2 and k3 are missing because PRANK crashed repeatedly with these sets, but we needed all values to compute the Friedman tests.