On Multiple Protein Scaffold Filling

In this paper, we initiate the study on some problems related to multiple protein scaffold filling, with or without references. The objective is to maximize the sum of the Blosum62 scores of the filled sequences when no reference is given, or to maximize the Blosum62 score between the filled sequence and a reference. We present the following results: (1) given n scaffolds generated from the top-down tandem mass spectra, finding k scaffolds whose corresponding contents can be used to fill into a target sequence (or, a sequence whose Blosum62 score with a reference is maximized) takes Ω (n^k-ε) time, unless the SETH (Strong Exponential Time Hypothesis) fails. (2) given two or more protein scaffolds and the corresponding multisets of amino acids to be filled accordingly, the corresponding optimization problem can be solved in polynomial time with dynamic programming. (3) Due to the high (and impractical) running times of the algorithms in (2), we implement several heuristic algorithms for the special cases when three scaffolds are given, and the corresponding empirical results are quite promising—although we also find that for the greedy algorithm more biological information needs to be incorporated to generate biologically meaningful results. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2026.