A Mixed Integer Linear Program for Post-translational Modification Characterization

Characterizing post-translational modifications (PTMs) is crucial due to their vital role in regulating cellular activities. Current database search methods for peptide identification and PTM characterization face the challenge of exponentially increasing number of PTM combinations. Consequently, these methods resort to enumerating a small fraction of the PTM combinations. However, based on our analysis, more than 99% of the PTM combinations (up to three PTMs) are infeasible as their total mass does not match the mass shift between the precursor mass and theoretical mass. Enumerating those infeasible combinations is unnecessary and would lead to unsatisfactory performance. To address this issue, we propose a two-step method for characterizing multiple PTMs with a reduced search space of feasible PTM combinations only. The method first uses a mixed integer linear program (MILP) to collect feasible peptide sequences and PTM mass combinations. Then, these feasible peptides are exhaustively examined to find the optimal one. We conducted comprehensive experiments to evaluate the method’s performance. When applied to a soybean data set, our method has better performance than a representative tag-based search engine. The effectiveness of search space reduction and the sensitivity and precision of our method are demonstrated.