where s(x i ) (and s(x j )) is the score for a single-stranded position x i and s(x i , x j ) is the score for paired bases x i and x j . In PETfold the single-stranded score of position x i consists of the evolutionary reliability R sg A,T,M (i) and the thermodynamic probability 1 n u q u f −1 A (i) over all sequences s u (1 ≤ u ≤ n) in the alignment, and the base pair score of the positions x i and x j consists of the evolutionary reliability R A,T,M (i, j) and the thermodynamic probability 1 n u p u f −1 A (i,j) . The optimal structure σ can be reproduced by backtracking from F (1, L) when L is the sequence length. In PETfold, we define ex-over(σ) = F (1, L).