The space of alignments of two biological sequences:

We define a space of the alignments of two biological (DNA, RNA and protein) sequences and , denoted by , as follows. We set as a base index set, and a binary variable for is defined by

Then is a subset of and is defined by

Here is a set of index-sets:

The inclusion means that position in the sequence aligns with at most one position in the sequence in the alignment , means that position in the sequence aligns with at most one position in the sequence and means the alignment and is not crossing. Note that depends on only the length of two sequences, namely, and .

The space of secondary structures of RNA:

We define a space of the secondary structures of an RNA sequence , denoted by , as follows. We set as a base index set, and a binary variable for is defined by

Then is a subset of and is defined by

Here is a set of index-sets

The inclusion means that position in the sequence belongs to at most one base-pair in a secondary structure , and means two base-pairs whose relation is pseudo-knot are not allowed in . Note that depends on only the length of the RNA sequence , that is, .

The space of phylogenetic trees:

We define a space of phylogenetic trees (unrooted and multi-branch trees) of a set of , denoted by , as follows. We set , where , as a base index set and we define binary variables for by

Then is a subset of and is defined by

Lemma 1The number of elements in (i.e. ) is equal to where .

Lemma 2The topological distance ^[17] between two phylogenetic trees and in is

Remark 1If we assume the additional condition , then is a set of binary trees.

Probability distributions on

For two protein sequences and , a probability distribution over the space , which is the space of pairwise alignments of and defined in the previous section, is given by the following models.

1. Miyazawa model ^[13] and Probalign model ^[25]:
   
   
   where is the score of an alignment under the given scoring matrix (We define where is a score for the correspondence of bases and ), is the thermodynamic temperature and is the normalization constant, which is known as a partition function.
2. Pair Hidden Markov Model (pair HMM) ^[19]:
   
   
   where is the initial probability of starting in state , is the transition probability from to and is the omission probability for either a single letter or aligner residue pair in the state .
3. CONTRAlign (pair CRF) model ^[26]:
   
   
   where is a parameter vector and is a vector of features that indicates the number of times each parameter appears, denotes the set of all possible alignments of and . We do not describe the feature vectors and refer readers to the original paper ^[26].

Remark 2Strictly speaking, the alignment space in the pair hidden Markov model and the CONTRAlign model consider the patterns of gaps. In these cases, we obtain the probability space on by a marginalization.

Probability distributions on

For an RNA sequence , a probability distribution over , which is the space of secondary structures of defined in the previous section is given by the following models.

1. McCaskill model ^[14]: This model is based on the energy models for secondary structures of RNA sequences and is defined by
   
   
   where denotes the energy of the secondary structure that is computed using the energy parameters of Turner Lab ^[27], and are constants and is the normalization term known as the partition function.
2. Stochastic Context free grammars (SCFGs) model ^[28]:
   
   
   where is the joint probability of generating the parse and is given by the product of the transition and emission probabilities of the SCFG model and is all parses of , is all parses for a given .
3. CONTRAfold (CRFs; conditional random fields) model ^[5]: This model gives us the best performance on secondary structure prediction although it is not based on the energy model.
   
   
   where , is the feature vector for in parse , is all parses of , is all parses for a given .

Probability distributions on

A probability distribution on is given by probabilistic models of phylogenetic trees, for example, ^[29], ^{[ 30]}. Those models give a probability distribution on binary trees and we should marginalize these distributions for multi-branch trees.

The pairwise alignment of biological (DNA, RNA, protein) sequences (Problem 1) is another fundamental and important problem of sequence analysis in bioinformatics (cf. ^[31]).

The -centroid estimator for Problem 1 can be introduced as follows:

Estimator 1 ( -centroid estimator for Problem∼:align)For Problem 1, we obtain the -centroid estimator where the predictive space is equal to and the probability distribution on is taken by .

First, Theorem 2 and the definition of lead to the following property.

Property 1 (A relation of Estimator 1 with accuracy measures)The -centroid estimator for Problem 1 is suitable for the accuracy measures: SEN, PPV, MCC and F-score with respect to the aligned-bases in the predicted alignment.

Note that accurate prediction of aligned-bases is important for the analysis of alignments, for example, in phylogenetic analysis. Therefore, the measures in above are often used in evaluations of alignments e.g. ^[4].

