A Dynamic Programming Approach for the Alignment of Molecules

Abstract

I.There is a need for computational approaches to compare molecules based upon chemical similarity or for evaluating biochemical transformations. Here, a new approach to molecular alignment in the Simplified Molecular Input Line Entry System (SMILES) format is introduced. Leveraging dynamic programming and scoring alignments to minimize differences in a measure of electronegativity, the study addresses the challenge of comprehending structural transformations in reaction pathways, notably transitions from linear to cyclical structures. The method is built from the Needleman-Wunsch algorithm for sequence alignment, but with a modified scoring function for different input data. Validation against a benchmarked dataset from the Krebs cycle based upon known chemical mechanisms of molecular transformations confirmed the efficacy of the approach. The transformations of the Pentose Phosphate Pathway were quantified using this algorithm and was compared with Glycolysis. The study introduces an algorithm that quantifies molecular transformations in metabolic pathways, highlighting a midpoint dissimilarity peak in cyclical pathways and a progressive decrease in molecular similarity in linear pathways. The software is available at: https://github.com/rwills5042/SMILES_Alignment.