OTMalign: A Fast and Robust TM-score-driven Protein Structure Alignment Algorithm using Optimal Transport

Abstract

Protein structure alignment is a fundamental task in computational biology. While the TM-score is a gold standard for evaluating structural similarity, its direct optimization is challenging. Many algorithms, therefore, rely on heuristic or combinatorial approaches. In this work, we present OTMalign, a novel algorithm that iteratively optimizes the TM-score in a fast and robust manner. OTMalign leverages the theory of Optimal Transport (OT) to establish a soft correspondence between protein structures, guided by a TM-score-inspired reward matrix. This avoids the pitfalls of combinatorial searches and provides a global perspective at each iteration. The optimal rigid body transformation is then determined analytically using a weighted Kabsch algorithm, where the weights are derived from the OT correspondence matrix (the P matrix). We demonstrate that this P matrix effectively captures the structural similarity, and its use in a weighted covariance matrix allows for a direct SVD-based solution for the rotation and translation. We evaluated OTMalign on the RPIC benchmark dataset, demonstrating its rapid convergence and ability to produce high-quality alignments. OTMalign offers a practical and theoretically sound framework for TM-score optimization, distinguished by its speed and iterative nature.