The protein sequences of 3-phosphoglycerate kinase (3PGK) were taken from (Pollack, et al., 2005) kindly provided by the authors.

An all against all comparison was carried out using BLAST (Altschul, et al., 1990) version 2.2.13 downloaded from http://www.ncbi.nlm.nih.gov/BLAST/download.shtml The BLOSUM62 matrix was used with a gap opening penalty of 11 and a gap extension penalty of 1 (default parameters). The results were stored in a compressed, tab-delimited ASCII file.

An all against all comparison was carried out using the Smith-Waterman algorithm (Smith and Waterman, 1981) as implemented in the water program of EMBOSS (Rice, et al., 2000). The program was downloaded from ftp://ftp.bioinformatics.org/pub/biobrew/. The BLOSUM62 matrix was used with a gap opening penalty of 10 and a gap extension penalty of 0.5 (default parameters). The results were stored in a compressed, tab-delimited ASCII file.

An all against all comparision was carried out using the Needleman-Wunsch algorithm (Needleman and Wunsch, 1970) as implemented in the needle program of EMBOSS (Rice, et al., 2000). The program was downloaded from ftp://ftp.bioinformatics.org/pub/biobrew/. The BLOSUM62 matrix was used with a gap opening penalty of 10 and a gap extension penalty of 0.5 (default). The results were stored in a compressed, tab-delimited ASCII file.

The Local Alignment Kernel program version 0.3 of Saigo and associates (Saigo, et al., 2004) was downloaded from http://cg.ensmp.fr/~vert/. The following run parameters were used: Default comparison matrix found in the parameters.h file. Gap opening penalty = 11 (default), Gap extension penalty = 1 (default), Scaling parameter = 0.5.

All vs. all comparison or the dataset was performed using a compression distance function D(X,Y) that can be calculated between two sequences, X and Y, as follows (Cilibrasi and Vitanyi, 2005, Kocsor et al, 2006): D(X,Y) = (C(xy) – min{C(X),C(Y)}) / max{C(X),C(Y)}, where C(.) denotes the length of a compressed string, compressed by the LZW (Lempel and Ziv, 1976) or the PPMZ algorithm (Bloom, 1998). The LZW algorithm was implemented in C, while the PPMZ2 algorithm was downloaded from Charles Bloom’s homepage (http://www.cbloom.com/src/ ppmz.html).

Nearest neighbour (1NN) classification is a technique whereby a query sequence is assigned to the a priori known class of the database entry that was found most similar to it in terms of a distance/similarity measure (for an introduction see Duda, et al., 2001).

The Support Vector Machines (SVM) classifier computes a hyperplane with the largest margin between the +train and –train groups (Vapnik, 1998) and the classification is based on the distance of the test objects from this hyperplane. SVMLight package (Joachims, 1999, Version 2.51, January 2002, downloaded from http://svmlight.joachims.org/ ) was used for the evaluation. The capacity parameter C was set to 100, the RBF kernel (also called Gaussian kernel) was used with its sigma parameter set to the median Euclidean distance from any positive training example to the nearest negative example. Each protein was represented by a feature vector whose components were similarity/distance scores computed between the protein and the proteins of the training set (Liao and Noble, 2003). The ROC analysis and the calculation of the AUC score was based on the distance of the test proteins from the hyperplane, used as the ranking variable.

The Random Forest (RF) technique uses a combination of decision trees (Breiman, 2001). The RF algorithm was used as implemented in the WEKA software package (Witten and Frank, 1999, Version 3.4.7, December 2005, downloaded from http://www.cs.waikato.ac.nz/ml/weka/). 10 trees were used and the number of variables in each node was set to log(D+1), where D is the number of inputs. Each protein was represented by a feature vector whose components were similarity/distance scores computed between the protein and the proteins of the training set. The output of the RF for a test protein was the probability of the protein belonging to the positive class. This value was then used as a ranking variable for ROC analysis and for the calculation of the AUC value.

The Artificial Neural Network (ANN) classifier consists of connected artificial neurons built in a multi-layer structure (Bishop, 1995). A three layer ANN was used and the number of neurons within the hidden layer was set to 20. The ANN algorithm was used as implemented in the WEKA software package (Witten and Frank, 1999, Version 3.4.7, December 2005, downloaded from http://www.cs.waikato.ac.nz/ml/weka/).

The Logistic Regression (LogReg) is a variation of ordinary regression which is used when the response variable is a dichotomous (e.g. -1 and 1) and the input variable are continuous, categorical or both (Rice, 1994). The LogReg algorithm was used as implemented in the WEKA software package (Witten and Frank, 1999, Version 3.4.7, December 2005, downloaded from http://www.cs.waikato.ac.nz/ml/weka/). Each protein was represented by a feature vector whose components were similarity/distance scores computed between the protein and the proteins of the training set. The output of the LogReg for a test protein was the probability of the test protein belonging to the positive class. This value was then used as a ranking variable for ROC analysis and for the calculation of the AUC value.

The evaluation of classification performance was carried out by the standard receiver operator characteristic (ROC) analysis (for an introduction see (Duda, et al., 2000)). This method is designed to test the ranking ability of a given classifier based on a real-valued ranking parameter. In the case of nearest neighbour classification, the ranking parameter was a similarity/distance parameter calculated between an object and the nearest member of the positive training set (outlier detection). Briefly, the analysis is carried out by plotting sensitivity vs 1-specificity at various threshold values, then the resulting curve is integrated to give an “area under curve” or AUC value. These values are determined for each classification experiment. For a perfect ranking, AUC=1.0, for random ranking AUC=0.5 (Egan, 1975).