2.3.4 Homologuous Core Structure Structural similarity among proteins can provide valuable insights into their functionality. One way to provide structural similarities is through three-dimensional alignment of proteins, also called *structural alignment*. The goal is to align two or more proteins by trying to overlap the three-dimensional coordinates of their atoms. When multiple homologue proteins are structurally aligned, we tend to observe that there is a subset of coordinates whose spatial locations are better conserved across structural alignment. This subset is called the homolog core structure (HCS) (Matsuo *et al*., 1999). According to the result reported by Gerstein *et al*. (1995), HCS can be utilized to detect homologue proteins.

Our goal was to estimate the HCS of a set of protein. As a first approximation, we propose a method to extract it from structural alignment by calculating how much aligned residues from different proteins tend to be close together. Following MAMMOTH, we represent residues through the coordinates of their C-α atoms. In other words, we assume that closeness between C-α atoms will approximate overlapping among amino-acids. To find out how much amino-acids are close together, we utilize the Euclidian distance measure, as shown in the equation 8. It represents the shortest distance between two points in the space.

$$d e_{a,b}={\sqrt{(x_{a}-x_{b})^{2}+(y_{a}-y_{b})^{2}+(z_{a}-z_{b})^{2}}}$$
2 (8)
The degree of overlap between aligned residues in the structural alignment was calculated through the relative distance dij , equation 9. This distance can be found through the average distance among the amino-acid in the position ij and other amino-acids in the j column of alignment.

$$d i_{j}={\frac{\sum_{b=j}^{n-1}d e_{(i,b),(i,b+1)}}{n-1}}$$

Finally, the relative distance was normalized according to 10, and it was used to determine the degree of overlap of each residue. These measures were normalized by using the equation 10, where dmin is the minimal distance and Omaxi is the maximal Ooi measure for protein i.

$$m_{i j}={\frac{d_{m i n}*O_{m a x_{i}}}{d i_{j}}}$$

After this step, we built the Ms matrix, where each mij matrix element corresponds to the relative distance of amino-acids ij in the structural alignment. This matrix represents structural weights that were used to build the model *pHMM3D*, shown in the figure 1.

## 2.4 Library Of Structural Models

In a second step, we join the models built from these matrices to form a library of structural models aiming at building a single model to represent the structural patterns under different aspects. We used the hmmpfam HMMER tool to combine the models together. Library of models have been used in a number of studies, such as (Bateman *et al*., 2004; Haft *et al*., 2003; Gough *et al*., 2001), and they are known to achieve better results than those achieved by single models.

## 2.5 Test Procedure

The main concern of our study is to build pHMMs that can be helpful in remote homology detection. Therefore, our experiments considered proteins with identity below 30%. To do so, we used the SCOP database
(Andreeva *et al*., 2004), and more specifically ASTRAL SCOP version 1.67 PDB40 (with 6600 protein sequences). ASTRAL SCOP is particularly interesting for our study because it describes structural and evolutionary relationships among proteins, such that none of the sequences in ASTRAL
SCOP present > 40% sequence identity. Thus, it is an excellent dataset to evaluate the performance of remote homology detection methods and has been widely used to reach this goal (Espadaler *et al*., 2005; Wistrand *et al*.,
2005; Hou *et al*., 2004; Alexandrov *et al*., 2004).

SCOP classifies all protein domains of known structure into a hierarchy with four levels: class, fold, super family and family. In our study, we work at the super family level, which gathers families in such a way that a common evolutionary origin is not obvious from sequence identity, but probable from an analysis of structure and from functional features. We believe that this level better represents remote homolog.

Moreover, we used cross-validation (Mitchell, 1997) to compare the different approaches. First, we divided SCOP database by super family level.

Next, from ASTRAL PDB40, we chose those super families containing at least three families and at least 20 sequences. We eventually tested 39 super families, as listed in Table 1. This whittled down the number of sequences we used to model building to 1137. Third, we implemented leave-one-familyout cross-validation. For any super family x having n families, we built n profiles so that each profile P was built from the sequences in the remaining n − 1 families. Thus, the n − 1 sequences form the training set for profile P. The test set for profile P will be the remaining sequences (test positives)
plus all other database sequences (test negatives).

Table 1. Superfamily SCOP-Ids

| a.1.1.   | a.138.1.   | a.25.1.   | a.26.1.   | a.3.1.   | a.39.1.   | a.4.1.   | b.121.4.   |
|----------|------------|-----------|-----------|----------|-----------|----------|------------|
| b.18.1.  | b.29.1.    | b.36.1.   | b.47.1.   | b.55.1.  | b.60.1.   | b.6.1.   | b.71.1.    |
| b.82.1.  | c.1.10.    | c.23.1.   | c.26.1.   | c.36.1.  | c.52.1.   | c.55.1.  | c.55.3.    |
| c.67.1.  | d.108.1.   | d.14.1.   | d.144.1.  | d.15.1.  | d.153.1.  | d.169.1. | d.3.1.     |
| d.58.7.  | d.92.1.    | g.3.11.   | g.3.6.    | g.3.7.   | g.37.1.   | g.39.1.  |            |

SCOP Super families used in our experiments. We only considered super families with at least 20 proteins and three or more families.

$$10$$

In order to assess HMMER-STRUCT performance, we used the HMMER
package. We did not compare with SAM (Hughey *et al*., 1996) package.

First, because our goal was to evaluate whether structural properties can improve pHMMs, not to compare the two packages, and second, because a related previous study on the same dataset actually showed HMMER outperforming SAM (Bernardes *et al*., 2007). The same study also indicated better results on the "twilight zone" using structural alignment tools, such as MAMMOTH-mult and 3DCOFFEE. We used MAMMOTH in this study.

Results were graphically analyzed by building ROC and Precision/Recall curves. ROC curves are a common measure of performance that is very used in bioinformatics application. They are based on the relation of the false positives (non homologue proteins) and of true positives (homologue proteins),
and are obtained by varying a parameter that affect these relationships. We further present Precision/Recall curves, as they give a good perspective on true positives, false positives and false negatives hits. In both cases, the bigger the area under the curve (AUC), the more efficient the analyzed tool is.

In both cases we used the minimal *e-value* required to accept a match as the parameter used to build both curves. We ranged e-values between 10−50 and 10. Finally, we used the paired two tailed t-test to assess significance, and assumed that results with p ≤ 0.05 (I.e. 95% of confidence) are significant.

## 3 Results

As a first step, we build a model for each structural property and evaluate it according to the methodology described in the Methods section. The ROC curves are presented in figure 4 and the Precision/Recall curves in figure 5. Both figures show all models, that is, *pHMM2D* (secondary structural model), *pHMMOi* (Ooi measure model), *pHMMAcc* (inaccessibility model) and *pHMM3D* (threedimensional structure model) outperforming the HMMER model.