The marginalized probability is called the aligned-base (matching) probability in this paper. The aligned-base probability matrix can be computed by the forward-backward algorithm whose time complexity is equal to ^[31]. Now, Theorem 3 leads to the following property.

Property 2 (Computation of Estimator 1)The pairwise alignment of Estimator 1 is found by maximizing the sum of aligned-base probabilities (of the aligned-bases in the predicted alignment) that are larger than . Therefore, it can be computed by a Needleman-Wunsch-style dynamic programming (DP) algorithm ^[32] after calculating the aligned-base matrix :

(19) 

The time complexity of the recursion of the DP algorithm in Eq. (19) is equal to , so the total computational cost for predicting the secondary structure of the -centroid estimator remains .

By using Corollary 1, we can predict the pairwise alignment of Estimator 1 with without using the DP algorithm in Eq. (19).

Property 3 (Computation of Estimator 1 with ) The pairwise alignment of the -centroid estimator can be predicted by collecting the aligned-bases whose probabilities are larger than .

The genome alignment software called LAST (http://last.cbrc.jp/) ^[4], ^{[ 33]} employs the -centroid estimator accelerated by an X-drop algorithm, and the authors indicated that Estimator 1 reduced the false-positive aligned-bases, compared to the conventional alignment (maximum score estimator).

Relations of Estimator 1 with existing estimators are summarized as follows:

1. A relation with the estimator by Miyazawa ^[13] (i.e. the centroid estimator): Estimator 1 where and the Miyazawa model is equivalent to the centroid estimator proposed by Miyazawa ^[13].
2. A relation with the estimator by Holmes et al.^[34]: Estimator 1 with sufficiently large is equivalent to the estimator proposed by Holmes et al., which maximizes the sum of matching probabilities in the predicted alignment.
3. A relation with the estimator in ProbCons: In the program, ProbCons, Estimator 1 with pair HMM model and the sufficient large was used. This means that ProbCons only take care the sensitivity (or SPS) for the predicted alignment.
4. A relation with the estimator by Schwartz et al.: For Problem 1, Schwartz et al.^[21] proposed an Alignment Metric Accuracy (AMA) estimator, which is similar to the -centroid estimator (see also ^[3]). The AMA estimator is a maximum gain estimator (Definition 3) with the following gain function.
   
   
   for . In the above equation, is a gap factor, which is a weight for the prediction of gaps. We refer to the function as the gain function of the AMA estimator. In a similar way to that described in the previous section, we obtain a relation between and (the gain function of the -centroid estimator). If we set , then we obtain
   
   (20) 
   where
   
   
   and is a value which does not depend on . If for , then we obtain and , and this means that is an aligned pair that is a false negative and is an aligned pair that is a false positive when is a reference alignment and is a predicted alignment. Therefore, the terms (in Eq. (20)) in the gain function of AMA are not appropriate for the evaluation measures SEN, PPV, MCC and F-score for aligned bases. In summary, the -centroid estimator is suitable for the evaluation measures: SEN, PPV and F-score with respect to the aligned-bases while the AMA estimator is suitable for the AMA.

Secondary structure prediction of an RNA sequence (Problem 2) is one of the most important problems of sequence analysis in bioinformatics. Its importance has increased due to the recent discovery of functional non-coding RNAs (ncRNAs) because the functions of ncRNAs are closely related to their secondary structures ^[35].

-centroid estimator for Problem 2 can be introduced as follows:

Estimator 2 ( -centroid estimator for Problem 2)For Problem 2, we obtain the -centroid estimator (Definition 7) where the predictive space is equal to and the probability distribution on is taken by .

The general theory of the -centroid estimator leads to several properties. First, the following property is derived from Theorem 2 and the definition of .

Property 4 (A relation of Estimator 2 with accuracy measures)The -centroid estimator for Problem 2 is suitable for the widely-used accuracy measures of the RNA secondary structure prediction: SEN, PPV and MCC with respect to base-pairs in the predicted secondary structure.

Because the base-pairs in a secondary structure are biologically important, SEN, PPV and MCC with respect to base-pairs are widely used in evaluations of RNA secondary structure prediction, for example, ^[5], ^{[ 12]}, ^{[ 36]}.

The marginalized probability is called a base-pairing probability. The base-paring probability matrix can be computed by the Inside-Outside algorithm whose time complexity is equal to where is the length of RNA sequence ^[14], ^{[ 31]}. Then, Theorem 3 leads to the following property.

Property 5 (Computation of Estimator 2)The secondary structure of Estimator 2 is found by maximizing the sum of the base-pairing probabilities (of the base-pairs in the predicted structure) that are larger than . Therefore, it can be computed by a Nussinov-style dynamic programming (DP) algorithm ^[37] after calculating the base-pairing probability matrix :

(21) 

If we replace “ ” with “ ” in Eq. (21), the DP algorithm is equivalent to the Nussinov algorithm ^[37] that maximizes the number of base-pairs in a predicted secondary structure. The time complexity of the recursion of the DP algorithm in Eq. (21) is equal to . Hence, the total computational cost for predicting the secondary structure of the -centroid estimator remains , which is the same time complexity as for standard software: Mfold ^[38], RNAFOLD^[39] and RNASTRUCTURE^[40].

By using Corollary 1, we can predict the secondary structure of Estimator 2 with without using the DP algorithm in Eq. (21).

Property 6 (Computation of Estimator 2 with )The secondary structure of the -centroid estimator with can be predicted by collecting the base-pairs whose probabilities are larger than .

The software CENTROIDFOLD^[12], ^{[ 15]} implements Estimator 2 with various probability distributions for the secondary structures, such as the CONTRAFOLD and McCASKILL models.

Relations of Estimator 2 with other estimators are summarized as follows:

1. A relation with the estimator used in SFOLD^[41], ^{[ 42]}: Estimator 2 with and the McCaskill model (i.e. the centroid estimator with the McCaskill model) is equivalent to the estimator used in the SFOLD program.
2. A relation with the estimator used in CONTRAFOLD: For Problem 2, Do et al.^[5] proposed an MEA-based estimator, which is similar to the -centroid estimator. (The MEA-based estimator was also used in a recent paper ^[6].) The MEA-based estimator is defined by the maximum expected gain estimator (Definition 3) with the following gain function for and .
   
   (22) 
   where and are symmetric extensions of (upper triangular matrices) and , respectively (i.e. for and for ; the definition of is similar.). It should be noted that, under the general estimation problem of Problem 3, the gain function of Eq. (22) cannot be introduced, and the gain function is specialized for the problem of RNA secondary structure prediction. The relation between the gain function of the -centroid estimator (denoted by and defined in Definition 7) and the one of the MEA-based estimator is
   
   (23) 
   where the additional term is positive for false predictions of base-pairs (i.e., and ) and does not depend on the prediction (see ^[12] for the proof). This means the MEA-based estimator by Do et al. possess a bias against the widely-used accuracy measures for Problem 2 (SEN, PPV and MCC of base-pairs) compared with the -centroid estimator. Thus, the -centroid estimator is theoretically superior to the MEA-based estimator by Do et al. with respect to those accuracy measures. In computational experiments, the authors confirmed that the -centroid estimator is always better than the MEA-based estimator when we used the same probability distribution of secondary structures. See ^[12] for details of the computational experiments.

The -centroid estimator for Problem 4 can be introduced as follows:

Estimator 3 ( -centroid estimator for Problem 4)For Problem 4, we obtain the -centroid estimator (Definition 7) where the predictive space is equal to and the probability distribution on is taken by .

The following property is easily obtained by Theorem 2 and ^[17].

Property 7 (Relation of 1-centroid estimator and topological distance)The -centroid estimator with (i.e. centroid estimator) for Problem 4 minimizes expected topological distances.

For ( is a set of partitions of and is formally defined in the previous section), we call the marginalized probability partitioning probability. However, it is difficult to compute as efficiently as in the prediction of secondary structures of RNA sequences, where it seems possible to compute the base-pairing probability matrix in polynomial time by using dynamic programming). Instead, a sampling algorithm can be used for estimating approximately ^[16] for this problem. Once is estimated, Theorem 3 leads to the following:

