TL;DR
This paper introduces "Nepal," a novel pairwise profile alignment tool that optimizes its scoring function using a derivative-free neural network approach. This new scoring function significantly improves alignment sensitivity and precision, particularly for remote homologous sequences, by better capturing non-linear relationships between protein profiles.
What Problem Does This Paper Address?
Accurately aligning protein sequences is fundamental to understanding their function and evolutionary relationships. Profile-based alignment methods, which use Position-Specific Scoring Matrices (PSSMs) to represent sequence families, are highly effective. However, the scoring functions used to compare these profiles within dynamic programming algorithms (like cosine similarity and correlation coefficient) are often linear and may fail to capture complex, non-linear relationships between amino acid probabilities at different positions. This limitation hinders the accurate alignment of distantly related proteins, often referred to as the "twilight zone" of sequence similarity. The authors aim to address this by developing a more sophisticated scoring function that can learn these non-linear patterns.
Methods
The core innovation lies in the development of a derivative-free neural network for optimizing the scoring function. Traditional neural networks rely on backpropagation, which requires a differentiable cost function. Since the "correct" scoring function for profile alignment is unknown, a direct cost function for supervised learning is unavailable. To overcome this, the authors combined a neural network with an evolutionary strategy optimization method, specifically the Covariance Matrix Adaptation Evolution Strategy (CMA-ES).
Here's how it works:
- Input: Two Position-Specific Scoring Vectors (PSSVs), representing two positions from different protein profiles, are concatenated into an input vector for the neural network.
- Neural Network Architecture: A simple feed-forward neural network with one hidden layer is used. The network learns weights ($W_{1a}, W_{1b}, b_1, W_2, b_2$) to produce a "score" representing the similarity between the two PSSVs.
- Derivative-Free Optimization: Instead of backpropagation, CMA-ES is used to search for the optimal network weights. This method adapts its search strategy based on the performance of a population of candidate solutions.
- Cost Calculation: The neural network's output score is used within a standard dynamic programming algorithm to generate a pairwise alignment. This alignment is then compared to a known "correct" (reference) alignment. The cost is calculated as 1 minus the alignment sensitivity, aiming to minimize this difference.
- Gap Penalty Optimization: The open and extension gap penalties for the dynamic programming algorithm were also optimized alongside the neural network weights.
The resulting optimized scoring function is implemented as a simple matrix operation, making it easy to integrate into existing alignment tools. The tool developed using this novel scoring function is named Nepal.
Datasets
The study utilized the SCOP40 (1.75 release) dataset, a non-redundant subset of protein domain sequences with pairwise sequence identity less than 40%. This dataset was chosen specifically to focus on improving remote homology alignment.
- Learning Dataset: 3,726 sequences.
- Test Dataset: 6,843 sequences.
To construct PSSMs and reference alignments, pairs of sequences were randomly extracted from superfamilies, ensuring they belonged to the same family to obtain reliable reference alignments. This resulted in:
- Learning Set Pairs: 1,721 sequence pairs.
- Test Set Pairs: 3,195 sequence pairs.
The test dataset was further categorized into "remote" (0-20% identity) and "medium" (20-40% identity) subsets to evaluate performance across different levels of sequence similarity.
Key Insights and Ideas
- Beyond Linearity: The most significant insight is that linear scoring functions (like cosine similarity and correlation coefficient) are suboptimal for profile alignment, especially for remote homologs. Non-linear relationships between profile positions are crucial for accurate alignment.
- Derivative-Free Learning for Unknown Objectives: The successful application of CMA-ES for optimizing a scoring function where a direct cost function is not available demonstrates a powerful approach for tackling problems with implicit objectives.
- Interior Residues Matter More for Remote Alignment: The analysis of connection weights revealed that residues tending to be buried within the protein's hydrophobic core (higher interior propensity) were assigned higher importance by the learned scoring function. This aligns with the idea that interior residues are less susceptible to mutation and thus more conserved in distantly related proteins, making them better indicators of homology.
- Reduced Overlap Improves DP: The new scoring function leads to fewer overlapping similarity scores compared to correlation coefficient. This is beneficial for dynamic programming, as it reduces ambiguity in selecting the optimal alignment path.
Key Results
- Improved Alignment Quality: Nepal significantly improved both alignment sensitivity and precision compared to existing methods, including profile comparison with correlation coefficient and sequence comparison methods like MIQS and BLOSUM62.
- Remote Homology Advantage: The improvements were most pronounced for the "remote" subset of sequences (0-20% identity), with Nepal achieving approximately 4% higher sensitivity and 1% higher precision than the best existing methods.
- Statistical Significance: These improvements were statistically significant according to Wilcoxon signed rank tests with Bonferroni correction.
- Optimized Gap Penalties: The optimized gap penalties for Nepal were found to be approximately -1.7 for open gaps and -0.2 for extension gaps.
Limitations and Future Work
- Computational Cost: The derivative-free neural network approach, while effective, required substantial computational resources, limiting the number of training epochs that could be performed. The authors could not definitively confirm convergence due to computational constraints.
- Limited Environment: The authors mention that their limited computational environment restricted the scope of their learning experiments.
- Future Directions: The authors suggest that Nepal could be further applied to improve the performance of distant homology detection and multiple sequence alignment for remote homologous sequences. They also provide the source code and learned parameters for community use.
Summary updated