Protein Structure and Function: Applications of Bioinformatics Methods - John Rigden 2014

Fold Recognition
Remote Homology Detection Without Alignment
Classification of Fold Types and the Support Vector Machine Method

Structure/29.html">Fold Recognition is a Classification problem. It can be viewed as a series of questions regarding whether a sequence under consideration folds into one or another structural type among their wide variety. This can be solved using machine learning Methods. If The properties of the studied sequence S are known—such as its Amino Acid Composition, related sequences, predicted Secondary structure, and the like—one can determine the most probable fold type possessing the properties s from a given set of fold types F. Such classifiers can be roughly divided into generative and discriminative. A typical generative classifier is the naive Bayes classifier. The core idea is to determine the relative importance of each feature (model parameters) for predicting the fold type by analyzing the frequencies with which these features occur in elements of a given Class within a specific training set.

As an example of using the naive Bayes classifier, let us consider the operation of determining the most probable value of F_nb given The values of s₁, s₂, ... s_n. As a result, we obtain:

In the general case, P(s_i\f_j) can be estimated using the formula:

where:

n is the number of training Examples for which f = f_j;

n_с is the number of examples for which f = f_j and s = s_j;

р is the prior estimate for P(s_i/f_j);

m is the equivalent Sample size (weight term for the prior estimate).

There is a marked similarity between this approach and the methods described above that are used to define Energy Functions.

Unlike generative classifiers, where probabilities are determined using training examples, discriminative classifiers attempt to achieve maximum predictive accuracy directly on the training set. Neural networks and support vector machines are discriminative classifiers widely used in computational biology (see, e.g., Busuttil et al. 2004; Garg et al. 2005; Nguyen and Rajapakse 2003; Bradford and Westhead 2005).

The Use of support vector machines (SVM) makes it possible to define a decision boundary, or hyperplane, that separates input data into two classes (e.g., fold type A and non-A fold type) based on the feature vector value s. In the most complex cases, the data cannot be separated using a linear function of the input features. In the support vector machine method, the non-linearity problem is solved using a kernel function k(s_i, s_j), which evaluates the degree of similarity between pairs of input examples s_i, s_j. During training, each example—both positive and negative—is compared with other examples of the considered set using the kernel function, which generates an n x n similarity matrix, where n is the number of training examples. The trick is that by using a kernel function—typically computationally simple and fast—data can be projected into a higher-dimensional feature space where they can then be linearly separated. The decision boundary defined in this way usually includes only a small number of training examples that lie directly on the decision boundary, known as support vectors due to their ability to “support” the boundary, much like struts support a structure.

The support vector machine method is used to detect remote Homology, including in such approaches as SVM-Fisher (Jaakkola et al. 2000), SVM-k-spectrum (Leslie et al. 2002), SVM-pairwise (Liao and Noble 2003), SVM I-sites (Hou et al. 2003), and SVM-mismatch (Leslie et al. 2004).

All these techniques are, in a sense, methods of “pure” recognition, since modeling does not generate a final alignment. Instead, the membership of the studied sequence in a particular class is determined with a certain probability. While this can be useful in some cases, researchers often aim to obtain a spatial model of the sequence under investigation, and therefore an additional system is required to perform the (non-trivial) alignment stage.