2026-08-27T21:20:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27521 2026-08-27T06:04:07Z ddc:004 open_access

Discriminative Learning of Substitution Matrices and Gap Penalties for Pairwise Alignment of Biological Sequences Ciach, Michał Aleksander Zacharopoulou, Elissavet Startek, Michał Piotr Miasojedow, Błażej Alexiou, Panagiotis Sequence alignment Substitution matrix Logistic regression Pairwise alignment scores are used to classify pairs of sequences in many areas of bioinformatics, including homology search, predicting interactions, or read mapping. The relative scores of different pairs strongly depend on the choice of a substitution matrix and gap penalties. However, current approaches for the estimation of these parameters typically describe patterns observed in a collection of ground-truth alignments instead of optimizing specifically for the task of classification. In this work, we present DiscrimAlign, a statistical model for discriminative learning of substitution matrices and gap penalties from a dataset of positive and negative pairs of unaligned DNA or amino acid sequences. The model links the alignment score of a sequence pair with the associated binary label through a logistic function and learns the parameters by likelihood maximization. We analyze theoretical properties of the model, derive and implement a learning procedure, study its performance in simulated experiments, and apply it to predict microRNA-target interactions. We show that sequence alignment with discriminative substitution matrices and gap penalties predicts the interactions comparably to black-box neural network classifiers while being more interpretable. An implementation of the model and reproducibility workflows are available at https://github.com/BioGeMT/DiscrimAlign. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michał Aleksander Ciach and Elissavet Zacharopoulou and Michał Piotr Startek and Błażej Miasojedow and Panagiotis Alexiou 2026 Is Part Of LIPIcs, Volume 390, 26th International Conference on Algorithms for Bioinformatics (WABI 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2026.17 urn:nbn:de:0030-drops-275218 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.17 eng https://creativecommons.org/licenses/by/4.0/legalcode