Experiments and Results - Protein Homology Detection Through Alignment of Markov Random Fields - page 46

Fig. 4.1 Running time of the Viterbi algorithm and MRFalign (which uses the ADMM
algorithm). The X-axis is the geometric mean of the lengths of two proteins under alignment. The
Y-axis is the running time in seconds

PDB25 to find the best match. Since PDB25 does not contain proteins very similar

to many of the test targets, we built a 3D model using MODELLER from the
alignment between a test target and its best match and then measure the quality of
the model. As shown in Fig. 4.2 , MRFalign yields much better 3D models than
HHsearch for most of the targets. This implies that MRFalign can generalize well to
the test data not similar to the training data.
In the second experiment, we divide the proteins in SCOP40 into three subsets
according their similarity with all the training data. We measure the similarity of
one test protein with all the training data by its best BLAST E-value. We used two
values 1e 35 as the E-value cutoff so that the three subsets have roughly

the same size. As shown in Table 4.17 , the advantage of MRFalign in remote
homology detection over HHpred is roughly same across the three subsets. Since
HHpred is an unsupervised algorithm, this implies that the performance of MRF-
align is not correlated to the similarity between the test and the training data.
Therefore, it is unlikely that MRFalign is over

2 and 1e

− −

it by the training data.