The problem studied here can be stated formally as follows: Given are an unlabeled protein sequence S and a known superfamily ; we want to determine whether or not S belongs to . (We refer to as the target class and the set of sequences not in as the nontarget class.) In general, a superfamily is a group of proteins that share similarity in structure and function. If the unlabeled sequence S is determined to belong to , then one can infer the structure and function of S. This process is important in many aspects of bioinformatics and computational biology.^7-9 For example, in drug discovery, if sequence S is obtained from some disease X and it is determined that S belongs to the superfamily , then one may try a combination of the existing drugs for to treat the disease X.

There are several approaches available for protein sequence classification. One approach is to compare the unlabeled sequence S with the sequences in the target class and the sequences in the nontarget class using an alignment tool such as BLAST.¹⁰ One then assigns S to the class containing the sequence best matching S.

The second method for protein sequence classification is based on hidden Markov models (HMMs).¹¹ The HMM method (e.g., SAM¹² and HMMer¹³) employs a machine-learning algorithm, which uses probabilistic graphical models to describe time-series and sequence data. It was originally applied to speech recognition,¹⁴ and now is also applied to modeling and analyzing protein superfamilies. It is a generalization of the position-specific scoring matrix to include insertion and deletion states. Often, an HMM is built for each (super)family. One then scores the unlabeled sequence S with respect to the HMM of a (super)family.¹⁵ If the score is more significant than a cut-off value, then S is regarded as a member of the (super)family.

Another approach for protein sequence classification is to iteratively build a model either based on hidden Markov models (e.g., SAM-T99¹⁶) or based on a position-specific weight matrix (e.g., PSI-BLAST¹⁰). The unlabeled sequence S is used as a seed sequence and iteratively searched against the (super)family either by the HMM or by the position-specific weight matrix.

In the study presented here, we compare our approach with BLAST, SAM, and the iterative method using SAM-T99. With hidden Markov models, we choose SAM rather than HMMer because the former outperforms the latter in protein sequence classification.¹⁷ With iterative methods, we choose SAM-T99 rather than PSI-BLAST because the former is more sensitive than the latter in homolog detection.⁷ We choose BLAST as a point of comparison because it represents a different computing paradigm, namely performing classification simply via alignment. One interesting finding from our work is that the compared classification methods complement each other; combining them yields higher precision than using them individually, as our experimental results will show later. This is consistent with a previous report¹⁸ in which we gave a preliminary analysis of the complementarity among our approach, BLAST, and SAM.

Feature extraction from protein data

From a one-dimensional point of view, a protein sequence contains characters from the 20-letter amino acid alphabet = {A, C, D, E, F, G, H, I, K, L, M, N, P, Q, R, S, T, V, W, Y}. An important issue in applying neural networks to protein sequence classification is how to encode protein sequences, i.e., how to represent the protein sequences as the input of the neural networks. Indeed, sequences may not be the best representation at all. Good input representations make it easier for the neural networks to recognize underlying regularities. Thus, good input representations are crucial to the success of neural network learning.¹⁹

We propose here new encoding techniques that entail the extraction of high-level features from protein sequences. The best high-level features should be “relevant.” By relevant we mean that there should be high mutual information between the features and the output of the neural networks, where the mutual information measures the average reduction in uncertainty about the output of the neural networks given the values of the features.

Another way to look at these features is that they capture both the global similarity and the local similarity of protein sequences. The global similarity refers to the overall similarity among multiple sequences, whereas the local similarity refers to motifs (or frequently occurring substrings) in the sequences. The next two sections elaborate on how to find the global and local similarity of the protein sequences. The third section presents our classification algorithm, which employs the Bayesian neural network originated from Mackay.²⁰ The last three sections evaluate the performance of the proposed classifier, compare our approach with the other protein classifiers, and conclude the paper.

Global similarity of protein sequences

To calculate the global similarity of protein sequences, we adopt the 2-gram, also known as 2-tuple, method as described in Wu.²¹ The 2-gram encoding method extracts various patterns of two consecutive amino acid residues in a protein sequence and counts the number of occurrences of the extracted residue pairs.²² For instance, given a protein sequence PVKTNVK, the 2-gram amino acid encoding method gives the following result: 1 for PV (indicating PV occurs once), 2 for VK (indicating VK occurs twice), 1 for VK, 1 for TN, and 1 for NV.

