extfieldsofstudy:
Medicine
Computer Science

s2fieldsofstudy:
Computer Science
Biology

text:
An Empirical Study of Different Approaches for Protein Classification

Many domains would benefit from reliable and efficient systems for automatic protein classification. An area of particular interest in recent studies on automatic protein classification is the exploration of new methods for extracting features from a protein that work well for specific problems. These methods, however, are not generalizable and have proven useful in only a few domains. Our goal is to evaluate several feature extraction approaches for representing proteins by testing them across multiple datasets. Different types of protein representations are evaluated: those starting from the position specific scoring matrix of the proteins (PSSM), those derived from the amino-acid sequence, two matrix representations, and features taken from the 3D tertiary structure of the protein. We also test new variants of proteins descriptors. We develop our system experimentally by comparing and combining different descriptors taken from the protein representations. Each descriptor is used to train a separate support vector machine (SVM), and the results are combined by sum rule. Some stand-alone descriptors work well on some datasets but not on others. Through fusion, the different descriptors provide a performance that works well across all tested datasets, in some cases performing better than the state-of-the-art.

Introduction
The explosion of protein sequences generated in the postgenomic era has not been followed by an equal increase in the knowledge of protein biological attributes, which are essential for basic research and drug development. Since manual classification of proteins by means of biological experiments is both time-consuming and costly, much effort has been applied to the problem of automating this process using various machine learning algorithms and computational tools for fast and effective classification of proteins given their sequence information [1]. According to [2], a process designed to predict an attribute of a protein based on its sequence generally involves the following procedures: (1) constructing a benchmark dataset for testing and training machine learning predictors, (2) formulating a protein representation based on a discrete numerical model that is correlated with the attribute to predict, (3) proposing a powerful machine learning approach to perform the prediction, (4) evaluating the accuracy of the method according to a fair testing protocol, and (5) establishing a user-friendly webserver accessible to the public.
In this work we are mainly interested in the second procedure, that is, in the definition of a discrete numerical representation for a protein. Since many different representations have been proposed in the literature, it would be valuable to investigate which of these are most useful for the specific applications, such as subcellular localization and proteinprotein interactions [3][4][5][6], to which these representations are applied [7,8].
Two kinds of models are typically employed to represent protein samples: the sequential model and the discrete model. The most widely used sequential model is based on the entire amino-acid sequence of a protein, expressed by the sequence of its residues, with each one belonging to one of the 20 native amino-acid types: (1) 2 The Scientific World Journal This kind of approach, whose length varies depending on the protein structure, is not suited for most machine learning predictors and fails to work when the query protein does not have significant sequence similarity to any attribute-known proteins.
More suitable for machine learning purposes are protein discrete models, which fall into two main classes. The first class includes the simple amino-acid composition (AAC) and approaches that are based on the AAC-discrete model, such as Chou's pseudo-amino-acid composition (PseAAC) [3][4][5], which is arguably one of the most popular methods for extracting features from proteins. This first class includes techniques based on vector representations of the protein, that is, where a protein sequence = ( 1 , 2 , . . . , ) is represented by a vector ∈ R N . In [9] AAC is a vector of length 20 that includes the normalized occurrence frequencies of the 20 native amino acids. PseAAC [10,11] expands AAC by retaining information embedded in protein sequences, such as some additional factors that incorporate information regarding a protein's sequential order. Various modes, such as a series of rank-different correlation factors along a protein chain, represent the sequential information. For an excellent history of the development of PseAAC that includes how to use the concept of Chou's PseAAC to develop 16 variant forms of PseAAC, the reader is referred to [11]. In [12] a protein representation based on physicochemical encodings is proposed that combines the value of a given property for an amino acid with its 2 grams representation. Another vector representation is the quasiresidue couple [13], a model which combines information related to a fixed physicochemical property of the protein with the sequence order effect of the composition of the amino acid. Other approaches belonging to this class of protein representation include dipeptide [14], tripeptide [15], and tetrapeptide [16]. These approaches are based on -peptide descriptors, where each protein is represented by a vector of length 20 that includes the normalized occurrence frequencies of the given -peptide. For reducing the dimensionality of the descriptor, a feature selection algorithm may be used, as in [16].
Before proceeding to the second class of representations based on protein discrete models, it should be noted that a number of different PseAAC methods have been developed for specific applications, such as for predicting certain biological attributes. Some examples include cellular automata image classification [17][18][19][20], complexity measure factor [19,21], gray dynamic model [17,18], and functional domain composition [20].
The second class of protein feature extraction methods is based on kernels. One of the first kernel-based methods (proposed for remote homology detection) is the Fisher kernel [22]. A kernel that performs equally well but with lower computational cost is the mismatch string kernel proposed in [23,24] that measures sequence similarity based on shared occurrences of subsequences. In [25] another class of kernels is proposed for vectors derived from the k-peptide vector, mapped by a matrix of high-scored pairs of k-peptides measured by BLOSUM62 scores. These kernel functions train a support vector machine (SVM). In [26] the biobasis function neural network trains sequence distances obtained using sequence alignment.
Aside from using AAC and protein properties for protein representation, several high performing features have also been derived from the position-specific scoring matrix (PSSM) [27]. PSSM describes a protein starting from the evolutionary information contained in a PSI-BLAST similarity search. For a survey of research using descriptors extracted from PSSM, see [28].
The main drawback of the methods based on structural or sequential features is that they only focus on the local variation of the protein itself. For this reason, cellular interactions of proteins have been investigated, as in [29], for solving some particular problems. In [30], the combination of traditional sequential features of the amino acid, such as PSSM, and different networks, such as KEGG enrichment scores of the protein neighbors in STRING network [31], were studied. Protein interaction networks have also been examined in [32,33].
In this study our objective is to search for a general ensemble method that works well across different protein classification datasets. To accomplish our goal we focus on structural and sequential features. We are motivated to study protein classification methods that generalize well because such systems offer the potential of deepening our understanding of protein representation and of speeding up real world development in new areas involving protein classification. Such investigations also have the potential of promoting and laying the foundations for the development of more robust and powerful classification systems.
The present paper provides an in-depth look at the protein representations that have led to the evolution of some of our previous work in this area.
(i) Reference [12], where an ensemble of approaches based on the amino-acid sequence was proposed.
(ii) Reference [34], where several feature extraction methods based on the calculation of texture descriptors starting from a wavelet representation of the protein were proposed.
(iii) Reference [28], where several feature extraction methods based on the calculation of PSSM were compared.
In this work we explain and compare several state-of-theart descriptors and some new variants starting from different types of protein representations: the PSSM, the amino-acid sequence, two matrix representations of the protein, and the 3D tertiary structure representations of the protein. We also develop a new ensemble (based on the above cited works) that performs well across multiple datasets, with our ensemble obtaining state-of-the-art performances on several datasets. For the sake of fairness, we use the same ensemble with the same set of parameters (i.e., the same weights in the weighted sum rule) across all tested datasets.
The remainder of this paper is organized as follows. In Section 2 the entire ensemble system is described, including all the protein representation approaches and feature extraction methods we use, all of which are detailed in Sections 3  and 4, respectively. In Section 5 the datasets used for experiments are described, and the results of several experiments conducted both with stand-alone approaches and ensembles of methods are reported and discussed. Finally, in Section 6, a number of conclusions are drawn and some future lines of research are proposed.

