The Dataset

The dataset consists of 85 multiple alignments of 10 sequences.
There are 17 sequence families, and there are five alignments for each family. The dataset is reasonably diverse;
its mean length varies from 54 bases to 291 bases, and
the mean pairwise sequence identities varies from 40% to 94%.
Additionally, we also used BRAlibaseII multiple alignment dataset for the comparison.

Accuracy Measures

The accuracy of the alignments is measured by the standard sum-of-pairs score (SPS).
To measure the efficiency of the structural alignment, the consensus structures are predicted
from the alignment results using the Pfold program.
The Matthews correlation coefficients (MCC) are then calculated for the predictions.
MCC is defined by the formula
MCC = (tp tn - fp fn)/ sqrt((tp + fp)(tp + fn)(tn + fp)(tn + fn))
where tp indicates the number of correctly predicted base pairs;
tn, the number of base pairs that are correctly predicted as unpaired;
fp, the number of incorrectly predicted base pairs;
and fn, the number of true base pairs that are not predicted.
Note that tn is computed in units of base pairs and is very large in most cases.
The numbers are computed by assigning both reference and predicted consensus
structures to each sequence using the alignment and then counting the matches and mismatches of
base pairs for all the sequences.

Comparison of the SPS and MCC values for several multiple alignment  programs. 

Each column show the SPS and MCC values of the alignment results. The MCC values are computed for the structures predicted by the Pfold software.
Each row shows the average values of SPS and MCC as "SPS/MCC" for each software.
The values in the "All'' row indicate the average values across all the families.
"Stemloc,'' "PMMulti'', "RNAcast'' and "Common'' indicate the average values across
the partial alignment set for which Stemloc, PMMulti, RNAcast,
and all the programs returned results, respectively.
For each row, the highest values of SPS and MCC are shown in bold type face.

 This shows the SPS and MCC values for the BRAlibaseII
multiple alignment dataset. Although the SPS and MCC values are
relatively high and the differences of scores among the programs are
smaller than the above dataset, Murlet still shows the highest
accuracies with regard to both the SPS and MCC values.

Comparison of time and memory usages

Elapsed time and the maximal resident memory for computing alignments of the datasets. In both figures, x-axis represents the mean length of the
sequence families. Y-axes represent the maximal resident physical memory
of the process in megabytes (MB) (left) and the elapsed time in minutes
(right). Each data point represents a specific sequence family of Table 2.
Only the alignments returned correctly are plotted. The memory and time
consumptions of ClustalW, ProbCons, and RNAcast are very small when
compared with those of the Sankoff-based programs, and several points for
these programs coincide in the figure.