|
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. |