Cyclic Peptide Sequencing Problem (Cyclic Peptide Sequencing Problem)

From Algorithm Wiki
(Redirected from CPSP)
Jump to navigation Jump to search

Description

Given an experimental $MS^3$ spectrum $S$, find a cyclic peptide $P$ maximizing the number of shared masses between $S$ and the theoretical spectrum of $P$.

Parameters

$n$: size of peptide, in daltons

$m$: number of elements in experimental spectrum

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Brute force 1987 ${2}^{O(n)}$ $O(n)$ Exact Deterministic
Branch and bound 1993 ${2}^{O(n)}$ $O({2}^{O(n)})$ Exact Deterministic

Time Complexity Graph

Cyclic Peptide Sequencing Problem - Time.png