De Novo Peptide Sequencing Based on Vertex Contraction Algorithm
peer-reviewed · 2012 Fifth International Joint Conference on Computational Sciences and Optimization · 2012
| Date | 2012-06-01 |
| Type | peer-reviewed |
| Venue | 2012 Fifth International Joint Conference on Computational Sciences and Optimization |
| Publisher | IEEE |
| Contribution | algorithm |
| DOI | 10.1109/cso.2012.19 |
| Citations (OpenAlex) | 0 |
Abstract
De novo peptide sequencing is an important method for peptide sequencing and protein identification. It can be transformed into a special case of paths avoiding forbidden pairs problem (PAFP). General PAFP is NP-complete. The definition of PAFP is the following: Given a directed acyclic graph G = (V, E), two distinguished vertices source s, sink t ∈ V , a set of forbidden pairs F ⊂ V × V, and an edge weight function w : E -+ R, asking for a maximum weight path from s to t passing at most one vertex from each forbidden pair. In the process of transformation from de novo peptide sequencing to PAFP, forbidden pairs have nested structure. We give a vertex contraction algorithm which is designed based on nested structure of forbidden pairs to solve paths avoiding forbidden pairs problem. The time complexity of vertex contraction algorithm is O(|V|3).
Methods and tools
- Vertex contraction de novo sequencing: Solves the nested forbidden-pairs longest path problem behind spectrum-graph de novo sequencing in cubic time by vertex contraction.