Cyclic Peptide Sequencing Problem

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