Multiple alignment

Suppose p_A, p_C, p_G, p_U are the nucleotide probabilities obtained after the concatenation of all sequences. Let p₍, p_•, p₎ be computed by individually folding each sequence and taking the arithmetic average of probabilities of (, • and ) over all sequences. The mean and standard deviation of sequence and structure similarity are computed similar to Eqs (10)–(14).

Sequence multiplicative scaling factor α_seq and the structure additive shift factor α_str are computed from these values using Eqs (15) and (16).

As in CLUSTAL [42] and the CLUSTAL Omega [43], our software RNAmountAlign implements progressive multiple alignment using the Unweighted Pair Group Method with Arithmetic Mean (UPGMA) [44] and p. 360 of [41]. In UPGMA, one first defines a similarity matrix S, where S[i, j] is equal to (maximum) pairwise sequence similarity of sequences i and j. A rooted tree is then constructed by progressively creating a parent node of the two closest siblings. Parent nodes are profiles (PSSMs) that represent alignments of two or more sequences, hence can be treated as pseudo-sequences in a straightforward adaptation of pairwise alignment to the alignment of profiles. Let’s consider an alignment of N sequences A=(a11*⋯a1M*⋯aN1*⋯aNM*) composed of M columns. Let Ai={a1i*,a2i*,…,aNi*} denote column i of the alignment (for 1 ≤ i ≤ M). Suppose p(i, x), for x ∈ {A, C, G, U, −}, indicates the probability of occurrence of a nucleotide or gap at column i of alignment A. Then sequence similarity SEQSIM between two columns is defined by

where

The structural measure for a profile is computed from the incremental ensemble heights averaged over each column. Let m_A(i) denote the arithmetic average of incremental ensemble mountain height at column A_i

where maj*(i) is the incremental ensemble mountain height at position i of sequence aj* obtained from Eq (4). Here, let maj*(i)=0 if aji* is a gap. Structural similarity between two columns is defined by

Finally, the combined sequence/structure similarity is computed from