Structure- and Function-Aware Substitution Matrices via Learnable Graph Matching

Substitution matrices, which are crafted to quantify the functional impact of substitutions or deletions in biomolecules, are central component of remote homology detection, functional element discovery, and structure prediction algorithms. In this work we explore the use of biological structures and prior knowledge about molecular function (e.g. experimental data or functional annotations) as additional information for building more expressive substitution matrices compared to the traditional frequency-based methods. External prior knowledge in the form of family annotations have been exploited for specialized sequence alignment methods, and substitution matrices on structural alphabets have led to advances in remote homology detection. However, no method has integrated both structural information as well as external priors without the need of pre-curated alignments. Here we propose a general algorithmic framework for learning structure-based substitution matrices automatically conditioned on any prior knowledge. In particular, we represent the structures of interest as graphs and we learn, using graph neural networks, suitable substitution cost matrices such that the resulting graph matching metric correlates with the prior at hand. Our method shows promising performance in functional similarity classification tasks and molecular database searching and shows potential for interpreting the functional importance of substructures. Code and data are available at: https://github.com/BorgwardtLab/GraphMatchingSubstitutionMatrices .