We also adopt the 6-letter exchange group {e₁, e₂, e₃, e₄, e₅, e₆} to represent a protein sequence,²³ where e₁ {H, R, K}, e₂ {D, E, N, Q}, e₃ {C}, e₄ {S, T, P, A, G}, e₅ {M, I, L, V}, and e₆ {F, Y, W}. Exchange groups represent conservative replacements through evolution. These exchange groups are effectively equivalence classes of amino acids and are derived from PAM.^24,25 For example, the above protein sequence PVKTNVK can be represented as e₄e₅e₁e₄e₂e₅e₁. The 2-gram exchange group encoding for this sequence is: 1 for e₄e₅, 2 for e₅e₁, 1 for e₁e₄, 1 for e₄e₂, and 1 for e₂e₅.

For each protein sequence, we apply both the 2-gram amino acid encoding and the 2-gram exchange group encoding to the sequence. Thus, there are 20² + 6² = 436 possible 2-grams in total. If all the 436 2-grams are chosen as the neural network input features, it would require many weight parameters and training data. This makes it difficult to train the neural network—a phenomenon called “curse of dimensionality.” Different methods have been proposed to solve the problem by careful feature selection and by scaling of the input dimensionality.^23,26 We propose here to select relevant features (i.e., 2-grams) by employing a distance measure to calculate the relevance of each feature.²⁷

Let X be a feature and let x be its value. Let P(x|Class = 1) and P(x|Class = 0) denote the class conditional density functions for feature X, where Class_1 represents the target class and Class_0 is the nontarget class. Let D(X) denote the distance function between P(x|Class = 1) and P(x|Class = 0), defined as²⁸

D(X) = < x|Class = 1) – P(x|Class = 0)|dx

(1)

The distance measure prefers feature X to feature Y if D(X) > D(Y). Intuitively, this means it is easier to distinguish between Class_1 and Class_0 by observing feature X than feature Y. That is, X appears often in Class_1 and seldom in Class_0 or vice versa. In our work, each feature X is a 2-gram. Let c denote the occurrence number of the feature X in a sequence S. Let l denote the total number of 2-grams in S and let len(S) represent the length of S. We have l = len(S) – 1. Define the feature value x for the 2-gram X with respect to the sequence S as

x =	c	(2)
	len(S) – 1

For example, suppose S = PVKTNVK. Then the value of the feature VK with respect to S is 2/(7 – 1) = 0.33.

Because a protein sequence may be short, random pairings can have a large effect on the result. We approximate D(X) in Equation 1 by²⁹

D(X) =	(m1 – m0)2	(3)
	d12 + d02

where m₁ and d₁ (m₀ and d₀, respectively) are the mean value and the standard deviation of the feature X in the positive (negative, respectively) training data set. Intuitively, in Equation 3, the larger the numerator is (or the smaller the denominator is), the larger the interclass distance is, and therefore the easier to separate Class_1 from Class_0 (and vice versa).

The mean value m and the standard deviation d of the feature X in a set of sequences are defined as

m =	1	N	xi	(4)
	N
		i=1

(5)

where x_i is the value of the feature X with respect to sequence S_i , and N is the total number of sequences in .

Let X₁, X₂, … , X_Ng, N_g 436, be the top N_g features (2-grams) with the largest D(X) values.³⁰ Intuitively, these N_g features occur more frequently in the positive training data set and less frequently in the negative training data set. For each protein sequence S (whether it is a training or an unlabeled test sequence), we examine the N_g features in S, calculate their values as defined in Equation 2, and use the N_g feature values as input feature values to the Bayesian neural network for the sequence S.

To compensate for the possible loss of information due to ignoring the other 2-grams, a linear correlation coefficient (LCC) between the values of the 436 2-grams with respect to the protein sequence S and the mean value of the 436 2-grams in the positive training data set is calculated and used as another input feature value for S. Specifically, the LCC of S is defined as:

LCC(S) =

(6)

where is the mean value of the jth 2-gram, 1 j 436, in the positive training data set, and x_j is the feature value of the jth 2-gram with respect to S as defined in Equation 2.

Local similarity of protein sequences

