  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.
