2008 | OriginalPaper | Buchkapitel
A Dynamic Programming Algorithm for De Novo Peptide Sequencing with Variable Scoring
verfasst von : Matthew A. Goto, Eric J. Schwabe
Erschienen in: Bioinformatics Research and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.