In contrast to the 2-grams that occur from the beginning to the end of a sequence (thus referred to as global similarities), the local similarity of protein sequences refers to frequently occurring motifs, where a motif is composed of substrings occurring in local regions of a sequence. Let _p = {S₁, … , S_k} be the positive training data set. We use a previously developed sequence mining tool Sdiscover^31,32 to find the regular expression motifs of the forms *X* and *X * Y* where each motif has length Len and approximately matches, within Mut mutations, at least Occur sequences in _p. Here, a mutation could be a mismatch, an insertion, or a deletion of a letter (residue); Len, Mut, and Occur are user-specified parameters. X and Y are segments of a sequence, i.e., substrings made up of consecutive letters, and * is a variable length “don't care” (VLDC) symbol. The length of a motif is the number of the non-VLDC letters in the motif. When matching a motif with a sequence S_i, a VLDC symbol in the motif is instantiated into an arbitrary number of residues in S_i at no cost. For example, when matching a motif *VLHGKKVL* with a sequence MNVLAHGKKVLKWK, the first * is instantiated into MN and the second * is instantiated into KWK. The number of mutations between the motif and the sequence is 1, representing the cost of inserting an A in the motif.

The Sdiscover tool is based on a heuristic that works by taking a small sample of sequences from the given set of sequences _p and storing them in a generalized suffix tree (GST).³³ The GST can be constructed asymptotically in O(n) time and space³⁴ where n is the total length of all sequences in the sample. The heuristic then traverses the GST to generate candidate regular expression motifs and compares these candidate motifs with all the sequences in _p to calculate their occurrence numbers. Given a candidate motif M and a sequence S in _p, one can determine whether M is within Mut mutations of S in O(Mut × |S|) time when O(|M|) = O(log |S|).³⁵ Thus Sdiscover can find all the motifs satisfying user-specified parameter values in time O(n × Mut × m × k), where n is the total length of all sequences in the sample , m is the average length of the sequences in _p, and k is the total number of sequences in _p, although the tool is practically much faster due to several optimization heuristics implemented for speeding up the traversal of the GST.

Often, the number of motifs returned by Sdiscover is enormous. It is useful to develop a measure to evaluate the significance of these motifs. We propose here to use the minimum description length (MDL) principle^8,36,37 to calculate the significance of a motif. The MDL principle states that the best model (a motif in our case) is the one that minimizes the sum of the length, in bits, of the description of the model and the length, in bits, of the description of the data (the positive training sequences in _p in our case) encoded by the model.

Evaluating the significance of motifs. We adopt information theory in its fundamental form^36,38 to measure the significance of different motifs. The theory takes into account the probability of an amino acid in a motif (or sequence) when calculating the description length of the motif (or sequence). Specifically, Shannon³⁸ showed that the length in bits to transmit a symbol b via a channel in some optimal coding is –log₂ P_x(b), where P_x(b) is the probability with which the symbol b occurs. Given the probability distribution P_x over an alphabet _x = {b₁, b₂, … , b_n}, we can calculate the description length of any string b_k1b_k2 … b_kl over the alphabet _x by

–	l	log2 Px(bki)	(7)
	i=1

In our case, the alphabet _x is the protein alphabet containing 20 amino acids. The probability distribution P_x, or P in our case, can be calculated by examining the occurrence frequencies of amino acids in the positive training data set _p. One straightforward way to describe (or encode) the sequences in _p, referred to as Scheme 1, is to encode sequence by sequence, separated by a delimiter $. Let dlen(S_i) denote the description length of sequence S_{i p}. Then

dlen(Si) = –	20	naj log2 P(aj)	(8)
	j=1

where a_j , 1 j 20; n_aj is the number of occurrences of a_j in S_i. For example, suppose S_i = MNVLAHGKKVLKWK is a sequence in _p. Then

dlen(Si) = –