Property 8 (Computaion of Estimator 3)The phylogenetic tree of Estimator 3 is found by maximizing the sum of the partitioning probabilities (of the partitions given by the predicted tree) that are larger than .

In contrast to Estimator 1 (the -centroid estimator for secondary structure prediction of RNA sequence) and Estimator 2 (the -centroid estimator for pairwise alignment), it appears that there is no efficient method (such as dynamic programming algorithms) to computed Estimator 3 with . Estimator 1 with , however, can be computed by using the following property, which is directly proven by Corollary 1 and the definition of the space .

Property 9 (Estimator 3 with )The -centroid estimator with for Problem 4 contains its consensus estimator.

In this section we consider the problem of the alignment between two multiple alignments of biological sequences (Figure 4), which is often important in the multiple alignment of RNA sequences ^[19]. This problem is formulated as follows.

Problem 10 (Alignment between two alignments of biological sequences)The data is represented as where and are alignments of biological sequences and the predictive space is equal to , that is, the space of the alignments of and .

In the following, and denote the length of the alignment and the number of sequences in the alignment , respectively. If both and contain a single biological sequence (with no gap), Problem 10 is equivalent to conventional pairwise alignment of biological sequences (Problem 1). As in common secondary structure prediction, the representative estimator plays an important role in this application.