A General Machine Learning Approach for Protein Classification
Since several problems in the bioinformatics literature require the classification of proteins, a number of datasets are available for experiments, and recent research has focused on finding a compact and effective representation of proteins [3][4][5]12], possibly based on a fixed-length descriptor so that the classification problem can be solved by a machine learning approach. In this work several solutions are evaluated based on a general representation approach that is coupled with a fixed-length encoding scheme so that it can be used with a general purpose classifier.
The classification system illustrated in Figure 1 is an ensemble of classifiers trained using the different descriptors. Five types of protein representations are considered for all the datasets: the simple amino-acid sequence (AAS), PSSM of the proteins, substitution matrix representation (SMR), physicochemical property response matrix (PR), and the wavelet image (WAVE). A detailed description of each representation is given in Section 3. From each representation several descriptors are extracted, which we describe in Section 4. Some descriptors are extracted multiple times, once for each physicochemical property considered in the extraction process. The set of physicochemical properties is obtained from the amino-acid index [35] database (available at http://www.genome.jp/dbget/aaindex.html but note that we do not consider properties where the amino acids have value 0 or 1). An amino-acid index is a set of 20 numerical values representing the different physicochemical properties of amino acids. This database currently contains 544 indices and 94 substitution matrices, but a reduced number of properties are enough for classification task. According to [12], a selection of 25 properties is performed to reduce the number of properties considered in the feature extraction process.
The combination of representation and descriptors is summarized in Table 1, with the size of each descriptor reported in Table 1.
Each descriptor is used to train a general purpose classifier. SVMs are used for the classification task due to their wide diffusion and high generalization ability. SVMs derive from the field of statistical learning theory [36] and are binary-class prediction methods. The basic idea behind SVMs is to find the equation of a hyperplane (called the margin) that divides the training set into two classes so that all the points of the same class are located on the same side while simultaneously maximizing the distance between the two classes and the margin. In those problems where a linear decision boundary does not exist, kernel functions are used to project the data onto a higher-dimensional feature space so that they can be separated by a hyperplane. Typical kernels include polynomial kernels and the radial basis function kernel. SVMs can be easily extended to multiclass problems by considering the one-versus-all classification task. In the experiments reported in this work, all features used for training an SVM are linearly normalized to [0, 1] considering the training data. In each dataset the SVM is tuned considering only the training data (in other words, the test is blind) using a grid search approach. In our system, SVM is implemented as in the LibSVM toolbox (available at http://www.csie.ntu.edu.tw/?cjlin/libsvm).
The ensemble approaches based on the fusion of different descriptors are obtained by combining the pool of SVMs by weighted sum rule; this rule simply sums the scores obtained by the pool of SVMs classifiers, where to each SVM a given weight is applied.

A Sequential Representation for Proteins: Amino-Acid
Sequence (AAS). The most widely used representation for proteins is a sequential model of the amino-acid sequence: where ∈ A = [A, C, D, . . . , Y] and A is the set of the 20 native amino-acid types. Several studies [35] have shown that AAS coupled with other information related to the physicochemical properties of amino acids produces 4 The Scientific World Journal Table 1: Summarized description of the datasets (if available, the number of training and independent samples is given in column "number of samples"). The column BKB reports whether it is possible from the dataset to obtain the PDB of the proteins for extracting the backbone structure.

Name
Short many useful descriptors, some of which will be described in Section 4.

A Matrix Representation for Proteins: Position-Specific
Scoring Matrix (PSSM). The PSSM representation of a protein, first proposed in [27], is obtained from a group of sequences previously aligned by structural or sequence similarity. Such representations can be calculated using the application PSI-BLAST (position-specific iterated BLAST), which compares PSSM profiles for detecting remotely related homologous proteins or DNA. The PSSM representation considers the following parameters.
(1) Position: the index of each amino-acid residue in a sequence after multiple sequence alignment.
(2) Probe: a group of typical sequences of functionally related proteins already aligned by sequence or structural similarity.
(3) Profile: a matrix of 20 columns corresponding to the 20 amino acids.
(4) Consensus: the sequence of amino-acid residues most similar to all the alignment residues of probes at each position. The consensus sequence is generated by selecting the highest score in the profile at each position.
A PSSM representation for a given protein of length is an × 20 matrix, whose elements PSSM( , ) are calculated as where ( , ) is the ratio between the frequency of the th amino acid at the position of the probe and total number of probes and ( , ) is the value of Dayhoff 's mutation matrix between the th and th amino acids ( ( , ) is a substitution matrix). A substitution matrix describes the rate at which one character in a protein sequence changes to other character states over time. Substitution matrices are usually seen in the context of amino acid or DNA sequence alignments, where the similarity between sequences depends on their divergence time and the substitution rates as represented in the matrix. Small values of PSSM( , ) indicate weakly conserved positions and large values indicate strongly conserved positions. In our study, we used PSI-BLAST which can be called from MATLAB for extracting PSSM using the command system ("blastpgp.exe-i input.txt-d swissprot-Q output.txt-j 3, " where "input.txt" is the protein sequence and "output.txt" contains the PSSM matrix to create PSSMs for each protein sequence).

A Matrix Representation for Proteins: Substitution Matrix
Representation (SMR). In [28] a variant of a representation method called the substitution matrix representation (SMR) proposed by [37]  where ( , ) is a 20 × 20 substitution matrix whose element , represents the probability of amino acid mutating to amino acid during the evolution process (note: the MATLAB code for this representation is available at http://bias.csr.unibo.it/nanni/SMR.rar).
In the experiments reported below, 25 random physicochemical properties have been selected to create an ensemble (labelled SMR) of SMR -based predictors.

A Matrix Representation for Proteins
where index( , ) returns the value of the property for the amino acid .
Then PRM is handled as an image and resized to 250 × 250 if larger to obtain the final matrix PR . In the experiments reported below, 25 random physicochemical properties have been selected to create an ensemble (PR) of PR -based predictors.

A Matrix Representation for Proteins: Wavelet (WAVE).
Wavelets are very useful descriptors with lots of different applications. First [38] then later [34] have suggested using wavelets as a method to represents proteins. Since wavelet encoding requires a numerical representation, the protein sequence is first numerically encoded by substituting each amino acid with a value of a given physicochemical property . Then the Meyer continuous wavelet is applied to the wavelet transform coefficients (labelled WAVE ). Features are extracted by considering 100 decomposition scales. In the experiments reported below, 25 random physicochemical properties have been selected to create an ensemble WAVE of 25 WAVE -based predictors.

A Matrix Representation for Proteins: 3D Tertiary
Structure (DM). The 3D tertiary structure representation for proteins is based on the protein backbone (i.e., the sequence of its atoms) to characterize the whole protein structure [39,40]. Given a protein and its backbone = (Coor 1 , Coor 2 , . . . , Coor ) (obtained as the 3D coordinates of its atoms), a distance matrix DM is defined as where dist(⋅) is the Euclidean distance. (Note: the MAT-LAB code for extracting the distance matrix is available at http://bias.csr.unibo.it/nanni/DM.zip).
As with the other matrix representations introduced above, DM is regarded as a grayscale image, which is used to extract texture descriptors, as illustrated in Figure 2

Protein Feature Extraction Approaches
In this section the approaches used to extract descriptors from the different representations introduced above are described. Most of the descriptors extracted from the primary representation are based on substituting the letter representation of an amino acid with its value of a fixed physicochemical property. In order to make the result independent on the selected property, a selection on 25 or 50 properties is done by random, and the resulting descriptors are used to train an ensemble of SVM classifiers.

A Descriptor for Primary Representation: Amino-Acid Composition (AS).
Amino-acid composition is the simpler method for extracting features from a protein representation that is based on counting the fraction of a given amino acid: where ℎ( ) counts the number of occurrences of a given amino acid in a protein sequence of length .

A Descriptor for Primary
where the function ℎ( , ) counts the number of occurrences of a given couple of amino acids ( , ) in a protein sequence of length . The 2G descriptor is a 400-dimensional vector.

A Descriptor for Primary Representation: Quasiresidue
Couple (QRC). Quasiresidue Couple is a method for extracting features from the primary sequence of a protein [12] that is inspired by Chou's quasi-sequence-order model and Yuan's Markov chain model [41]. The original residue couple model was designed to represent both the information of the amino-acid composition and the order of the amino acids in the protein sequences. The quasiresidue couple descriptor is obtained by selecting a physicochemical property and combining its values with each nonzero entry in the residue couple. The parameter denotes the order of the composition (values ≤ 3 are considered enough to represent a sequence).
The QRC model (of order ≤ 3) for a physicochemical property is given by where and are the 20 different amino acids, is the length of the protein, the function index( , ) returns the value of the property for the amino acid , and the function , ( , , ) = index( , ), if = and = , , ( , , ) = 0 otherwise.
In our experiments, the QRC features are extracted for ranging from 1 to 3 and concatenated into a 1200-dimensional vector. In the experiments reported below, 25 random physicochemical properties have been selected to create an ensemble of QRC descriptors (Note: the MATLAB code for QRC is available at http://bias.csr.unibo.it/nanni/QRcouple2.zip).

A Descriptor for Primary
Representation: Autocovariance Approach (AC). The autocovariance approach [42] is a sequence-based variant of Chou's pseudo-amino-acid composition, which extracts a set of pseudo-amino-acid-based features (extracted by the MATLAB code shared by the original authors) from a given protein as the concatenation of the 20 standard amino-acid composition values and values reflecting the effect of sequence order. The parameter denotes the maximum distance between two considered amino acids , (set to 20 in the tests reported below).
Given a protein = ( 1 , 2 , . . . , ) and fixing a physicochemical property , the autocovariance descriptor is AC ∈ R 20+ : where the function index( , ) returns the value of the property for the amino acid , the function ℎ( ) counts the number of occurrences of a given amino acid in a protein sequence, and and are normalization factors denoting mean and the variance of on the 20 amino acids: In the experiments reported below, 25 random physicochemical properties have been selected to create an ensemble of 25 AC descriptors (Note: the MATLAB code for AC is available at http://bias.csr.unibo.it/nanni/EstraggoFeaturesAC.rar).

A Descriptor for Primary Representation: AAIndexLoc
(AA). The AAIndexLoc is a descriptor proposed in [43]. AAIndexLoc is composed of the following features.
(i) Amino-acid composition (20 features): this is a fraction of a given amino acid.
(ii) Weighted amino-acid composition (20 features): this is defined for a given amino acid as (amino-acid composition of ) ×index( , ).
(iii) Five-level grouping composition (25 features): the result of a five-level dipeptide composition applied to a classification of the amino acids by k-means (into five groups) considering their amino-acid index values. The five-level dipeptide composition is defined as the composition of the occurrence of two consecutive groups; see [43] for more details.
In the experiments reported below, 25 random physicochemical properties have been selected to create an ensemble of 25 AA descriptors. The Scientific World Journal 7 from the 10 characteristic sequences, CS Pt , obtained from each of the 10 different partitions Pt of A into 2 subsets of three classes (e.g., Pt = {(A1, A2, A3), (A4, A5, A6)} is one of the 10 partitions). CS Pt is obtained by transforming the protein into a numerical sequence where a given amino acid is represented by 1 if it belongs to the first class of the partition (i.e., (A1, A2, A3)) and 0 otherwise. The two sets of measures used to define GE are the frequency of 0s and 1s in each CS Pt and the frequency of transitions (i.e., number of 1s followed by a 0, and vice versa).

A Descriptor for Primary
where and denote the 20 different amino acids, is the length of the protein, the function index( , ) returns the value of the property for the amino acid , and the function ℎ( , ) counts the number of occurrences of a given couple of amino acids ( , ) in a protein sequence. The P2G descriptor is an 800-dimensional vector. In the experiments reported below, 25 random physicochemical properties have been selected to create an ensemble of 25 P2G descriptors.

A Descriptor for Primary Representation: N-Gram (NG).
The N-gram descriptor is similar to the standard 2 grams descriptor but is obtained on a different -peptide composition using different amino-acid alphabets. In this work 5 alphabets proposed in [45] are considered, and we train five different SVMs. Each classifier is trained using a differentpeptide composition with different amino-acid alphabets: Each protein is first translated according to the 5 alphabets. Then 2 gram representations are calculated from A1 to A2 languages, and the 3 gram representations are calculated from A3 to A4 to A5. The five descriptors are having dimensions #A , where = 2 for 2 gram representations and = 3 for 3 gram representations. The 5 representations are fused together by weighted sum rule (with weights 1, 1, 1, 0.5, and 0.25).

4.9.
A Descriptor for Primary Representation: Split Amino-Acid Composition (SAC). Split amino-acid composition is a descriptor proposed by [46] that is based on the subdivision of the protein sequence into parts from which a separate descriptor is calculated (i.e., the standard amino-acid composition for each part). In this work each protein is divided into the following three parts: (i) 20 amino acids of Nterminus, (ii) 20 amino acids of C-terminus, and (iii) the region between these two termini.

A Descriptor for Primary Representation: Discrete Wavelet (DW).
A sequence descriptor based on biorthogonal discrete wavelet is proposed in [34]. Given a protein = ( 1 , 2 , . . . , ) and a fixed physicochemical property , each amino acid of the sequence is substituted by its value of : where the function index( , ) returns the value of the property for the amino acid . The vector PP is then transformed in the wavelet space by a four-scale biorthogonal discrete wavelet. The final descriptor DW is obtained as the first five discrete cosine coefficients from the approximation coefficients and the maximum, minimum, mean, and standard deviation values from both detail and approximation coefficients. This choice is motivated by the fact that high-frequency components are noisy; thus the low-frequency components are more useful for the classification task.
In the experiments reported below, 25 random physicochemical properties have been selected to create an ensemble of 25 DW descriptors.

A Matrix-Based Descriptor: Average Blocks (AB).
This matrix descriptor was originally proposed in [47] for the PSSM representation of a protein, but it is used for other matrix representations in this work. Average blocks is a fixedlength vector AB ∈ R 400 elements obtained as the local average of the input matrix Mat ∈ R ×20 : where is a linear index used to scan the cells of Mat. Thus the final descriptor is a vector obtained as the average of Mat blocks (each related to the 5% of a sequence).

A Matrix-Based Descriptor: Single Average (SA).
This descriptor [48] is a variant of the previous one and is designed to group together rows related to the same amino acid, thus where is a linear index used to scan the cells of Mat, where A = [A, C, D, . . . , Y] is the ordered set of amino acids, and where (⋅, ⋅) is the Kronecker delta function.
In this work two variants of the single average descriptor are used: the one described above (labelled SA) and a version including matrix normalization using a sigmoid function by which each element of Mat is scaled to [0, 1] (labelled SAN).

A Matrix-Based Descriptor: Autocovariance Matrix (AM).
The autocovariance matrix is a matrix descriptor proposed in [49] that aims at avoiding the loss of the local sequence-order information. Each column of the input matrix is reduced to a fixed length by autocovariance variables. An autocovariance matrix (AM) describes the average correlation between positions in a series of lags (i.e., the residue number when applied to protein sequences) throughout the protein sequence.
AM can be calculated from an input matrix Mat ∈ R ×20 as follows: where is a linear index used to scan the cells of Mat, lag denotes the distance between one residue and its neighbors, and is the length of the sequence.

A Matrix-Based Descriptor: Pseudo-PSSM (PP).
This pseudo-PSSM approach (PP) is one of the most widely used matrix descriptors for proteins (see [47,50]). Usually applied to the PSSM matrix representation of a protein, PP is extended in this work to SMR. This descriptor is designed to retain information about amino-acid sequence by considering the pseudo-amino-acid composition. Given an input matrix Mat ∈ R ×20 , the pseudo-PSSM descriptor is a vector PP ∈ R 320 defined as where is a linear index used to scan the cells of Mat, where lag denotes the distance between one residue and its neighbors, and where is the length of the sequence and ∈ R ×20 , which is a normalized version of Mat defined as

A Matrix-Based Descriptor: Singular Value Decomposition (SVD).
Singular value decomposition is a general purpose matrix factorization approach [51] that has many useful applications in signal processing and statistics. In this work SVD is applied to a matrix representation of a protein with the aim of reducing its dimensionality. Given an input matrix Mat ∈ R × , SVD is used to calculate its factorization of the form: Mat = Σ , where Σ is a diagonal matrix whose diagonal entries are known as the singular values of Mat. The resulting descriptor is the ordered set of singular values: SVD ∈ R , where = min{ , }.

A Matrix-Based Descriptor: Discrete Cosine Transform (DCT). DCT [52] is a linear separable transformation for converting a signal into elementary frequency components;
it is widely used in image compression for its capability to concentrate information into a small number of coefficients. Given an input matrix Mat ∈ R × , its DCT transformation is defined as In this work the final DCT descriptor is obtained by retaining the first 400 coefficients.
The Scientific World Journal

A Matrix-Based Descriptor: N-Gram Features (NGR).
The N-gram descriptor is usually extracted from the primary protein sequence (as already described in Section 4.6). In [53] this descriptor is extracted directly from the PSSM matrix by accumulating the probabilities of each of the N-gram according to the probability information contained in PSSM.
Given an input matrix Mat ∈ R ×20 representing the PSSM of a given protein, the frequency of occurrence of transition from th amino acid to th amino acid is calculated as follows for 2 grams (BGR) and 3 grams (TGR), respectively:

A Matrix-Based Descriptor: Texture Descriptors.
A very interesting feature extraction approach for proteins is to treat a protein matrix representation as an image and to use well-known image texture descriptors for extracting features. In this work two high performing descriptors are evaluated: local binary pattern histogram fourier (LHF) descriptors [54] and local phase quantization (LPQ) (Note: the MATLAB code for LBQ is available at http://www.cse.oulu.fi/CMV/Downloads/LPQMatlab) [55]. Both these descriptors are extracted according to a global and a local evaluation (i.e., from the whole image or from subwindows of an image with the results of each concatenated). The feature vectors extracted are labelled, respectively: LHF G and LPQ G, when extracted from the whole image, and LHF L and LPQ L, when obtained by dividing the image into three equal subwindows and concatenating the resulting feature vectors.

Local Binary Pattern Histogram Fourier (LHF).
First proposed by [54], LHF is a rotation invariant image descriptor that is computed from the discrete Fourier transforms of local binary pattern (LBP) histograms. The LHF descriptor computes a noninvariant LBP histogram and constructs rotationally invariant features from the histogram using discrete Fourier transform. The features are invariant to cyclic shifts in the input vector. In this work the final vector is the concatenation of results obtained using the following parameters for LBP computation: ( = 16; = 2) and ( = 8; = 1).

Local Phase Quantization (LPQ).
The LPQ operator [55] is based on the blur invariance property of the Fourier phase spectrum. LPQ uses the local phase information extracted from the two-dimensional short-term Fourier transform (STFT) computed over a rectangular neighborhood defined by each pixel position. After STFT only four complex coefficients are retained corresponding to four fixed two-dimensional frequencies, which are separated into real and imaginary parts and quantized as integers between 0-255 using a binary coding scheme. The final feature vector is a normalized histogram of such coefficients. In this work the final vector is the concatenation of results obtained with two different radii for LPQ computation: radii 3 and 5, using the Gaussian derivative quadrature filter pair for local frequency estimation (Note: we used the MATLAB code for LPQ available at http://www.ee.oulu.fi/mvg/download/lpq/).

Experiments
This section reports the results of an experimental evaluation of the protein descriptors on sequence-based protein classification problems performed on several datasets.

Datasets, Testing Protocols, and Performance Indicators.
The proposed approach has been evaluated on the 15 datasets listed below and according to the testing protocols suggested by the developers of the datasets. A brief summary description of each dataset and related testing protocol is reported in Table 2. [56]). This is a dataset containing membrane proteins belonging to eight membrane types: (1) single-pass type I transmembrane, (2) singlepass type II, (3) single-pass type III, (4) single-pass type IV, (5) multipass transmembrane, (6) lipid-chain-anchored membrane, (7) GPI-anchored membrane, and (8) peripheral membrane.The objective of this dataset is to classify a given query protein in a given localization. All proteins in the same subcellular location have less than 80% sequence identity. The testing protocol is based on a given subdivision, each of which is divided into a training set (3249 proteins) and a testing set (4333 proteins). [57]). This is a dataset containing 118 DNA-binding proteins and 231 non-DNA-binding proteins with less than 35% sequence identity between each pair. [58]). This is a dataset that was created using the PDB archive and includes proteins annotated as enzymes, specifically, 381 hydrolases and 713 enzymes of different kinds. [58]). This is a dataset that was extracted from the PDB archive by selecting proteins according to GO annotations. It distinguishes the biological processes "immune response" (33 proteins) and "DNA repair" (43 proteins) and the molecular functions "substrate specific transporter activity" (39 proteins) and "signal transducer activity" (53 proteins). The presence of highly similar proteins within the same class was avoided by removing sequences which had more than 30% identity.

GO Dataset (GO) (See
Human Interaction (HI) (See [59]). This is from the positive protein-protein-interaction (PPI) dataset [59], which was  [59] for details). The final dataset was constructed from the original benchmark dataset by excluding proteins having more 25% sequence identity to any of the other proteins using the PISCES program. Accordingly, the number of proteins in the positive dataset was reduced from 9,630 to 2,502, and the number of proteins in the negative dates was reduced from 2,184 to 661 for a total of 3,899 positive samples of protein pairs and 4,262 negative samples of protein pairs. This dataset is not used in all experiments because of its large size (e.g., it is not used in the first experiment to calculate the rank of the compared approaches). [60]). This is a dataset containing 317 proteins classified into three submitochondria locations: 131 inner membrane proteins; 41 outer membrane proteins; and 145 matrix proteins. To obtain a balance between the homologous bias and the size of the training set, no more than 40% similarity was allowed (i.e., the identity between any 2 sequences in the processed dataset had to be less than 40%).

Submitochondria Locations (SL) (See
Virulent Datasets 1 and 2 (VI1, VI2) (See [48]). This is a dataset containing bacterial virulent protein sequences that were retrieved from the SWISS-PROT and VFDB (an integrated and comprehensive database of virulence factors of bacterial pathogens). The two independent sets share the same training set of 1025 virulent and 1030 nonvirulent bacterial sequences. The virulent independent dataset 1 (VI1) contains 83 protein sequences, selected so that no two sequences are more than 40% similar. The virulent independent dataset 2 (VI2) contains 141 virulent and 143 nonvirulent sequences from bacterial pathogens sequences of organisms that were not represented in the training set. [48]). This is a dataset containing 469 adhesins and 703 nonadhesins proteins (including several archaebacterial, viral, and yeast nonvirulent proteins). The training set contains 1025 virulent and 1030 nonvirulent bacterial sequences. [20]). This is a dataset containing G proteincoupled receptors (GPCR) and non-GPCRs. The aim of this dataset is to identify a query protein as either GPCR or non-GPCR. None of the proteins included have ≥40% pairwise sequence identity to any other in the same subset. [61]). This is a dataset containing grampositive proteins that belong to five subcellular location sites:

GRAM (GR) (See
(1) cell wall, (2) cytoplasm, (3) extracellular, (4) periplasm, and (5) plasma membrane. The aim of this dataset is to classify a given query protein in a given localization. Only those proteins that have <25% sequence identity to any other in a same subcellular location were allowed to be included in the benchmark datasets. In this way, redundancy and homology bias is limited.
Human Protein-Protein Interaction (HU) (See [62]). This is a dataset containing a total of 1882 human protein pairs. Each pair of proteins is labeled as either an interacting pair or a noninteracting pair. [63]). This is a dataset containing proteins that belong to four classes: cytoplasm, extracellular, nucleus, and plasma membrane. The aim of this dataset is to classify a given query protein in a given localization. None of the proteins have 25% sequence identity to any other in the same subset (subcellular location). Subcellular localization of viral proteins within a host cell or virus-infected cell is very useful for studying the function of viral proteins as well as designing antiviral drugs.

Viral (VR) (See
Protein Fold (PF) (See [15]). The dataset used in this work is a subset of the database presented in [15]. The training set contains 313 proteins and the testing set contains 385 samples from 27 classes. The sequence similarities are less than 35% and 40%, respectively. The testing protocol uses the training The Scientific World Journal 11 set to build the classifier models and independently uses the testing set to evaluate performance. [64]). This is a dataset that was constructed to predict the state of cysteines. It contains 957 protein sequences, having a sequence identity lower than 25%. The dataset is divided into three classes: proteins that do not have disulfide bonds, which are labeled as "none" and two others that are labelled "mix" and "all" depending on whether all the cysteines have been formed into disulfide bonds or not.

Cysteine (CY) (See
SubCell (SC). This is a dataset containing proteins that belong to three subcellular location sites: (1) nucleus, (2) cytoplasm, and (3) extracellular. Only proteins where the PDB format is available are used. The aim is to classify a given query protein in a given localization. The testing protocol employed in the experiments depended on the datasets. In cases where the original dataset is not divided into training and testing sets, a 10-fold crossvalidation was performed (results averaged on ten experiments); otherwise the subdivision of the training and testing sets was maintained.
Three performance indicators are used in the reported results: the classification accuracy, the area under the ROC curve (AUC), and the statistical rank. The accuracy is the ratio between the number of samples correctly classified and the total number of samples. The ROC curve is a graphical plot of the sensitivity of a binary classifier versus false positives (1-specificity), as its discrimination threshold is varied. AUC [65] is a scalar measure that can be interpreted as the probability that the classifier will assign a lower score to a randomly picked positive pattern than to a randomly picked negative pattern. When a multiclass dataset is used, the oneversus-all area under ROC curve is used [66]. Since AUC is considered one of the most reliable performance indicators [67], internal comparisons are evaluated according to AUC, while accuracy is used to compare results with the literature in those cases where AUC is not reported.
The statistical rank returns the relative position of a method against other tested methods. The average rank is the most stable indicator to average performance on different datasets and is calculated using the Friedman's test (alpha = 0.05) applying the Holm post hoc procedure [68].

Experimental
Results. The first experiment is aimed at comparing all the descriptors detailed in Section 3 and is summarized in Table 2 in terms of the statistical rank evaluated considering all the datasets (excluding HI).
In Table 3 the different methods are evaluated by their average rank, with the best descriptor for each representation highlighted. Notice that the representation method DM is not included in this table; this is because it is available only in a subset of datasets (i.e., where the PDB format is obtainable). Examining Table 3 it is clear that on average PSSM is the best representation. The other representations, however, are useful for building a strong ensemble that outperforms the results of the best stand-alone descriptors, as demonstrated by experiments reported. The second experiment is aimed at comparing only the best descriptors found in Table 3. In Tables 4 and 5, we report the performance (in terms of AUC) of the two best 12 The Scientific World Journal   descriptors for each representation (see Table 3) related to 2class and multiclass datasets, respectively. The two best results for each dataset are highlighted. On average PP coupled with PSSM obtains the best results in most datasets, but in some problems the PP descriptor is outperformed by SAN (which is always coupled to PSSM). Some results related to HI are not reported due to the high computational costs. The best results in the previous tables are almost always obtained with PSSM and AAS representations of proteins. Comparing the reported results of PR and WAVE with [34], where the first versions of those representations were tested, with the experiments reported here, it is clear that there is a boost in performance in PR and WAVE. See, for comparison, Table 6, where previous results obtained using these representations (SVM is the classifier) are reported. The results of these two ensembles are compared in Tables  7 and 8 with the best three single methods. Results related to FUS2 are reported for only a few datasets since it contains a descriptor based on the DM matrix.
The most interesting result among those reported in Tables 7 and 8 is that of our ensemble FUS1, which outperforms the other approaches in nearly all the datasets and accomplishes this performance gain without changing its weights. It is also interesting to note that even though the recent representation of SMR works rather poorly compared with PSSM and AAS, it is nonetheless useful when combined with PSSM and AAS. The other representations, WAVE, PR,  and DM, are not yet useful in fusion; in our opinion, a wide survey on different texture descriptors still needs to be performed to determine which set of descriptors can boost the performance of these representations. The forth experiment is aimed at comparing our ensembles FUS1 and FUS2 with the performance reported in the literature by other state-of-the-art approaches. Unfortunately, a fair comparison with other approaches is not always easy for the following reasons.
(i) Several papers use self-collected datasets and only in a few cases is the code for feature extraction available.
(ii) Many works report results obtained on small datasets, without a clear indication of the testing protocol used; therefore, it is difficult to know whether parameter optimization was performed on the entire dataset (thereby overfitting results) or only on a training set.
Overfitting is particularly dangerous in small datasets.
The comparison is much easier when considering large datasets (as with HI and MEM) or when an independent dataset separate from the training set is available (as in PF). So in the following tests we compare our results only when we are quite sure that the comparison is fair.
Tables 9 and 10 report the performance in terms of AUC and accuracy, respectively. When available we have used original source code for comparing methods. When results are extracted from the original reference paper, the best method reported in the paper is considered in the comparison. It should also be noted that in what follows we are comparing the most widely used descriptors in the literature, using whenever possible the original source code for the descriptors (not our reimplementation). To ensure fair comparison, we have also used the same testing protocol that was used in the original reference. Moreover, it should be noted that although it is the case that when small datasets are used (or when only a few datasets are tested) a jackknife approach is quite feasible, in our survey using several datasets and many descriptors, the jackknife approach becomes computationally unfeasible.
The results reported in Tables 9 and 10 are interesting not only because in this work we outperform all our previously proposed ensembles but also because we obtain state-ofthe-art performances on such large datasets as HI and on such widely used benchmarks as PF and MEM. Please note that our ensemble FUS1 works well across nearly all the tested datasets, without any parameter tuning to optimize performance for a given dataset.
Considering the dataset PF, which is one of the most widely used benchmarks, FUS1 compares very well with the other approaches where features are not extracted using 3D information (for a fair comparison). The performance FUS1 is all the more valuable when considering that unlike the older approaches, ours is obtained without ad-hoc feature extractors (where the features are validated only on PF with a high risk of overfitting).
The compared approaches on PF are the following.
(i) Reference [15], where six kinds of features denoted by C, S, H, P, V, and Z are proposed. C is the popular amino-acid composition; the remaining five indicate the features of polarity, polarizability, normalized Van Der Waals volume, hydrophobicity, and predicted secondary structure, respectively.
(ii) Reference [70], where the same CSHPVZ features proposed by [15] are used, but with different classifier systems.
(iv) Reference [72], where the authors do the same work as [69] but improve the classifier system using the technique of data fusion.
14 The Scientific World Journal  Since the PF dataset aims at predicting the 3D structure of a protein, features extracted from 3D representations are highly useful as proven by the better performance obtained by FUS2 with respect to FUS1.
Given the results reported above, our proposed ensemble FUS1 should prove useful for practitioners and experts alike since it can form the base for building systems that are optimized for particular problems (e.g., SVM optimization and physicochemical properties selection). Obviously, it is very important that only the training data be used for physicochemical properties selection; it is not fair to choose the physicochemical properties using the entire dataset to do so. Moreover, when the ensemble is optimized for a given dataset, it is very important to consider that large descriptors work better when a large training set is available (because of the curse of dimensionality). As an example of this, we report below the performance of AAS(RC) and AAS(AC). AAS(RC) has high dimensionality and, accordingly, as seen in Table 11, works well mainly on large datasets. For this reason, it can be used in an ensemble only in the case where a large training set is available (as with MEM or HI). Notice that in HI the method AAS(RC) outperforms our best ensemble.
A similar behavior occurs with some other methods. In Table 12 we report the performance obtained by PSSM(LPQ G). It works very poorly in some datasets but very well in others (mainly with the larger datasets).
It is clear from our experimental results that it is difficult to find an ensemble that performs the best across each of the datasets. Nonetheless, we have shown that among the several tested and proposed protein descriptors, it is always possible to find an ensemble that performs well in each type of dataset.

Conclusion
One goal in this work was to provide a survey of several state-of-the-art descriptors and some new variants starting from different protein representations. We compare the performance of these descriptors across several benchmark datasets. The results reported in this paper show that the best protein representation is PSSM, but AAS and SMR also work well. We found that no single descriptor is superior to all others across all tested datasets.
Another objective of this study was to search for a general ensemble method that could work well on different protein classification datasets. Accordingly, we performed several fusions for finding experimentally a set of descriptors based on different representations that worked well across each of the tested datasets. A couple of representations, such as  WAVE and PR, were not useful in fusion. Given the results of our experiments, we concluded that a wide survey of different texture descriptors needs to be performed since different descriptors contain different information that might boost performance when combined with others. Our major contribution is to propose an ensemble of descriptors/classifiers for sequence-based protein classification that not only works well across several datasets but also, in some cases, proves superior to the state-of-the-art. Unlike other papers that develop a web server, we share almost all the MATLAB codes used in the proposed approaches. Our proposed ensemble could be considered a baseline system for developing an ad-hoc system for a given problem. Issues to consider when optimizing such a base system for a given dataset were also discussed. For instance, the size of datasets seems to play a role in the choice of protein representation, with some descriptors showing stronger performance on large datasets. In particular, approaches that use a high dimensional representation (e.g., RC) requires larger datasets in order to avoid the curse of dimensionality.
To further improve the performance of our methods, we plan, in the future, on testing more classification approaches. We are particularly interested in investigating ensembles made with AdaBoost and Rotation forest [74] classifiers. The main drawback using these ensemble methods is that they require more computational power than SVM, the classifier used in this work. Although this would not be a problem for the testing phase, it would be a drawback in the training phase if we want to compare a number of different descriptors across several (preferably large) datasets.


Design Architecture-Based on Web Server and Application Cluster in Cloud Environment

Cloud has been a computational and storage solution for many data centric organizations. The problem today those organizations are facing from the cloud is in data searching in an efficient manner. A framework is required to distribute the work of searching and fetching from thousands of computers. The data in HDFS is scattered and needs lots of time to retrieve. The major idea is to design a web server in the map phase using the jetty web server which will give a fast and efficient way of searching data in MapReduce paradigm. For real time processing on Hadoop, a searchable mechanism is implemented in HDFS by creating a multilevel index in web server with multi-level index keys. The web server uses to handle traffic throughput. By web clustering technology we can improve the application performance. To keep the work down, the load balancer should automatically be able to distribute load to the newly added nodes in the server.

INTRODUCTION
Cloud is emerging as a cost effective solution in the computing world. The data capacity of the cloud has gone up to a zettabyte from gigabyte. Cloud Computing are the virtual pool of computing resources that provides an online pool of resources for computing, where the computing is performed by efficient sharing of resources, which we call as load balancing/ resource sharing. Cloud relies on its resources for handling the application in the local and personal devices. MapReduce [2] is the heartbeat of Hadoop framework. It is a programming paradigm that allows for huge scalability across hundreds or thousands of servers in a cluster. It is a programming model that is associated with the implementation of processing and generating large data sets. The term MapReduce basically refers to two separate and distinct tasks that Hadoop programs perform [6]. MapReduce also plays an important factor in Cloud computing environment, because it decreases the complexity of the distributed programming and is easy to be developing on large clusters of common machine [12]. The data flow architecture of MapReduce shows the techniques to analyze and produce the search index [12] as shown in figure1.
The main purpose of this work is to develop a technique for a fast and efficient way of searching data in the MapReduce paradigm of the Hadoop Distributed File System. Hadoop is a framework which is specifically designed to process and handle vast amounts of data [10]. It is based on the principle of moving computation to the place of data which is cheaper than moving large data blocks to the place of computation.
The Hadoop [1] MapReduce framework is a master -slave architecture, which has a single master server called a job tracker and several slave servers called task trackers, one per node in the cluster. The job tracker is the point of interaction between users and the framework. The user submits map and reduce jobs to the job tracker, which puts them in a queue of pending jobs and executes them on a first-come-first-served basis. In this paper the schematic view of the design architecture is given, with effective scenario to investigate the performance of Hadoop in high speed retrieval of data in the cloud environment by replacing the map phase of the MapReduce paradigm with a web server. For real time processing on Hadoop, a searchable mechanism is implemented in HDFS by creating multilevel index in web server with multi-level index keys in NameNode.
The rest of the paper is structured as follows. Module 2 & 3 highlights the related works and Hadoop Distributed File System implementation. Module 4 describes the web application in a cloud and architecture design. Module 5 describes the implementation details followed by the results & analysis. Finally work done is concluding, with future work in module 6. Hadoop [10] is an open source Java-based programming framework which is a part of the Apache project which was sponsored by the Apache Software Foundation. MapReduce is a part of Hadoop framework. It is a programming concept and Hadoop is a framework to run MapReduce program. In February 2003 first MapReduce library was introduced @Google. In 2004 MapReduce was simplified for data processing on large cluster [4]. Google introduced MapReduce in 2004 to support large distributed computing, on large clusters of computers to implement huge amounts of data set [3]. MapReduce is a framework that processed parallel problems of huge data set using a large number of computers or nodes that is collectively referred to as a cluster or a grid [7]. A distributed file system (DFS) facilitates rapid data transfer rates among nodes and allows the system to continue operating uninterrupted in case of a node failure. It was originally developed to support distribution for the Nutch search engine project. In January 2008 Hadoop made apache as a top level project center.

RELATED WORK
In July 2009 new Hadoop subproject was found where Hadoop core is renamed as Hadoop Common. In this subproject MapReduce and Hadoop distributed file system (HDFS) get separated for doing separate work. HDFS is designed to store very large data sets [10]. In 2010 web application based process is used to handle high throughput traffic [6]. Facebook has claimed that they had the largest Hadoop cluster in the world with 21 PB of storage and on July 27th, 2011 they have announced that the data had grown up to 30PB.
In 2012 the load rebalancing problem in cloud DFSs is illustrated by Hsueh-Yi Chung Che-Wei Chang Hung Chang Hsiao, Yu-Change Chao. The file system in cloud shall incorporate decentralized load rebalancing algorithm to eliminate the performance [17]. In May 2013 a fully distributed load rebalancing algorithm is presented to cope with the load imbalance problem by Hung-Chang, Haiying Shen. This algorithm is a centralized approached in a production system and a competing system [18].

HADOOP DISTRIBUTED FILE SYSTEM
Recent trends in the analysis of big data sets from scientific applications show adoption of the Google style programming infrastructure, MapReduce [2]. Hadoop, which is a collection of open-source projects originated by "Doug Cutting in 2006" to apply the Google MapReduce programming framework across a distributed system [8]. It provides an easily obtained framework for distributed processing, and a number of open-source projects quickly emerged which leveraged this to solve very specific problems. Hadoop in a cloud computing environment supports the processing of large data sets in a distributed computing environment, primarily in data warehouse systems and plays an important role in support of big data analytics to understand the user behavior and their needs in web services [9]. HDFS stores file system and application data separately. HDFS also provides high throughput access to the application of data and it is suitable for the application that has large data sets. HDFS is highly fault-tolerant, which provides high throughput access to the application data and is a perfect application that has large data sets. It adopts the master and slave architecture.
HDFS cluster consists of DataNode and NameNode shown in Figure 2. NameNode which is a central server, also called as a Master server, is responsible for managing the file system namespace and client access to files and DataNode in the cluster node are responsible for files storage. In HDFS, a file is divided into one or more number of blocks for storing data [13].

WEB APPLICATION IN A CLOUD AND ARCHITECTURE DESIGN
In the following module, the schematic design of the architecture for a scaling structure and the dynamic scaling for a web application in cloud is designed. The structure is based on using a front-end load balancer to dynamically route user requests to backend, Master web servers that host the web application. The number of web servers should automatically scale according to the threshold on the number of current active sessions in each web server instance to maintain service quality requirements.
High speed data retrieval from cloud storage has been an active area of research. The Apache Hadoop project design, architecture which is based on the web server and application cluster in cloud environment was started with this as one aim in mind. We review here the basic details of the design architecture, apache load balancer and the details of the Master web server with the multi-level indexing. In the following module, the schematic design of the architecture for a scaling scenario and the dynamic scaling web application for the web in a Cloud is clustered.

ARCHITECTURE DESIGN
The data in Hadoop Distributed File System is scattered, searching and data retrieval is one of the most challenging tasks, so to overcome these tasks a searchable mechanism in HDFS has been implemented. A web server has been designed in the Map phase of MapReduce. The jetty web server is considered as a web interface. Web applications are generated in the HDFS and a web server is started in the form of Hadoop job by submitting our keys to URL Hadoop url/file/key. The Apache load balancer is used in between the client and server to balance the work load of the localhost because if one level is not sufficient, then the system will automatically expand to the second level of indexing.
For real time processing on Hadoop, a searchable mechanism is implemented in HDFS by creating a multilevel index in web server with multi-level index keys. To keep the work down, the load balancer should automatically be able to distribute load to the newly added nodes in the server. The load balancer is used to balance the workload across servers to improve its availability, performance and scalability. To be able to exploit the elasticity of a cloud infrastructure, the applications usually need to be able to scale horizontally, i.e. it must be possible to add and remove nodes offering the same capabilities as the existing ones. In such scenarios, a load balancer is usually used.
NameNode is divided into Master and Slave server. Master server contains multi -level index and slave have data and key index. In the server at the time of the data request, the key is being passed on multi level indexes. Indexing all the process is done by Master server and all retrieval process are done by slave serve. The overall view of the design architecture has been shown in the figure 3.

LOAD BALANCER
It is used to balance the workload across servers to improve its availability, performance and scalability. Its purpose is to improve the performance of the distributed system through an appropriate distribution of the application [17]. In a distributed system, it is possible for some computers to be heavily loaded while others are lightly loaded. In this situation system can lead to poor system. The goal of load balancing is to improve the performance by balancing the loads among computers.
The Apache load balancer will give better performance of the workload. These can be configured to know a certain number of workers and their host names, but no workers can be added automatically during runtime [14]. It is implemented in between clients and servers to balance the work load of the web server. These servers run on each NameNode and DataNode of which web application package is deployed on the HDFS [13].

LOAD BALANCING WITH THE MASTER WEB SERVER
A common approach is used in combination of the Apache module mod proxy [15] and mod proxy balancer [16]. After adding these modules to the Apache Web Server 2, a virtual host configuration has to be created that configures the load balancer and its balance members. By using the directive ProxySet, the load balancing method can be set to balance either by the number requests, by counting the bytes of the traffic, or by pending requests. By using the Balancer Member directive, a worker with the given URL can be introduced to the load balancer, including how much load it should receive.
The Master server runs on each NameNode and DataNode (Figure 4), web server application package is deployed on the HDFS. The web server in NameNode is divided into Master/slave architecture, according to HDFS storage features, it will store all the keys in the indexing form.
All client requests are first sent to the NameNode through URL Hadoop url/file/key, and Master server in NameNode will decide which the Master server either master/slave on DataNode to respond to the request according to the location information of web files stored in the multi-level indexing on NameNode, and then redirected URL to the node and request the same Uri, finally, a connection can be established between the current Master web server and the browser, and sending files and data between them. To be able to exploit the elasticity of a cloud infrastructure, the applications usually need to be able to scale horizontally, i.e. it must be possible to add and remove nodes offering the same capabilities as the existing ones. In such scenarios, a load balancer is usually used.
It is possible to add the new workers directly to the Master server configuration and starting the load balancer, a large number of virtual folders can be defined in the virtual host configuration. Then, whenever a worker registers at the load balancer, the htaccess rewriter writes a forward rule to the. htaccess file located in htdocs/virtual a request sent to, the URL path route/1 is redirected to the first URL specified in the htaccess file, a request sent to, the URL path route/2 to the second, and so on. Since then htaccess file is evaluated for each request, changing it at runtime allows additions as well as removal of workers. With these measures, it is possible to allow workers to register at the load balancer automatically upon their startup and shutdown, thus bypass the need to manually add or remove workers. Even the rules allow for the changes take effect during runtime. Further modifications of the load factor are possible by collecting monitoring data [11].
A starting load factor can be determined by a performance test. Load balancer knows the potential workload of all workers; it can calculate a load factor for each worker proportional to each worker's potential or monitored workload [5]. The features of load balancer are  If a server dies connection will be directed to the nearest server.
 Once the server comes back online it rejoins the cluster.
 It can be controlled to take into account machine difference.
 It supports complex topologies and failover configuration  It distributes the client request across the server, redirect to the localhost.

RESULT & ANALYSIS
In this module, for the implementation, we configured Hadoop with 6 DataNodes and one NameNode, 6 Task trackers and one job tracker. With each of the nodes we install the jetty server and connect it with Hadoop using eclipse. Jetty server is running on each of DataNode of Master server. Each jetty server works on specific key. Master server contains a list of keys which correspond to jetty server information. When a read request come from the clients via Master server then it does look up to find the jetty server for corresponding keys and then forward it to the corresponding server. For our experiments we use all systems with Core i7 2.93 GHz CPU, 8 GB DDR3 RAM, 1 TB hard drive. All systems are connected over a 1 Gbps switch.
Web applications are generated in the HDFS and a web server is started in the form of Hadoop job by submitting our keys to the URL of Hadoop i.e. Hadoop url/file/key. The key and value are submitted to the local host of a Hadoop URL in the file system of Master web server and read operations can be performed in the same URL. The read operation performed in Hadoop is done by Master web server through Uniform Resource Locator. To keep the work down, the load balancer should automatically be able to distribute load to the newly added nodes in the server.
When one Master Server (jetty server) is running and read operation is carried out from HDFS, it has been seen that the average time (seconds) keeps on increasing when data input is increased in HDFS. The average time taken for retrieving data in HDFS is shown in the figure 6 and is 4.2 seconds for 100MB data size, 6.8seconds for 1000MB, 17.3seconds for 10000MB and 24.7second for 100000MB data size. Increased of Master Server (jetty server) will give better performance for retrieving data through the Hadoop url / file/key. It has been seen that the average time (retrieving data) keeps on decreasing when data input is constant or increasing in HDFS. The Master web server (Jetty server) takes seconds to read a particular or text data from 100000 MB size of data which has been stored in the HDFS where the data are kept constant (100000MB). We have increased the number of servers from 1 to 6 servers for better performance in retrieving of text data from HDFS. The average time taken for retrieval of text data in HDFS by Master server is shown in Figure 7 and is 22.7 seconds, 17.8seconds, and 14.7seconds, 8.3seconds, 7.6seconds and 4.8seconds form 100000MB data size where data are kept constant and web servers are increasing.

CONCLUSION & FUTURE WORK
In this paper, we have given the schematic view of the designed architecture with effective structure to investigate the performance of Hadoop in high speed retrieval of data in a cloud environment. Apache Web Server a dynamic cloud-ready load balancer was presented as well. It was shown that the Master web server is a static load balancer when using one of the common load balancing modules. To avoid having to manually add workers to the load balancer configuration, we have also added a benchmarking and registration component to the workers.
The results shows that using this architecture in the Hadoop and making map phase as a web server, faster read operation for MapReduce programs can be achieved through URL. For large databases of data warehouse applications in cloud, searching process takes a very long time as the data is scattered. High sped retrieval of data can be particularly useful for real-time applications based on Hadoop where quick fetching and storage of data is necessary.
In future, experiments can be carried out on large datasets and some real-time applications to measure the usefulness of the proposed approach. This web server can conceptually be extended to provide dynamic load balancing capabilities. Apache Web Server cans also be used as a load balancer in combination with Apache Tomcat workers.


s2fieldsofstudy:
Computer Science
Mathematics

text:
COMPLEXITY OF FIRST-ORDER METHODS FOR DIFFERENTIABLE CONVEX OPTIMIZATION

This is a short tutorial on complexity studies for differentiable convex optimization. A complexity study is made for a class of problems, an "oracle" that obtains information about the problem at a given point, and a stopping rule for algorithms. These three items compose a scheme, for which we study the performance of algorithms and problem complexity. Our problem classes will be quadratic minimization and convex minimization in ℝn. The oracle will always be first order. We study the performance of steepest descent and Krylov spacemethods for quadratic function minimization and Nesterov’s approach to the minimization of differentiable convex functions.

INTRODUCTION
Due to the huge increase in the size of problems tractable with modern computers, the study of problem complexity and algorithm performance became essential. This was recognized very early by computer scientists and mathematicians working on combinatorial problems, and has recently become a central issue in continuous optimization. Complexity studies for these problems started in the former Soviet Union, and the main results are described in the book by Nemirovski & Yudin [14].
The special case of Linear Programming, which will not be tackled in this paper, initiated with Khachiyan [10], also in Russia in 1978, and had an explosive expansion in the West with the creation of interior point methods in the 80's and 90's. This paper starts with a brief introduction to the main concepts in the study of algorithm performance and complexity, following Nemirovski and Yudin, and then apply to the study of the convex optimization problem: minimize where f : R n → R is a continuously differentiable function.
In Section 2 we introduce the general framework for the study of algorithm performance and problem complexity and present a simple example.
We dedicate Section 3 to study the special case of convex quadratic functions, because they are the simplest non-linear functions: if a method is inefficient for quadratic problems, it will certainly be inefficient for more general problems; if it is efficient, it has a good chance of being adaptable to general differentiable convex problems, because near an optimal solution the quadratic approximation of the function uses to be precise. We study the performance of steepest descent and of Krylov space methods.
Section 4 will describe and analyze a basic method for unconstrained convex optimization devised by Nesterov [15], with "accelerated steepest descent" iterations. This method has become very popular, and the presentation and complexity proofs will be based on our paper [7].
Finally, we comment in Section 5 on improvements of this basic algorithm, presenting without proofs its extension to problems restricted to "simple sets" (sets onto which projecting a vector is easy).

SCHEMES, PERFORMANCE AND COMPLEXITY
A complexity study is associated with a scheme ( , O, τ ε ) as follows.
(i) is a class of problems. Examples: linear programming problems, unconstrained minimization of convex functions.
(ii) O is an oracle associated to .
The oracle is responsible for accessing the available information O(x) about a given problem in at a given point x.
• The numerical performance is a bound on the number of arithmetical operations needed in the worst case. The numerical performance is usually proportional to the iteration performance for each given algorithm. In this paper we only study the iteration performance of algorithms.
• The complexity of the scheme ( , O, τ ε ) is the performance of the best possible algorithm for the scheme. It is frequently unknown, and finding it for different schemes is the main purpose of complexity studies.
The performance of any algorithm for a scheme gives an upper bound to its complexity. A lower bound to the complexity may sometimes be found by constructing an example of a (difficult) problem in and finding a lower bound for any algorithm based on the same oracle and stopping rule. This will be the case in the end of Section 3.
If the performance of an algorithm for a scheme matches its complexity or a fixed multiple of it, it is called an optimal algorithm for the scheme.

First-order algorithms:
In most of this paper we study first-order algorithms for solving the problem minimize where f : R n → R is a differentiable function. The problem classes will be the special cases of quadratic and convex functions.
A first-order algorithm starts from a given point x 0 and constructs a sequence (x k ) using the where span(S) stands for the subspace generates by S.
In particular, the most well-known minimization algorithm is the steepest descent method, in which where λ k is a steplength. Each different choice of steplength (the rules of the method) defines a different steepest descent algorithm. This will be studied ahead in this paper.
Remark: In our algorithm model we used a single oracle, but there may be more than one.
and O 0 may be called more than once in each iteration. This is the case when line searches are used. The performance evaluation must then be adapted.

The notation O(·).
Given two real positive functions g(·) and h(·), we say that g = O(h) if there exists some constant K > 0 such that g(·) ≤ K h(·). This notation is very useful in complexity studies. For example, we shall prove that a certain steepest descent algorithm stops for k ≤ C 4 log 1 ε , where C is a parameter that identifies the problem in and ε is the precision. We may write k = C O(log(1/ε)), ignoring the coefficient 1/4.

Example: root of a continuous function
Here we present a simple example to illustrate how a complexity analysis works. Consider the following example of ( , O, τ ε ) given by: : Given a continuous function f : Remark: The stopping rule above is obviously not computable. We shall use a practical rule that implies τ ε .

Algorithm 2. Bisection
Performance: the following facts are straightforward at all iterations: If the algorithm does not stop at iteration k, then 2 −k > ε, and then k < log 2 (1/ε). We conclude that the stopping rule will be satisfied for k = log 2 (1/ε) , where r is the smallest integer above r. Thus that the performance of the scheme above is k = log 2 (1/ε) = O(log(1/ε)).
It is possible to prove that this is the best possible algorithm for this scheme, and hence the complexity of the scheme is this performance.

Remarks:
(i) Note that the only assumption here was the continuity of f . With stronger assumptions (Lipschitz constants for instance), better algorithms are described in numerical calculus textbooks.
(ii) The rules of the method are in the bisection calculation. Only the present oracle information O(m) is used at step k.

MINIMIZATION OF A QUADRATIC FUNCTION: FIRST-ORDER METHODS
Quadratic functions are the simplest nonlinear functions, and so an efficient algorithm for minimizing nonlinear functions must also be efficient in the quadratic case. On the other hand, near a minimizer, a twice differentiable function is usually well approximated by a quadratic function. A quadratic function is defined by where c ∈ R n and H is an n × n symmetric matrix. Then for x ∈ R n , If x * is a minimizer or a maximizer of f , then and hence finding an extremal of f is equivalent to solving the linear system H x * = −c, one of the most important problems in Mathematics.
The behavior of a quadratic function depends on the eigenvalues of its Hessian H . Since H is symmetric, it is known that H has n real eigenvalues which may be associated with n orthonormal (mutually orthogonal with unit norm) eigenvectors v 1 , v 2 , . . . , v n . There are four cases, represented in Figure 1:  (iv) If c T v i < 0 for some i = 1, . . . , k, then f is unbounded below.
In this section, we study the following scheme: : the class of quadratic functions that are bounded below (cases (i) and (iii) above). A function in has at least one minimizer x * . Without loss of generality, the study of algorithmic properties (not the implementation) may assume that x * = 0, and so the function becomes τ ε : Given an initial point x 0 ∈ R n , two rules will be used in the analysis: These rules are not implementable, because they require the knowledge of x * , but are very useful in the performance analysis.
Simplification: As we explained above, we assume that f (·) has a minimizer x * = 0. After performing the analysis with this simplification, we substitute x − x * for x. A further simplification may be done by diagonalizing H , also without loss of generality.

Steepest descent algorithms
In the first half of the 19 th century, Cauchy found that the gradient ∇ f (x) of a function f is the direction of maximum ascent of f from x, and stated the gradient method. It is the most basic of all optimization algorithms, and its performance is still an active research topic.

Algorithm 3. Steepest descent algorithm (model)
Data: Steplengths: Each different method for choosing the steplengths λ k defines a different steepest descent algorithm. Let us describe the two best known choices for the steplengths: • The Cauchy step, or exact step, the unique minimizer of f along the direction −g with g = ∇ f (x k ). The steplength is computed by setting ∇ f (x k − λ k g)⊥g and simplifying, which results in • The short step: λ k < 2/μ n , a fixed steplength.

Complexity results
Now we study the iteration performance of the steepest descent methods with these two steplength choices for minimizing a strictly convex quadratic function (case (i)). Given ε > 0 and In both cases the algorithm stops in O(C log(1/ε)) iterations, where C = μ n /μ 1 . At this moment the following question is open: find a steepest descent algorithm (by a different choice of λ k ) with performance O( √ C log(1/ε)). This performance is achieved in practice for "normal problems" (but not for particular worst case problems) by Barzilai-Borwein and spectral methods, described in [3]. Theorem 1. Let C = μ n /μ 1 ≥ 1 be the condition number of H . The iteration performance of the steepest descent method with Cauchy steplength for minimizing f starting at x 0 ∈ R n and with stopping criterion (5) is given by Proof. We begin by stating a classical result for the steepest descent step, which is based on the Kantorovich inequality and is proved for instance in [12, p. 238], Using this recursively, we obtain is an increasing function and that for t > 1, If τ ε is not satisfied at an iteration k, then by Example. In this example we show that the bound obtained in Theorem 1 is sharp, i.e., it cannot be improved. Take the following problem in R 2 : Assume that the initial point of some iteration has the shape x = (C, 1) z, for some z ∈ R. Then Computing the steplength λ by (4), we obtain λ = 2/(C + 1), and then the next iterate will be It follows that and this will be repeated on all iterations, with the worst possible performance as in Theorem 1.

Theorem 2.
Let C = μ n /μ 1 ≥ 1 be the condition number of H . The iteration performance of the steepest descent method with short steps λ k = 1/μ n , for minimizing f starting at x 0 ∈ R n and with stopping criterion (5) is given by

Proof.
A simplification in the analysis can be made by diagonalizing the matrix H by using the orthonormal matrix whose columns are the eigenvectors of H . Thus, we can consider, without loss of generality, that H = diag(μ 1 , . . . , μ n ). Given x 0 ∈ R n , by the steepest descent algorithm with short steps, Thus, for all i = 1, . . . , n, Consequently, by the definition of f , Proceeding like in the proof of Theorem 1, we obtain So, if τ ε is not satisfied at an iteration k, then k < C 2 log 1 ε , completing the proof.

Remarks:
• When the short steps 1/μ n are used, the result is that for • The diagonalization of H can be made without loss of generality for the performance analysis, as we did in the proof of Theorem 2. This leads to an interesting observation about the constant C, for the case in which there are null eigenvalues (case(iii)). Assuming that μ 1 = μ 2 = . . . = μ p = 0, we see that for i = 1, . . . , p, (∇ f (x)) i = 0, and the variables x i remain constant forever having no influence on the performance. The bounds in Theorems 1 and 2 remain valid for C = μ n /μ p+1 .

Krylov methods
Krylov space methods are the best possible algorithms for minimizing a quadratic function using only first-order information. Let us describe the geometry of a Krylov space method for the quadratic (2).
• Starting at a point x 0 , define the line This is actually the Cauchy step. We may write and the next iterate will be This is a two-dimensional problem.
• k-th step: adding ∇ f (x k−1 ) to the set of gradients, we construct the set and the next point will be It is then clear that x n is an optimal solution because V n = R n . This gives us a first performance bound k ≤ n for the Krylov space method. This bound is bad for high-dimensional spaces.
Main question: how to solve (P k ). Without proof (see for instance [15,20]), it is known that the directions (x k − x k−1 ) are conjugate, and any conjugate direction algorithm like Fletcher-Reeves [4,18] solves (P k ) at each iteration with about the same work as in the steepest descent method.
From now on we do a performance analysis of the Krylov space method, with stopping criterion A result for the relative error bound will also be discussed in the end of the section. The analysis is quite technical and will result in (16). Definition 1. Given x 0 ∈ R n and k ∈ N, define the k-th Krylov space by Consider V k = x 0 + K k and define the sequence (x k ) by Let P k be the set of polynomials p : R → R of degree k such that p(0) = 1, i.e, P k = 1 + a 1 t + a 2 t 2 + · · · + a k t k | a i ∈ R, i = 1, . . . , k .
From now on we deal with matrix polynomials, setting t = H .

Lemma 1.
A point x ∈ V k if, and only if, x = p(H )x 0 for some polynomial p ∈ P k . Furthermore,

Proof.
A point x ∈ V k if, and only if, where p ∈ P k . Furthermore, As H is symmetric, p(H ) T H = H p(H ), completing the proof.

Lemma 2. For any polynomial p ∈
Proof. Consider an arbitrary polynomial p ∈ P k . From Lemma 1, the point x = p(H )x 0 belongs to V k . As Using (8) we complete the proof.
Proof. As A is a symmetric matrix, there exists an orthogonal matrix P such that A = P D P T , with D = diag(λ 1 , λ 2 , . . . , λ n ). If q(t ) = a 0 + a 1 t + · · · + a k t k , then q(H ) = a 0 I + a 1 P D P T + · · · + a k (P D P T ) k = P a 0 I + a 1 D + · · · + a k D k P T .

Chebyshev Polynomials
The Chebyshev polynomials will be needed in the performance analysis of Krylov methods.
The next lemma shows that T k is, in fact, a polynomial (even though it does not look like one).

Lemma 5.
If T k (t ) = a k t k + · · · + a 2 t 2 + a 1 t + a 0 , then a k = 2 k−1 . Furthermore, Proof. We prove by induction. The results are trivial for k = 0 and k = 1. Suppose that the results hold for all natural number less than or equal to k. Using the induction hypothesis, consider leading to the first statement. Suppose that (k + 1) is even. Then k is odd and (k − 1) is even. Thus, by induction hypothesis, T k has only odd powers of t and T k−1 has only even powers. In this way, by (9), T k+1 has only even powers of t . Furthermore, its independent term is

COMPLEXITY OF FIRST-ORDER METHODS FOR DIFFERENTIABLE CONVEX OPTIMIZATION
On the other hand, if (k + 1) is odd, then k is even and (k − 1) is odd. Again by the induction hypothesis, T k only has even powers of t and T k−1 has only odd powers. Thus by (9), T k+1 has only odd powers of t . Furthermore, its linear term is completing the proof.
The next lemma discusses a relationship between a Chebyshev polynomial of odd degree and polynomials of the set P k , defined in (7). Lemma 6. Consider L > 0 and k ∈ N. Then there exists p ∈ P k such that, for all t ∈ [0, L], Proof. By Lemma 5, for all t ∈ [−1, 1], we have where the polynomial in parentheses has only even powers of t . So, for all t ∈ [0, L], Defining we complete the proof.

Complexity results
Now we present the main result about the performance of Krylov methods for minimizing a convex quadratic function. This result is based on [19, Thm. 3, p. 170].
We use the matrix norm defined by Theorem 3. Let μ n be the largest eigenvalue of H and consider the sequence (x k ) defined by (6).
and f (x k ) − f * ≤ ε is satisfied for Proof. Without loss of generality, assume that x * = 0. By Lemma 2, for all polynomial p ∈ P k , But, from Lemma 3 and (10), Considering the polynomial p ∈ P k given in Lemma 6 and using the fact that all eigenvalues of H belong to (0, μ n ], we have proving (11). If τ ε is not satisfied at an iteration k, then f (x k ) > ε and consequently ε < μ n x 0 2 2(2k + 1) 2 < μ n x 0 2 8k 2 which implies (12) and completes the proof.
Performance of the method for the relative error bound: A similar analysis for τ ε given by (5), also using Chebyshev polynomials, can be done using the condition number C. This is done in [14,23], and the result is clearly better than the best performance of the steepest descent algorithm for the steplength rules studied above, and for reasonable values of μ 1 , better than (12).
Complexity bound. The Krylov space methods uses at each iteration all the information gathered in the previous steps, and hence it seems to be the best possible algorithm based on first order information. In fact, Nemirovskii & Yudin [14] prove that no algorithm using a first order oracle can have a performance more than twice as good as the Krylov space method.
For methods based on accumulated first order information there is a negative result described by Nesterov [15, p. 59]: he constructs a quadratic problem (which he calls "the worst problem in the world") for which such methods need at least iterations to reach τ ε .
We conclude that the best performance for a first order method must be between the bounds (12) and (15). So the complexity of the scheme is

CONVEX DIFFERENTIABLE FUNCTIONS: THE BASIC ALGORITHM
In this section we study the performance of algorithms for the unconstrained minimization of differentiable convex functions. Quadratic functions are a particular case, and hence the performance bounds for first order algorithms will not be better than those found in the former section.
The role played by μ n in quadratic functions will be played by a Lipschitz constant L for the gradient of f (indeed, for a quadratic function the largest eigenvalue is a Lipschitz constant for the gradient), and we shall see that there are optimal algorithms, i.e., algorithms with the performance given by (16) with μ n replaced by L. These algorithms were developed by Nesterov [15], and are also studied in our papers [7,8].
Consider the scheme ( , O, τ ε ) where : the class of minimization problems of a convex continuously differentiable function f , with a Lipschitz constant L > 0 for the gradient. It means that for all x, y ∈ R n , Simple quadratic functions. The following definition will be useful in our development: we shall call "simple" a quadratic function φ : R n → R with ∇ 2 φ(x) = γ I , γ ∈ R, γ > 0. The following facts are easily proved for such functions: • φ(·) has a unique minimizer v ∈ R n (which we shall refer as the center of the quadratic), and the function can be written as • Given and

The algorithm
We now state the main algorithm and then study its properties. We include in the statement of the algorithm the definitions of the relevant functions (approximations of f (·) and the simple quadratic defined below).
We begin by summarizing the geometrical construction at an iteration k, represented in Figure 2. The iteration starts with two points x k , v k ∈ R n and a simple quadratic function whose global minimizer is v k . A point y k = x k + α(v k − x k ) is chosen between x k and v k . The choice of α is a central issue, and will be discussed later. All the action is centered on y k , with the following construction: • Take a gradient step from y k , generating x k+1 .

Analysis of the algorithm
The most important procedure in the algorithm is the choice of the parameter α k , which then determines y k at each iteration. The choice of α k is the one devised by Nesterov in [15, Scheme (2.2.6)]. Instead of "discovering" the values for these parameters, we shall simply adopt them and show their properties.
Once y k is determined, two independent actions are taken: (i) A steepest descent step from y k computes x k+1 .
(ii) A new simple quadratic is constructed by combining φ k (·) and the linear approximation Our scope will be to prove two facts: From these facts we shall conclude that f (x k ) → f * with the same speed as γ k → 0, which easily leads to the desired performance result.
The first lemma shows our main finding about the geometry of these points. All the action happens in the two-dimensional space defined by x k , v k , v k+1 . Note the beautiful similarity of the triangles in Figure 3.

Lemma 7.
Consider the sequences generated by Algorithm 4. Then for k ∈ N, Proof. By the algorithm, we know that Lα 2 k = γ k+1 , and completing the proof.

Lemma 8. Consider the sequences generated by Algorithm 4. Then for k ∈ N,
Proof. By the definition of φ α k , Using this, the definition of and the fact that α k ∈ (0, 1), we have By the definition of y k in the algorithm, v Substituting this in (21), we complete the proof.

Lemma 9. Consider the sequences generated by Algorithm 4. Then for k ∈ N,
Proof. The first inequality follows trivially from the convexity of f and the definition of u.
Since x k+1 and v k+1 are respectively global minimizers of u(·) and φ α k (·), we have from (18) that, for all x ∈ R n , As f (y k ) = u(y k ) and, from the last lemma, u(y k ) ≤ φ α k (v k ), we only need to show that The construction is shown in Fig. 3: since, by Lemma 7, Using this, (24) and the fact that by construction, proving the second inequality of (22).

Lemma 10.
For any x ∈ R n and k ∈ N, Proof. By the definition of φ α k and the fact that Subtracting f (x) in both sides, using (23) and the definition of γ k+1 , we have Using this recursively, we get the result and complete the proof.

Complexity
The following lemma was proved by Nesterov [15, p. 77] with a different notation.
Theorem 4. Consider the sequences generated by Algorithm 4 and assume that x * is an optimal solution. Then for k ∈ N, Proof. From Lemma 10,(25) holds in particular at x * , Using the fact that f (x k ) = φ k (v k ) ≤ φ k (x * ) and the definition of φ 0 , we get, Since x * is a minimizer of the convex function f , Applying this and the result of Lemma 11 in (28), As γ 0 = L, we have (26). If τ ε is not satisfied at an iteration k, then f (x k ) − f * > ε and consequently which implies (27) and completes the proof.
So, the iteration performance of Algorithm 4 is which corresponds to the complexity (16) for quadratic performance. Then, the algorithm is optimal.

CONVEX DIFFERENTIABLE FUNCTIONS: ENHANCED ALGORITHMS
The algorithm presented in the former section may be extended in several ways: the need for a previous knowledge of a Lipschitz constant L may be eliminated, a strong convexity constant akin to the smallest eigenvalue in the quadratic case may be used, and the algorithm may be extended to problems constrained to so-called simple sets. These extensions are treated in our paper [8] and in references therein.
In this section we state the extension of the basic algorithm to problems with simple constraints, without proofs. Consider the scheme ( , O, τ ε ) where : the class of problems where ⊂ R n is a closed convex set and f : R n → R is convex and continuously differentiable, with a Lipschitz constant L > 0 for the gradient. We assume that is a "simple" set, in the following sense: given an arbitrary point x ∈ R n , an oracle is available to compute P (x) = argmin y∈ x − y , the orthogonal projection onto the set . We now state the basic algorithm for constrained problems, without proofs. We keep in the statement the definition of the functions used in the analysis made in [8].

Algorithm 5.
Data: Consider the sequences generated by Algorithm 5. Then, as proved in [8,Thm. 2.6], at any iteration k before stopping, and hence This expression is similar to (27). In fact, if x * is a global minimizer, then may be introduced in the last expression, retrieving (27).
Estimations of the Lipschitz constant. Both Algorithms 4 and 5 and the algorithms discussed by Nesterov in [15, Chapter 2] make explicit use of a Lipschitz constant L for the function gradient. In [16], Nesterov describes a method for a more general problem, easily applied to the situations studied in this paper. This method includes a scheme for estimating the Lipschitz constant. In [7,8], the authors eliminate the use of L at the cost of an extra imprecise line search, and obtain an algorithm which keeps the optimal complexity properties and also inherits the global convergence properties of the steepest descent method for general continuously differentiable optimization. Besides this, the algorithm takes advantage of the knowledge of the strong convexity constant for the function and develop in [7] an adaptive procedure for estimating it. In another context -constrained minimization of non-smooth homogeneous convex functions -Richtárik [21] uses an adaptive scheme for guessing bounds for the distance between a point x 0 and an optimal solution x * . This bound determines the number of subgradient steps needed to obtain a desired precision.
Extensions. Nesterov's approach is applied to penalty methods by Lan, Lu & Monteiro [11], and interior descent methods based on Bregman distances are described by Auslender & Teboulle [1]. This method has been generalized to a non-interior method using projections by Rossetto [22]. Results for higher order methods are discussed in Nesterov & Polyak [17]. Accelerated versions of first-order algorithms following Nesterov's approach were developed by Monteiro, Ortiz & Svaiter [13] and by Beck & Teboulle [2], with improved performance for benchmark problems.

CONCLUSIONS
In this paper we described what we believe to be the basic results in the study of algorithm performance and problem complexity for the minimization of convex functions, both unconstrained and with simple constraints.
Algorithms with proved low worst-case performance are not necessarily efficient for practical problems. Khachiyan's algorithm [10] for linear programming is very inefficient, but had a great impact on the development of both continuous and discrete optimization. Karmarkar's algorithm [9] for linear programming improved Khachiyan's performance bound, and his bound was again improved later (see [6]). The effort to improve complexity led to better algorithms, which are nowadays used for solving large scale linear and quadratic in many domains. In fact, the largest linear programming problem treated up to now had 1.1 billion variables and 380 million constraints, solved by Gondzio & Grothey [5] using an interior point algorithm.
The conjugate gradient algorithm (Krylov space method) has optimal performance for quadratic problems, but its extension to more general problems is not straightforward. It was superseded by quasi-Newton methods, which are more efficient for non-quadratic problems, but coincide with it in the convex quadratic case. Note that the conjugate gradient method was not motivated by the complexity study, which came later.
Accelerated gradient methods are now in the phase of development, and we are not aware of any extensive comparison with classical algorithms. Research in this field is presently very active, and it is not clear to what classes of problems this approach will be applied and which methods will be the winners in practical applications to large-scale problems.