Complexity and scoring function of MS/MS peptide de novo sequencing

Area of Science:

• Computational Biology
• Proteomics
• Bioinformatics

Background:

• Tandem mass spectrometry (MS/MS) is crucial for peptide and protein identification.
• De novo sequencing, deriving peptide sequences from MS/MS spectra, relies heavily on scoring functions.
• Existing algorithms often use N-terminal or C-terminal fragment ions, with internal ion effects on computational complexity unknown.

Purpose of the Study:

• To determine the computational complexity of de novo sequencing when considering internal fragment ions.
• To develop an improved scoring method for de novo sequencing that accounts for fragment ion correlations.
• To enhance the accuracy of de novo sequencing in proteomics.

Main Methods:

• Proved that including internal fragment ions renders the de novo sequencing problem NP-complete.
• Developed a novel regression model-based scoring function to capture fragment ion correlations.
• Integrated the new scoring function with the PEAKS de novo sequencing algorithm.

Main Results:

• Demonstrated that de novo sequencing becomes NP-complete with the inclusion of internal fragment ions.
• The regression model-based scoring method effectively incorporates fragment ion correlations.
• Testing on ion trap data showed significant improvements in de novo sequencing accuracy.

Conclusions:

• The consideration of internal fragment ions introduces significant computational complexity (NP-complete) to de novo sequencing.
• The proposed regression model-based scoring function offers a more accurate approach to de novo sequencing by leveraging fragment ion correlations.
• This advancement holds promise for improving peptide and protein identification in proteomics research using MS/MS data.