Estimator 4 (Representative estimator for Problem 10)For Problem 10, we obtain the representative estimator (Definition 10). The gain function is the gain function of the -centroid estimator. The parameter space is represented as a product space where is defined in the previous section. The probability distribution on the parameter space is given by for where is given in the previous section (when or contains some gaps, is defined by the sequences with the gaps removed).

Corollary 2 proves the following properties of Estimator 5.

Property 10 (A Relation of Estimator 4 with accuracy measures)Estimator 4 is consistent with the accuracy process for Problem 10 that is shown in Figure 5. We compare every pairwise alignment of and with the reference alignment. These comparisons are made using TP, TN, FP and FN with respect to the aligned-bases (e.g., using SEN, PPV and F-score).

Property 11 (Computation of Estimator 4)Estimator 4 can be given by maximizing the sum of probabilities that are larger than where

(24) 

Therefore, the pairwise alignment of Estimator 4 can be computed by the Needleman-Wunsch-type DP algorithm of Eq. (19) in which we replace with Eq. (24).

Property 12 (Computation of Estimator 4 with )The Estimator 4 with contains the consensus estimator. Moreover, the consensus estimator is identical to the estimator :

The probability matrix is often called an averaged aligned-base (matching) probability matrix of and . In the iterative refinement of the ProbCons ^[19] algorithm, the existing multiple alignments are randomly partitioned into two groups and those two multiple alignments are re-aligned. This procedure is equivalent to Problem 10.

The estimator used in ProbCons is identical to Estimator 4 in the limit . Therefore, the estimator used in ProbCons is a special case of Estimator 4 and it only takes into account the SEN or SPS (sum-of-pairs score) of a predicted alignment.

Common secondary structure prediction from a given multiple alignment of RNA sequences plays important role in RNA research including non-coding RNA (ncRNA) ^[43] and viral RNAs ^[44], because it is useful for phylogenetic analysis of RNAs ^[45] and gene finding ^[43], ^{[ 46]}–^[48]. In contrast to conventional secondary structure prediction of RNA sequences (Problem 2), the input of common secondary structure prediction is a multiple alignment of RNA sequences and the output is a secondary structure whose length is equal to the length of the input alignment (see Figure 6).

Problem 11 (Common secondary structure prediction)The data is represented as where is a multiple alignment of RNA sequences and the predictive space is identical to (the space of secondary structures whose length is equal to the alignment).

The representative estimator (Definition 10) directly gives an estimator for Problem 11.

Estimator 5 (The representative estimator for Problem 11)For Problem 11, we obtain the representative estimator (Definition 10) as follows. The gain function is the gain function of the -centroid estimator. The parameter space is equal to where is the space of secondary structures. The probability distribution on is given by where is the probability distribution of the secondary structures of after observing the alignment .

For example, can be given by extending the , although we have also proposed more appropriate probability distribution (see ^[49] for the details).

Corollary 2 proves the following properties of Estimator 5.

Property 13 (A relation of Estimator 5 with accuracy measures)Estimator 5 is consistent with an evaluation process for common secondary structure prediction: First, we map the predicted common secondary structure into secondary structures in the multiple alignment, and then the mapped structures are compared with the reference secondary structures based on TP, TN, FP and FN of the base-pairs using, for example, SEN, PPV and MCC (Figure 7).

Much research into common secondary structure prediction employs the evaluation process in Figure 7 (e.g., ^[50]).

Property 14 (Computation of Estimator 5)The common secondary structure of Estimator 5 is given by maximizing the sum of the averaged base-pairing probabilities where

(25) 

Therefore, the common secondary structure of the estimator can be computed using the dynamic programming algorithm in Eq. (10) if we replace with .

