A Dynamic Programming Algorithm for De Novo Peptide Sequencing with Variable Scoring

In the de novo peptide sequencing problem, output data from a tandem mass spectrometer are used to determine the peptide whose fragmentation yielded the output. Candidate peptides can be determined by finding forbidden-pairs paths in a spectrum graph constructed from the mass spectrometer data, assigning scores to vertices and/or edges in order to favor higher-scoring peptides. Chen et al. gave an algorithm to find the highest-scoring forbidden-pairs path in such a graph. However, in some scoring models, a vertex’s score may vary depending on which incident edges are used in the path containing the vertex, ruling out the use of this algorithm. We give an algorithm to solve the highest-scoring forbidden-pairs paths problem when vertex scores can vary depending on the incident edges used that runs in

O

(

n

2

d

3

) time on a graph with

n

forbidden pairs and a maximum vertex degree of

d

, and prove its correctness. We are currently working on a Java implementation of this algorithm that we plan on incorporating into the Illinois Bio-Grid Desktop.