Biological sequences like DNA and proteins are shaped by evolution, undergoing continuous "edit operations" such as substitutions, insertions, and deletions. While standard Convolutional Neural Networks (CNNs) excel at capturing "shift invariance"—finding a pattern regardless of its starting position—they struggle significantly with "edit invariance." Standard convolution operations essentially compute a dot product, which corresponds to Hamming distance and only accounts for substitutions. If a single amino acid is inserted into a protein sequence, the entire reading frame shifts, causing standard CNN filters to fail.
This paper introduces architectures that natively understand these evolutionary "glitches," proposing two primary approaches: a differentiable version of the classic Needleman-Wunsch alignment algorithm, and a theoretical framework demonstrating how deep CNNs with concatenations can act as powerful regular expression recognizers.
Edit Invariant Neural Networks (EINNs)
To directly incorporate edit operations into neural networks, the authors propose the Edit Invariant Neural Network (EINN). This approach takes the Needleman-Wunsch (NW) algorithm—a foundational dynamic programming method in bioinformatics used for global sequence alignment—and transforms it into a differentiable neural network layer.
By replacing the "hard" maximum operations typically found in the NW dynamic programming table with a "smoothed" softmax version (conceptually similar to SoftDTW), the model can backpropagate gradients through the entire alignment process. This innovation allows the network to learn optimal gap costs and substitution scores directly from the data, rather than relying on manually defined scoring matrices. Interestingly, the authors prove that as the gap cost in the EINN model approaches infinity (making insertions and deletions impossible), the EINN mathematically converges to a standard CNN convolution, positioning EINNs as a direct generalization of CNNs for sequence data.
Deep CNNs as Regex Recognizers
Alongside EINNs, the authors provide a theoretical analysis showing that standard CNNs can handle insertions and deletions, provided they are sufficiently deep and utilize concatenations (similar to DenseNet architectures).
They demonstrate that a CNN can emulate a regular expression (excluding Kleene stars). In this framework, different network layers recognize specific sub-motifs. Skip-connections and concatenations act as logical "OR" and "AND" gates, allowing the network to "skip" characters or combine patterns. This effectively mimics the behavior of an alignment algorithm, recognizing "gapped" motifs (e.g., "Pattern A followed by Pattern B, with or without a character in between").
Key Results and Trade-offs
The models were evaluated on protein secondary structure prediction (classifying parts of a protein as a helix, sheet, or coil) using the widely-used CB513 benchmark dataset and a rigorously filtered CB6133 training set.
- State-of-the-Art Performance: A proposed 12-block CNN model achieved 71.5% accuracy on the CB513 dataset, establishing a new state-of-the-art for non-ensemble models at the time of publication and outperforming complex RNN and CNN architectures.
- Data Efficiency: EINNs provide a strong "inductive bias" by being hard-coded to understand alignment. In experiments using only 1% or 2% of the training data, the EINN model significantly outperformed standard CNNs, confirming that explicitly modeling edit operations helps networks learn efficiently from limited biological samples.
- Computational Trade-offs: While EINNs are highly effective on small datasets, they are computationally expensive. The dynamic programming requires $O(k^2)$ complexity for a kernel size $k$ and is harder to parallelize on GPUs. For massive datasets, deep CNNs with concatenations can implicitly learn these alignment patterns while remaining much faster to compute.
Limitations and Future Directions
Despite the strong results, the approaches have limitations. The computational complexity of EINNs makes them over ten times slower than standard CNNs for a kernel size of 5, restricting their use in very deep architectures. Furthermore, the theoretical proof for CNNs as regex recognizers is limited to expressions without Kleene stars (infinite repetitions). Extending this to handle repetitive biological structures, like leucine zippers, remains an open challenge. Finally, the current EINN relies on global alignment; future work could integrate local alignment (Smith-Waterman) or heuristic-based alignments like BLAST into the differentiable framework.
Summary updated