Also, we can predict the secondary structure of Estimator 5 without conducting Nussinov-style DP:

Property 15 (Computation of Estimator 5 with )The secondary structure of Estimator 5 with can be predicted by collecting the base-pairs whose averaged base-paring probabilities are larger than .

It should be noted that the tools of common secondary structure prediction, RNAALIFOLD^[50], PETFOLD^[8] and MCCASKILL-MEA ^[7] are also considered as a representative estimators (Definition 10). In ^[49], the authors systematically discuss those points. See ^[49] for details.

As in the previous application to RNA secondary structure prediction using homologous sequences, if we obtain a set of homologous sequences for the target sequences and (see Figure 8), we would have more accurate estimator for the pairwise alignment of and than Estimator 1. The problem is formulated as follows.

Problem 12 (Pairwise alignment using homologous sequences)The data is represented as where and are two biological sequences that we would like to align, and is a set of homologous sequences for and . The predictive space is given by which is the space of the pairwise alignments of two sequences and .

The difference between Problem 1 and this problem is that we can use other biological sequences (that seem to be homologous to and ) besides the two sequences and which are being aligned.

We can introduce the probability distribution (denoted by ) on the space of multiple alignments of three sequences , and (denoted by and whose definition is similar to that of ) by a model such as the triplet HMM (which is similar to the pair HMM). Then, we obtain a probability distribution on the space of pairwise alignments of and (i.e., ) by marginalizing into the space :

(26) 

(27) 

The -centroid estimator with the distribution in Eq. (27) directly gives an estimator for Problem 12. However, to compute the aligned-base-pairs (matching) probabilities with respect to this distribution demands a lot of computational time, so we employ the approximated -type estimator (Definition 12) of this -centroid estimator as follows.

Estimator 6 (Approximated -type estimator for Problem 12)We obtain the approximated -type estimator (Definition 12) for Problem 12 with the following settings. The parameter space is given by where

(28) 

(29) 

Property 16 (Computation of Estimator 6)The alignment of Estimator 6 is equal to the alignment that maximizes the sum of larger than where

(30) 

Therefore, the recursive equation of the dynamic program to calculate the alignment of Estimator 6 is given by replacing in Eq. (19) with Eq. (30).

Moreover, by using Theorem 1, we have the following proposition, which enables us to compute the proposed estimator for without using (Needleman-Wunsch-type) dynamic programming.

Property 17 (Computation of Estimator 6 for )The pairwise alignment of Estimator 6 with can be predicted by collecting the aligned-bases whose probability in (30) is larger than .

It should be noted that is identical to the probability consistency transformation (PCT) of and ^[19]. In ProbCons ^[19], the pairwise alignment is predicted by the Estimator 6 with sufficiently large . Therefore, the estimator for Problem 12 used in the ProbCons algorithm is a special case of Estimator 6.

If we obtain a set of homologous RNA sequences for the target RNA sequence, we might have a more accurate estimator ^[23] for secondary structure prediction than the -centroid estimator (Estimator 2). This problem is formulated as follows and was considered in ^[23] for the first time (See Figure 9).

Problem 13 (RNA secondary structure prediction using homologous sequences)The data is represented as where is the target RNA sequence for which we would like to make secondary structure predictions and is the set of its homologous sequences. The predictive space is identical to , the space of the secondary structures of an RNA sequence .

The difference between this problem and Problem 2 is that we are able to employ homologous sequence information for predicting the secondary structure of the target RNA sequence. In this problem, it is natural that we assume the target sequence and each homologous sequence share common secondary structures. The common secondary structure is naturally modeled by a structural alignment (that considers not only the alignment between bases but also the alignment between base-pairs), and the probability distribution (denoted by ) on the space of the structural alignments of two RNA sequences and (denoted by ) is given by the Sankoff model ^[51]. By marginalizing the distribution into the space of secondary structures of the target sequence , we obtain more reliable distribution on :

(31) 

(32) 

Estimator 7 (Approximated -type estimator for Problem 13)We obtain the approximated -type estimator (Definition 12) for Problem 13 with the following settings. The parameter space is given by where

It should be noted that Estimator 13 is equivalent to the estimator proposed in ^[23]. The secondary structure of the estimator can be computed by the following method.

Property 18 (Computation of Estimator 7)The secondary structure of Estimator 7 is computed by maximizing the sum of larger than where

(33) 

