Title: A Dynamic Programming Algorithm for Finding Highest-Scoring Forbidden-Pairs Paths with Variable Vertex Scores
Published: July 2007
Authors: Matthew A. Goto, Eric J. Schwabe
Abstract: In the de novo peptide sequencing problem, output data from a mass spectrometer is used to determine the peptide whose fragmentation yielded that output. Candidate peptides are 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, vertex scores may vary depending on which incident edges are used in the path, 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 in this way that runs in O(n2 d3) time on a graph with n forbidden pairs and a maximum vertex degree of d. We are currently working on a Java implementation of this algorithm that we plan on incorporating into the Illinois Bio-Grid Desktop.
Full Paper: [postscript, pdf]