Abstract
The pre-image problem has to be solved during inference by most structured output predictors. For string kernels, this problem corresponds to finding the string associated to a given input. An algorithm capable of solving or finding good approximations to this problem would have many applications in computational biology and other fields. This work uses a recent result on combinatorial optimization of linear predictors based on string kernels to develop, for the pre-image, a low complexity upper bound valid for many string kernels. This upper bound is used with success in a branch and bound searching algorithm. Applications and results in the discovery of druggable peptides are presented and discussed.
Introduction
In the field of computational biology, the design of new therapeutic peptides relies heavily on predictive modeling. Researchers often employ regression models, such as Kernel Ridge Regression, to estimate the bioactivity of short amino acid sequences. These models frequently utilize string kernels, which quantify similarity between sequences by comparing their constituent sub-strings, or k-mers.
A critical challenge arises once a model is trained: identifying the specific peptide sequence that yields the maximum predicted bioactivity. This is known as the pre-image problem. While solving this for unnormalized string kernels is computationally straightforward—often reducible to finding the longest path in a directed acyclic graph—the resulting sequences are frequently biologically flawed due to mathematical biases.
The Challenge of Normalization
Unnormalized string kernels are inherently biased toward sequence length and k-mer repetitions. A machine learning model might "exploit" this by assigning a massive score to a sequence that simply repeats a high-weight k-mer (e.g., "AAAAA"). While mathematically optimal for an unnormalized model, such repetitive peptides are often biologically useless or unstable.
Normalizing the kernel—dividing the prediction by the norm of the sequence—corrects this bias. However, normalization breaks the elegant graph-based optimization solutions used for unnormalized kernels. Finding the pre-image for a normalized string kernel is a notoriously difficult combinatorial optimization problem, conjectured to be NP-Hard.
Branch and Bound Methodology
To address the normalized pre-image problem, this paper introduces a branch-and-bound (B&B) search algorithm. Given that the space of possible peptide sequences grows exponentially with length, an exhaustive search is infeasible. The B&B approach systematically partitions the search space and prunes branches that cannot possibly surpass the best sequence identified so far.
The efficiency of this algorithm hinges on a novel low-complexity upper bound. The objective function for a normalized kernel is a fraction: the unnormalized prediction divided by the sequence norm. To bound this fraction for a partial string, the authors:
- Lower-bound the denominator: They determine the minimum possible norm for any sequence that could complete the current prefix.
- Upper-bound the numerator: They repurpose the dynamic programming tables from previous graph-based unnormalized methods to quickly estimate the maximum possible unnormalized score.
The algorithm further enhances performance by alternating between a greedy search—to establish a high initial pruning threshold—and the rigorous B&B phase.
Experimental Results
The proposed method was validated using a dataset of 101 cationic antimicrobial pentadecapeptides (CAMPs). The study compared the top 1,000 peptides generated by unnormalized versus normalized predictors. While there was a 70.5% overlap in the sequences identified, their internal rankings were poorly correlated (Pearson coefficient of 0.56), highlighting the impact of normalization on the final selection.
The necessity of normalization was most apparent in simulations of cyclic peptides, where position penalties are removed. In these tests, the unnormalized model failed catastrophically, outputting the highly repetitive sequence "FKKIFKKIFKKIFKF". In contrast, the normalized B&B method successfully identified a biologically plausible sequence, "WKKIFKKIWKFRVFK", which shared realistic substructures with known active peptides in the training set.
Conclusion and Future Work
This research demonstrates that while the normalized pre-image problem is computationally demanding, it can be solved effectively using a branch-and-bound framework guided by intelligent upper bounds. This approach avoids the "repetition trap" of unnormalized kernels, providing a more reliable tool for drug discovery. Future work will focus on developing even tighter bounds to further reduce search time and applying the method to the design of cyclic peptide drugs and other structured output tasks.
Summary updated