fastISM: Performant in-silico saturation mutagenesis for convolutional neural networks

Surag Nair, Avanti Shrikumar, Anshul KundajebioRxiv 2020 · DOI

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:

  1. Convolutional layers dominate computation: The majority of the computational cost in CNNs during ISM comes from these layers.
  2. 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, fastISM only 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. fastISM cleverly 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: fastISM significantly 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, fastISM achieves more than a 10x speedup compared to standard ISM. This speedup increases with input sequence length.
  • Competitive with backpropagation methods: For single-output models, fastISM runtimes are competitive with Integrated Gradients and DeepSHAP, often within 2-4x.
  • Superior to backpropagation for multi-output models: For multi-output architectures like BPNet, fastISM dramatically surpasses backpropagation-based methods, which would require running computations for each output individually. For BPNet, fastISM is 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 fastISM as 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 fastISM suggests that similar optimization strategies could be applied to other types of deep learning architectures or feature attribution methods.

Summary updated

Abstract

Abstract Deep learning models such as convolutional neural networks are able to accurately map biological sequences to associated functional readouts and properties by learning predictive de novo representations. In-silico saturation mutagenesis (ISM) is a popular feature attribution technique for inferring contributions of all characters in an input sequence to the model’s predicted output. The main drawback of ISM is its runtime, as it involves multiple forward propagations of all possible mutations of each character in the input sequence through the trained model to predict the effects on the output. We present fastISM, an algorithm that speeds up ISM by a factor of over 10x for commonly used convolutional neural network architectures. fastISM is based on the observations that the majority of computation in ISM is spent in convolutional layers, and a single mutation only disrupts a limited region of intermediate layers, rendering most computation redundant. fastISM reduces the gap between backpropagation-based feature attribution methods and ISM. It far surpasses the runtime of backpropagation-based methods on multi-output architectures, making it feasible to run ISM on a large number of sequences. An easy-to-use Keras/TensorFlow 2 implementation of fastISM is available at https://github.com/kundajelab/fastISM , and a hands-on tutorial at https://colab.research.google.com/github/kundajelab/fastISM/blob/master/notebooks/colab/DeepSEA.ipynb .
BibTeX
@misc{nair2020fastism,
  author = {Surag Nair and Avanti Shrikumar and Anshul Kundaje},
  title = {{fastISM: Performant <i>in-silico</i> saturation mutagenesis for convolutional neural networks}},
  year = {2020},
  doi = {10.1101/2020.10.13.337147},
  howpublished = {bioRxiv},
}

Loading related content...

Figure