(log2 P(M) + log2 P(N) + 2 log2 P(V) + 2 log2 P(L) + log2 P(A) + log2 P(H) + log2 P(G) + 4 log2 P(K) + log2 P(W)

(9)

Let dlen(_p) denote the description length of _p = {S₁, … , S_k}. Then the description length of _p is given by

dlen(p) =	k	dlen(Si) + (k – 1) × dlen($)	(10)
	i=1

Since the description length of the delimiter $, dlen($), is insignificant, we can ignore it and hence

dlen(p) =	k	dlen(Si)	(11)
	i=1

Another method to encode the sequences in _p, referred to as Scheme 2, is to encode a regular expression motif, say M_j, and then encode the sequences in _p based on M_j. Specifically, if a sequence S_{i p} can approximately match M_j, then we encode S_i based on M_j. Otherwise we encode S_i using Scheme 1.³⁹ Let us use an example to illustrate Scheme 2. Consider, for example, M_j = *VLHGKKVL*. We encode M_j as 1, *, V, L, H, G, K, K, V, L, *, $0 where 1 indicates one mutation is allowed in matching M_j with S_i and $0 is a delimiter to signal the end of the motif. Let ₁ denote the alphabet {a₁, a₂, … , a₂₀, *, $0}, where a₁, a₂, … , a₂₀ are the 20 amino acids. Let P₁ denote the probability distribution over the alphabet ₁. P₁($0) can be approximated by the reciprocal of the average length of motifs. P₁(*) = n(P₁($0)), P₁(a_i) = (1 – (n + 1)P₁($0))P(a_i), where n denotes the number of VLDCs in the motif M_j. For a motif of the form *X*, n is 2; for a motif of the form *X * Y*, n is 3.

Given P₁, we can calculate the description length of a motif by substituting the probability distribution P₁ for the probability distribution P_x in Equation 7. Specifically, let M_j = *a_j1a_j2, … , a_jk*. Let dlen(M_j) denote the description length, in bits, of the motif M_j. Then

dlen(Mj) = –		2 log2 P1(*) + log2 P1($0) +	k	log2 P1(aji)		(12)
			i=1

For instance, consider again M_j = *VLHGKKVL*. We have

dlen(Mj) =

– (2 log2 P1(*) + log2 P1($0) + 2 log2 P1(V) + 2 log2 P1(L) + log2 P1(H) + log2 P1(G) + 2 log2 P1(K)

(13)

Sequences that are approximately matched by the motif M_j can be encoded with the aid of the motif. For example, consider again M_j = *VLHGKKVL* and S_i = MNVLAHGKKVLKWK. M_j matches S_i with one mutation, representing the cost of inserting an A in the third position of M_j. The first VLDC symbol is instantiated into MN and the second VLDC symbol is instantiated into KWK. We can thus rewrite S_i as MN • SS_i • KWK where SS_i is VLAHGKKVL and • denotes the concatenation of strings. Therefore we can encode S_i as M, N, $1; 1, (O_I, 3, A); K, W, K, $1. Here $1 is a delimiter, 1 indicates that one mutation occurs when matching M_j with S_i, and (O_I, 3, A) indicates that the mutation is an insertion that adds the letter A to the third position of M_j. In general, the mutation operations involved and their positions can be observed using approximate string matching algorithms.³⁵ The description length of the encoded S_i based on M_j, denoted dlen(S_i, M_j), can be calculated easily as in Equation 12.

Suppose there are h sequences S_p1 … S_ph in the positive training data set _p that can approximately match the motif M_j. The weight (or significance) of M_j, denoted w(M_j), is defined as

w(Mj) =	h	dlen(Spi) –		dlen(Mj) +	h	dlen(Spi, Mj))		(14)
	i=1				i=1

Intuitively, the more sequences in _p approximately matching M_j and the fewer bits we use to encode M_j and to encode those sequences based on M_j, the larger weight M_j has.

Using Sdiscover, one can find a set of regular expression motifs of the forms *X* and *X * Y* from the positive training data set _p where the motifs satisfy the user-specified parameter values Len, Mut, and Occur. We choose the top N_l motifs with the largest weights. Let denote this set of motifs. Suppose a protein sequence S (whether it is a training sequence or an unlabeled test sequence) can approximately match, within Mut mutations, m motifs in . Let these motifs be M₁, … , M_m. The local similarity (LS) value of S, denoted LS(S), is defined as

LS(S) =

max1 i m{w(Mi)} 0

if m 0 otherwise

(15)

This LS value is used as an input feature value of the Bayesian neural network for the sequence S. Note that we use the “max” operator here to maximize discrimination. In general, positive sequences will have large LS values with high probabilities and small LS values with low probabilities. On the other hand, negative sequences will have small LS values with high probabilities and large LS values with low probabilities.

Remark. Essentially, the proposed scheme is to count amino acids in a sequence (or motif). This scheme is not complete in the sense that different sequences may have the same description length when they have the same number of the same amino acids. Also, there may be multiple ways to align a motif M with a sequence S and hence the description length of the encoded sequence S based on M may not be unique. As a consequence, the weight of a motif defined in Equation 14 may not be unique (in which case the proposed heuristic randomly picks one). There are several other approaches for finding motifs of different forms and for calculating their significance values (see, e.g., Wang,⁸ Brazma,³⁶ Califano,⁴⁰ and Hart⁴¹). However, motifs have relatively little effect on PIR sequence classification and a combination of the proposed techniques already yields a very high precision, as our experimental results show in a later section.

The Bayesian neural network classifier

We adopt the Bayesian neural network (BNN) originated from Mackay²⁰ to classify protein sequences.⁴² There are N_g + 2 input features, including N_g 2-grams, the LCC feature, and the LS feature, both previously described. Thus, a protein sequence is represented as a vector of N_g + 2 real numbers. The BNN has one hidden layer containing multiple hidden units. The output layer has one output unit, which is based on the logistic activation function f(a) = 1/(1 + e^–a). The BNN is fully connected between the adjacent layers. Figure 1 illustrates an example BNN model with two hidden units.

Figure 1

Let = {x^(m), t_m}, 1 m N, denote the training data set including both positive and negative training sequences. x^(m) is an input feature vector including the N_g + 2 input feature values, and t_m is the binary (0/1) target value for the output unit. That is, t_m equals 1 if x^(m) represents a protein sequence in the target class, and 0 otherwise.

Let x denote the input feature vector for a protein sequence, which could be a training sequence or a test sequence. Given the architecture A and the weights w of the BNN, the output value y can be uniquely determined from the input vector x. Because of the logistic activation function f(a) of the output unit, the output value y(x; w, A) can be interpreted as P(t = 1|x, w, A), i.e., the probability that x represents a protein sequence in the target class given w, A. The likelihood function of the data given the model is calculated by

P(|w, A) =	N	y tm(1 – y)1–tm = exp (– G(|w, A))	(16)
	m=1

where G(|w, A) is the cross-entropy error function,

G(|w, A) = –	N	tm log(y) + (1 – tm) log (1 – y)	(17)
	m=1

The G(|w, A) is the objective function in a non-Bayesian neural network training process and is minimized. This process assumes all possible weights are equally likely. The weight decay is often used to avoid overfitting on the training data and poor generalization on the test data by adding a term /2 ^q_i=1 w_i² to the objective function, where is the weight decay parameter (hyperparameter), ^q_i=1 w_i² is the sum of the squares of all the weights of the neural network, and q is the number of weights. This objective function is minimized to penalize the neural network with weights of large magnitudes. Thus, it penalizes an over-complex model and favors a simple model. However, there is no precise way to specify the appropriate value of , which is often tuned off line.

In contrast, in the Bayesian neural network, the hyperparameter is interpreted as the parameter of a model and is optimized on line during the Bayesian learning process. We adopt the Bayesian training of neural networks described in Mackay²⁰ to calculate and maximize the evidence of , namely P(|, A). The training process employs an iterative procedure; each iteration involves three levels of inference. Figure 2 illustrates the training process of the BNN.

Figure 2

In classifying an unlabeled test sequence S represented by its input feature vector x, the output of the BNN, P(t = 1|x, w, A), is the probability that S belongs to the target class. If the probability is greater than the decision boundary 0.5, S is assigned to the target class; otherwise S is assigned to the nontarget class. In general, for an unlabeled test sequence S with m amino acids, it takes O(m) time to calculate 2-gram feature values, O(m) time to calculate the LCC feature value, and O(m × n) time to calculate the LS feature value where n is the total length of the motifs chosen, and constant time for calculating the probability P(t = 1|x, w, A). Thus, the time complexity of our approach to classifying the unlabeled test sequence S is O(m × n).

Performance of the BNN classifier

We carried out a series of experiments to evaluate the performance of the proposed BNN classifier on a Pentium** II PC running the LINUX** operating system. The data used in the experiments were obtained from the International Protein Sequence Database,⁴³ release 62, in the Protein Information Resource (PIR) maintained by the National Biomedical Research Foundation (NBRF-PIR) at the Georgetown University Medical Center. This database, accessible at http://pir.georgetown.edu, currently has 172 684 sequences. Table 1 summarizes the data used in the experiments.

Table 1	Data used in the experiments. N is the number of sequences, Lm is the minimal length of the sequences, and Lx is the maximal length of the sequences.

Data Set N Lm Lx Globin 831 115 173 Kinase-related transforming protein 350 151 502 Ras transforming protein 386 106 322 Ribitol dehydrogenase 319 129 335 Negative sequences 1650 100 200

Data. Four positive data sets were considered; they were globin, kinase, ras, and ribitol superfamilies, respectively, in the PIR protein database. The negative data set contained 1650 protein sequences, also taken from the PIR protein database, with lengths ranging from 100 residues to 200 residues; these negative sequences did not belong to any of the four positive superfamilies. Both the positive and negative sequences were randomly divided into training sequences and test sequences, where the size of the training data set equaled the size of the test data set multiplied by an integer r. With the same training data, we tested several BNN models with different numbers of hidden units. When there were two hidden units, the evidence obtained was the largest (see Figure 2), so we fixed the number of hidden units at two. Models with more hidden units would require more training time while achieving roughly the same performance.

Table 2 summarizes the parameters and base values used in the experiments. The measure used to evaluate the performance of the BNN classifier is precision, PR, which is defined as

PR =	NumCorrect	× 100 percent	(18)
	NumTotal

where NumCorrect is the number of test sequences classified correctly and NumTotal is the total number of test sequences. In general, precision is a comprehensive measure in the sense that it considers true positives, false positives, true negatives, false negatives, and unclassified sequences;⁴⁴ it is used here to find the best parameter values of the proposed BNN classifier. A false positive is a nontarget member sequence that was misclassified as a target member sequence. A false negative refers to a sequence in the target class (e.g., the globin superfamily) that was misclassified as a nontarget member. We present the results for the globin superfamily only; the results for the other three superfamilies were similar.

Table 2   Parameters and their base values for the proposed BNN classifier

Parameter Meaning Value Ng Number of 2-grams used by BNN 60 Nl Number of motifs used by BNN 20 Len Length of motifs for Sdiscover 6 Mut Mutation number for Sdiscover 2 Occur Occurrence frequency of motifs for Sdiscover 1/10 r Size ratio 2

Results. In the first experiment, we considered only 2-grams and evaluated their effect on the performance of the proposed BNN classifier. Figure 3 graphs PR as a function of N_g. It can be seen that the performance improves initially as N_g increases. The reason is that the more 2-grams we use, the more precisely we represent the protein sequences. However, when N_g is too large (e.g., > 90), the training data are insufficient and the performance degrades. In general, the larger N_g is, the more input features the BNN classifier has, and thus the larger training data set BNN requires. In our case, there are 561 positive training sequences and 1089 negative training sequences. When N_g > 90, these data become too few to yield reasonably good performance. Figuring out how big the parameter N_g should be requires some tuning. We have not yet worked out a theory for it.

Figure 3

In the second experiment, we considered only motifs found by Sdiscover and studied their effect on the performance of the BNN classifier. In this experiment 1597 motifs were found, with lengths ranging from six residues to 34 residues. Figure 4 graphs PR as a function of N_l. It can be seen that the more motifs one uses, the better performance one achieves. However, that would also require more time in matching a test sequence with the motifs.⁴⁵ We experimented with other parameter values for Len, Mut, and Occur used in Sdiscover. The results did not change as these parameters changed.

Figure 4

Figure 5 compares the effects of the various types of features introduced in the paper. To isolate the effects of these features, we began by using features of only one type and then using their combinations. It can be seen that features generated from global similarities yield better results than those generated from local similarities. This happens because PIR superfamilies are categorized based on the global similarities of sequences. Note also that the best performance is achieved when all the features are used.

Figure 5

Comparison of four protein classifiers

The purpose of this section is to compare the proposed BNN classifier with the BLAST classifier¹⁰ built based on sequence alignment, and with the SAM and SAM-T99 classifiers¹⁶ built based on hidden Markov models. The parameter values for the BNN classifier were as shown in Table 2. Table 3 summarizes the studied tools. The BNN classifier used both 2-grams and regular expression motifs.

Table 3   The bioinformatics tools studied in the paper

Tool Underlying Techniques BNN Bayesian neural networks BLAST Similarity search and pairwise alignment SAM Hidden Markov models SAM-T99 Iterative hidden Markov models

The BLAST version number was 2.0.10. We used default values for the parameters in BLAST. For this tool, we aligned an unlabeled test sequence S with the positive training sequences (i.e., those in the target class, e.g., the globin superfamily) and the negative training sequences in the nontarget class shown in Table 1 using the tool. If the score of S was below the threshold of the expectation (E) value of BLAST, S was undetermined or unclassified. Otherwise, we assigned S to the class containing the sequence best matching S.

The SAM version number was 3.2.1. For this tool, we employed the program buildmodel to build the HMM model by using only the positive training sequences. We then calculated the log-odds scores¹³ for all the training sequences using the program hmmscore.⁴⁶ The log-odds scores were all negative real numbers; the scores (e.g., –100.3) for the positive training sequences were generally smaller than the scores (e.g., –4.5) for the negative training sequences. The largest score S_p for the positive training sequences and the smallest score S_n for the negative training sequences were recorded. Let B_high = max {S_p, S_n} and B_low = min {S_p, S_n}. We then calculated the log-odds scores for all the unlabeled test sequences using the program hmmscore. If the score of an unlabeled test sequence S was smaller than B_low, S was classified as a member of the target class, e.g., a globin sequence. If the score of S was larger than B_high, S was classified as a member of the nontarget class. If the score of S was between B_low and B_high, S was unclassified or undetermined.

The SAM-T99 version number was also 3.2.1. For this tool, we built an HMM (target model) for each unlabeled test sequence S. We then scored all the training sequences using the HMM target model. If the lowest score of the training sequences was higher than the expectation value (E-value) of the HMM target model, the test sequence S was undetermined or unclassified.⁴⁷ Otherwise, we assigned the test sequence to the class containing the training sequence having the lowest E-value. The target model was built in four iterations. In the first iteration, SAM-T99 used BLAST to compare the test sequence S with sequences in the nonredundant protein database maintained at the National Center for Biotechnology Information (NCBI) and chose a set of close homologs to build an initial HMM. It also did a BLAST search of the test sequence S against the nonredundant protein database with a very loose cut-off value to get a pool of potential homologs. Then the HMM obtained from the previous iteration was compared against the pool of potential homologs with a looser cut-off value than that of the previous iteration to find weaker homologs. These weaker homologs were included to build a new HMM for the next iteration. This whole process was repeated three times.

In comparing the relative performance of these tools, we use four more measures in addition to the precision PR defined in the previous section: specificity, sensitivity, unclassified_p, and unclassified_n, where

specificity =		1 –	Nfp		×100 percent	(19)
			Nng

sensitivity =		1 –	Nfn		×100 percent	(20)
			Npo

unclassifiedp =	Nup	×100 percent	(21)
	Npo

unclassifiedn =	Nun	×100 percent	(22)
	Nng

N_fp is the number of false positives, N_fn is the number of false negatives, N_up is the number of undetermined positive test sequences, N_un is the number of undetermined negative test sequences, N_ng is the total number of negative test sequences, and N_po is the total number of positive test sequences. Note that in contrast to PR, specificity and sensitivity do not consider unclassified sequences. That is why we also add the unclassified_p and unclassified_n measures for performance evaluation.

In the first experiment, we studied the effect of the threshold of the E-value in the BLAST classifier. Figure 6 shows the impact of E-values on the performance of BLAST. It can be seen that with E = 10, BLAST performs well. With smaller E-values (e.g., 0.1), the specificity of BLAST can approach 100 percent with very few false positives, whereas the number of unclassified sequences is enormous. Thus, we fixed the threshold of the E-value at 10 in subsequent experiments.

Figure 6

Tables 4, 5, 6, and 7 summarize the results and classification times, in seconds, of the four studied tools, referred to as basic classifiers, on the four superfamilies in Table 1.⁴⁸ In addition to the basic classifiers, we developed an ensemble of classifiers, called COMBINER, that employs a weighted voter and works as follows. If a basic classifier gives an “undetermined” verdict, the classifier is regarded as “abstaining” and its verdict is not counted. The result of COMBINER is the same as the result of the majority of the remaining classifiers. If there is a tie on the verdicts given by the remaining classifiers, the result of COMBINER is the same as the result of the BNN classifier. We see that in comparison with BLAST, SAM, and SAM-T99, the BNN classifier is faster, yielding fewer unclassified sequences. COMBINER achieves the highest precision and SAM-T99 requires most time among all the classifiers.

Table 4   Comparison of the studied classifiers on the globin superfamily

BNN BLAST SAM SAM-T99 COMBINER Precision 98.0% 92.7% 95.3% 93.2% 99.8% Specificity 98.0% 95.7% 99.8% 94.9% 99.6% Sensitivity 98.0% 100.0% 99.6% 100.0% 100.0% Unclassifiedp 0.0% 0.0% 1.1% 0.0% 0.0% Unclassifiedn 0.0% 6.7% 6.2% 5.1% 0.0% CPU time 36 1515 80 848 961 –—

Table 5   Comparison of the studied classifiers on the kinase superfamily

BNN BLAST SAM SAM-T99 COMBINER Precision 99.0% 86.2% 99.4% 92.6% 99.6% Specificity 98.8% 87.8% 99.5% 93.1% 99.5% Sensitivity 100.0% 100.0% 100.0% 100.0% 100.0% Unclassifiedp 0.0% 0.0% 0.0% 0.0% 0.0% Unclassifiedn 0.0% 4.4% 0.2% 2.0% 0.0% CPU time 30 1214 63 2 168 005 –—

Table 6   Comparison of the studied classifiers on the ras superfamily

BNN BLAST SAM SAM-T99 COMBINER Precision 98.7% 91.0% 95.5% 91.6% 99.7% Specificity 99.3% 95.0% 99.8% 92.2% 99.6% Sensitivity 96.1% 100.0% 100.0% 100.0% 100.0% Unclassifiedp 0.0% 0.0% 3.1% 0.0% 0.0% Unclassifiedn 0.0% 6.0% 4.6% 2.5% 0.0% CPU time 29 1232 64 637 424 –—

Table 7   Comparison of the studied classifiers on the ribitol superfamily

BNN BLAST SAM SAM-T99 COMBINER Precision 96.6% 88.5% 99.4% 90.4% 99.4% Specificity 97.0% 92.6% 100.0% 91.1% 99.2% Sensitivity 94.3% 100.0% 100.0% 100.0% 100.0% Unclassifiedp 0.0% 0.0% 2.0% 0.0% 0.0% Unclassifiedn 0.0% 6.2% 0.3% 2.5% 0.0% CPU time 27 1212 62 747 821 –—

Table 8 shows the complementarity of the four studied tools BNN, BLAST, SAM, and SAM-T99. We see that when all the four classifiers agree on their classification result, the result is correct with probability 80.88 percent/(80.88 percent + 0.07 percent) = 99.91 percent.

Table 8	Complementarity among the four studied tools BNN, BLAST, SAM, and SAM-T99. The percentages in the table add up to 100.

Classification Results Percentage of the Test Sequences All classifiers agreed and all were correct 80.88 All classifiers agreed and all were wrong 0.07 The classifiers disagreed and one of them was correct 18.91 The classifiers disagreed and all were wrong 0.14

Conclusion

In this paper we have presented a Bayesian neural network approach to classifying protein sequences. The main contributions of our work include:

• The development of new algorithms for extracting the global similarity and the local similarity from the sequences that are used as input features of the Bayesian neural network
• The development of new measures for evaluating the significance of 2-grams and frequently occurring motifs used in classifying the sequences
• Experimental studies in which we compare the performance of the proposed BNN classifier with three other classifiers, namely BLAST, SAM, and SAM-T99, on four different superfamilies of sequences in the PIR protein database

The main findings of our work include the following:

• The four studied classifiers, BNN, BLAST, SAM, and SAM-T99, complement each other; combining them yields better results than using the classifiers individually.
• The training phase, which is done only once, of the BNN classifier may take some time. After the classifier is trained, it runs significantly faster than BLAST and SAM-T99 in sequence classification.

Future research directions include:

• Comparison of motifs generated by different tools in combination with learning-based tools such as neural networks and hidden Markov models when applied to sequence classification in PIR, PROSITE,^32,49 and other protein databases
• Generalization of the classifiers in combination with graph matching algorithms to analyze the sequence-structure relationship in protein and DNA sequences.

Acknowledgments

We thank the anonymous reviewers for their thoughtful comments and constructive suggestions, which helped to improve the paper. We also thank David Mackay for sharing the Bayesian neural network software with us, and Richard Hughey for providing us with the SAM package.

This work was supported in part by National Science Foundation grants IRI-9531548, IRI-9531554, IIS-9988345, and IIS-9988636, and by a grant from Novartis Pharmaceuticals Corporation.

**Trademark or registered trademark of Intel Corporation or Linus Torvalds.

Cited references and notes

Accepted for publication January 24, 2001.