TL;DR
This paper introduces fastISM, a novel algorithm that significantly speeds up in-silico saturation mutagenesis (ISM) for convolutional neural networks (CNNs) by over 10x. By identifying and eliminating redundant computations within CNN layers during the mutation analysis, fastISM makes this powerful interpretability technique computationally feasible for large-scale genomic analyses and competitive with, or even superior to, backpropagation-based methods.
What Problem Does This Paper Address?
Deep learning models, particularly CNNs, have become powerful tools for understanding biological sequences like DNA, predicting their functional roles. To interpret why these models make certain predictions, researchers use feature attribution methods. In-silico saturation mutagenesis (ISM) is a popular method that works by systematically mutating each character in a sequence and observing how the model's output changes. This helps identify which parts of the sequence are most important for the prediction. However, the major bottleneck for ISM is its extreme computational cost. It requires running the entire deep learning model multiple times for every possible mutation at every position in a sequence, making it prohibitively slow for large datasets or complex models. This paper aims to overcome this computational hurdle, making ISM a more practical tool for genomic sequence analysis.
Methods
The core innovation of fastISM lies in its exploitation of the computational structure of CNNs. The authors observed that:
- Convolutional layers dominate computation: The majority of the computational cost in CNNs during ISM comes from these layers.
- Local impact of mutations: A single mutation in the input sequence only affects a limited, local region in the intermediate layers of a CNN. Regions further away remain unchanged.
fastISM leverages these observations by:
- Caching intermediate outputs: For unperturbed input sequences, intermediate layer outputs are computed once and cached.
- Targeted recomputation: When a mutation is introduced,
fastISMonly recomputes the affected regions in the intermediate layers. It then intelligently combines these mutated regions with the cached unperturbed regions to compute the output of subsequent layers. - Computational graph representation: The algorithm first represents the model as a computational graph and chunks it into manageable segments.
This approach avoids redundant computations in unaffected regions of convolutional layers, leading to significant speedups.
Datasets
The paper does not explicitly mention specific biological datasets used for training the models. However, it uses three established CNN architectures for evaluation:
- Basset: A CNN for predicting chromatin accessibility.
- Factorized Basset: A variant of Basset.
- BPNet: A model for predicting quantitative regulatory profiles from DNA sequences.
These models are evaluated on inputs of varying lengths (1000bp and 2000bp) to assess the performance of fastISM across different sequence lengths and model complexities.
Key Insights and Ideas
- Redundancy is the enemy: The primary insight is that standard ISM is computationally inefficient because it recomputes large portions of the network that are unaffected by a single mutation.
- Local effects, global impact: While a mutation has a local effect in early layers, the CNN architecture propagates this effect.
fastISMcleverly manages this propagation by only recomputing what's necessary. - CNNs are ripe for optimization: The layered, convolutional nature of CNNs makes them particularly amenable to this type of targeted computation, unlike more monolithic architectures.
- Bridging the interpretability gap:
fastISMsignificantly narrows the performance gap between computationally expensive but faithful methods like ISM and faster but potentially less direct methods like backpropagation-based approaches.
Key Results
fastISM demonstrates substantial speed improvements:
- Over 10x speedup: For commonly used CNN architectures like Basset and Factorized Basset,
fastISMachieves more than a 10x speedup compared to standard ISM. This speedup increases with input sequence length. - Competitive with backpropagation methods: For single-output models,
fastISMruntimes are competitive with Integrated Gradients and DeepSHAP, often within 2-4x. - Superior to backpropagation for multi-output models: For multi-output architectures like BPNet,
fastISMdramatically surpasses backpropagation-based methods, which would require running computations for each output individually. For BPNet,fastISMis 1.6x-2.1x faster than standard ISM for different input lengths, and significantly faster than backpropagation methods (e.g., DeepSHAP and Integrated Gradients take over 50x longer). - Feasible for genome-wide analysis: These speed improvements make it practical to apply ISM genome-wide or on a large number of models.
Limitations and Future Work
- Overheads: While theoretically reducing computations by a factor of 17, practical speedups might be dampened by overheads like concatenating flanking regions.
- Architecture-specific implementation: The authors note that defining a custom model for ISM for each specific model could be cumbersome, which is why they developed
fastISMas a general method. - Future Work: The paper provides a Keras/TensorFlow 2 implementation and a tutorial, encouraging its adoption and further exploration. The success of
fastISMsuggests that similar optimization strategies could be applied to other types of deep learning architectures or feature attribution methods.
Summary updated