For two unaligned RNA sequences Seq x and Seq y , the single sequence prediction method DotKnot returns structure element dictionaries derived from the probability dot plot. Let n and m be the number of structure elements in sequences Seq x and Seq y , respectively. Calculating the similarity scores and the optimal structure element alignment takes O(nm) time. Furthermore, nested structures are taken into account for significant outer stem pairs, which have estimated P-value less than . Let a be the number of significant stem pairs, where both stems are hairpin loops. For each significant outer hairpin loop pair, the optimal structure alignment of inner elements is computed. In the worst case, this increases time requirements to O(a Â nm). The number of structure elements depends on the base composition of the sequence. Empirically, n and m can be observed to grow linearly with the length of the sequence for uniform base distribution (see Supplementary Material). In practice, DotKnot-PW can be expected to run in the order of minutes for sequences shorter than 500 nt.