Here, and . Therefore, the secondary structure of Estimator 7 can be computed by the Nussinov-type DP of Eq. (10) in which we replace by Eq. (33).

The computational cost with respect to time for computing the secondary structure of Estimator 7 is where is the number of RNA sequences and is the length of RNA sequences. In ^[23], we employed a further approximation of the estimator, and reduced the computational cost to . We implemented this estimator in software called CENTROIDHOMFOLD. See ^[23] for details of the theory and results of computational experiments. Although the authors did not mention it in their paper ^[23], the following property holds.

Property 19 (Computation of Estimator 7 with )Estimator 7 with can be predicted by collecting the aligned-bases where the (pseudo-)base-paring probability of Eq. (33) is larger than .

In this section, we focus on the pairwise alignment of structured RNAs. This problem is formulated as Problem 1, so the output of the problem is a usual alignment (contained in ). In contrast to the usual alignment problem, we can consider not only nucleotide sequences but also secondary structures in each sequence for the problem. Note that this does not mean the structural alignment ^[51] of RNA sequences, because the structural alignment produces both alignment and the common secondary structure simultaneously.

The probability distributions on described in the previous section are not able to handle secondary structures of each RNA sequence. In order to obtain a probability distribution on that considers secondary structure, we employ the marginalization of the Sankoff model ^[51] that gives a probability distribution (denoted by ) on the space of possible structural alignments between two RNA sequences (denoted by ). In other words, we obtain a probability distribution on the space by marginalizing the probability distribution of structural alignments of two RNA sequences (given by the Sankoff model) into the space as follows.

(34) 

Then, the -centroid estimator with this distribution Eq. (34) will give a reasonable estimator for the pairwise alignment of two RNA sequences. However, the computation of this estimator demands huge computational cost because it uses the Sankoff model (cf. it requires time for computing the matching probability matrix of structural alignments). Therefore, we employed the approximated -type estimator (Definition 12) of the -centroid estimator with the marginalized distribution as follows.

Estimator 8 (Approximated -type estimator for Problem 1 with two RNA sequences)In Problem 1 where and are RNA sequences, we obtain the approximated -type estimator (Estimator 2) with the following settings. The parameter space is given by where

This approximated -type estimator is equivalent to the estimator proposed in ^[52] and the alignment of the estimator can be computed by the following property.

Property 20 (Computation of Estimator 8)The alignment of Estimator 8 can be computed by maximizing the sum of probabilities that are larger than where

(35) 

Here, we define

Therefore, the pairwise alignment of Estimator 8 can be computed by a Needleman-Wunsch-type dynamic program of Eq. (19) in which we replace with Eq. (35).

Note that in Eq. (35) is considered as a pseudo-aligned base probability where aligns with .

By checking Eq. (14), we obtain the following property:

Property 21 (Computation of Estimator 8 with )The pairwise alignment of Estimator 8 can be predicted by collecting aligned-bases where the probability in Eq. (35) is larger than .

We will prove a more general case of Theorem 1 where the parameter space is different from the predictive space and a probability distribution on is assumed (cf. Assumption 2).

Theorem 4In Problem 3 with Assumption 1 and a pointwise gain function, suppose that a predictive space can be written as

(36) 

(37) 

(proof)It is sufficient to show that the consensus estimator is contained in the predictive space because for all in the MEG estimators, where

If we assume that is not contained in the predictive space, that is, , then there exists a such that . Because is a binary vector, there exist indexes such that , and . By the definition of , we obtain

Therefore, we obtain

In order to prove the last inequality, we use Eq. (??). This leads to a contradiction and the theorem is proved.

Remark 3It should be noted that the above theorem holds for an arbitrary parameter space including continuous-valued spaces.

Proof of Theorem 2. (proof)Because for arbitrary , we obtain, using the definitions given in equations (15),(16),(17) and (18),

Therefore, we have

Proof of Theorem 3. (proof)The expectation of the gain function of the -centroid estimator is computed as

Proof of Corollary 1. (proof)For every , , , , we have

The last half of the corollary is easily proved using the equation

Proof of Proposition 1. (proof) 5The representative estimator in Definition 10 can be written as

Then, we finish the proof of Proposition 1.

The equation is easily derived from the equality .

The top row includes problems about RNA secondary structure predictions and the middle row includes problems about alignment of biological sequences. Note that the estimators in the same column corresponds to each other.