TL;DR
This paper introduces a novel method for classifying protein sequences into families by combining motif information and amino acid composition. They leverage Principal Component Analysis (PCA) for dimensionality reduction and a hybrid Genetic Algorithm-Support Vector Machine (GA/SVM) to select the most informative features and optimize the classifier, achieving improved accuracy over existing methods.
What Problem Does This Paper Address?
Accurately classifying protein sequences into functional families is crucial for understanding their roles in biological processes. Traditional methods often rely on sequence similarity or generative models that build profiles for individual families. While discriminative approaches like Support Vector Machines (SVMs) have shown promise, their performance heavily depends on the quality of features used to represent the protein sequences. This paper addresses the challenge of effectively extracting and selecting these features, aiming to improve classification accuracy by considering both local (motif) and global (compositional) sequence characteristics.
Methods
The authors propose a multi-stage approach:
- Feature Vectorization: Each protein sequence is first converted into a fixed-dimensional vector. This vector combines:
- Motif Content: Presence or absence of known protein motifs from the PROSITE database (1744 features).
-
Protein Composition: Frequency of each of the 20 amino acids (20 features). This results in an initial feature vector of 1764 dimensions.
-
Dimensionality Reduction with PCA: To handle the high dimensionality and potential redundancy, Principal Component Analysis (PCA) is applied. This projects the feature vectors into a lower-dimensional "eigen-space," represented by eigenvectors of the covariance matrix. A large dimensionality (1000) is initially chosen for this eigen-space.
- Hybrid GA/SVM for Feature Selection and Hyperparameter Optimization: A key novelty is the use of a hybrid Genetic Algorithm (GA) and Support Vector Machine (SVM) approach.
- GA: Acts as the search mechanism. Chromosomes in the GA population represent potential feature subsets (binary encoding for feature selection) and the SVM's regularization parameter (C) (encoded as powers of 10).
- SVM: Used within the GA's fitness function to evaluate the quality of each chromosome. It performs classification using the selected features and optimized parameter.
- Fitness Function: Combines classification accuracy (from SVM's five-fold cross-validation) and the number of features used, prioritizing accuracy.
- Genetic Operators: Tournament selection, uniform crossover, and mutation are employed to evolve the population.
- Classification: Once the optimal feature subset and SVM parameters are identified by the GA/SVM, a final SVM classifier is trained and used to classify unseen protein sequences.
Datasets
The paper uses two primary datasets for evaluation:
- PIR Database: Protein sequences from the Protein Information Resource (PIR) were used for initial experiments. Six protein superfamilies were used as positive datasets, and one as a negative dataset.
- SCOP Database: The Structural Classification of Protein (SCOP) database (version 1.53) was used for more extensive evaluation, as described by Liao and Noble (2003). Sequences were filtered using an E-value threshold of 10⁻²⁵, resulting in 4352 sequences grouped into 54 families.
Key Insights and Ideas
- Synergy of Motif and Composition: Combining both motif presence/absence and amino acid composition provides a richer representation of protein sequences than either feature type alone, leading to improved classification.
- PCA as a Preprocessing Step: PCA effectively reduces dimensionality and normalizes features, creating an "eigen-space" that is more amenable to feature selection and potentially reveals underlying structural relationships.
- GA/SVM for Efficient Feature Engineering: The hybrid GA/SVM approach is powerful because it simultaneously searches for the most discriminative features and optimizes the classifier's key hyperparameter (C). This avoids manual tuning and ensures features are selected in the context of an optimized classifier.
- Feature Selection is Crucial: The results strongly suggest that selecting a smaller, biologically relevant subset of features from the PCA-transformed space significantly improves classification accuracy and provides a more concise representation of protein families.
- Consistency in Feature Distribution: Figure 9 shows that selected features exhibit similar distributions in training and testing sets (both positive and negative), indicating that the selected features are robust and generalize well.
Key Results
- Improved Accuracy: The proposed PCA+GA+SVM method consistently outperformed baseline methods like PSI-BLAST, C4.5 decision trees, and HMMer in terms of recognition rates across various protein superfamilies.
- Significant Feature Reduction: The method achieved substantial feature reduction, with feature numbers decreasing by 52.9-62.3% (Experiment I) and 50-56.9% (Experiment II) compared to the complete eigen-feature sets, while simultaneously improving accuracy.
- Superiority over SVM-pairwise: In Experiment II, the PCA+GA+SVM method showed better performance than SVM-pairwise across almost all families, both in terms of ROC scores and median False Positive Rates (RFP).
- Weighting Parameter 'w': The study found that a larger weight 'w' for the number of features in the fitness function led to smaller feature sets but worse recognition rates, suggesting the chosen weight (4x10⁻⁵) strikes a good balance.
Limitations and Future Work
- Computational Cost: While effective, the GA/SVM approach can be computationally intensive due to the iterative nature of GA and the SVM evaluations within its fitness function.
- Choice of Eigen-space Dimensionality: The paper mentions that determining the optimal number of principal components can be subjective. While they chose 1000, further investigation into optimal dimensionality selection could be beneficial.
- Future Work: The authors imply that their method is effective and could be applied to other biological sequence classification tasks. The robustness demonstrated in Figure 9 suggests potential for further exploration of the biological interpretability of the selected features.
Summary updated