Reconstruction of sequence from its circular partial sums for cyclopeptide sequencing problem
peer-reviewed · Journal of Bioinformatics and Computational Biology · 2015
| Date | 2015-02-01 |
| Type | peer-reviewed |
| Venue | Journal of Bioinformatics and Computational Biology |
| Publisher | World Scientific Pub Co Pte Lt |
| Contribution | algorithm |
| DOI | 10.1142/s0219720015400089 |
| Citations (OpenAlex) | 8 |
| Venue 2-year citedness | 0.89 |
Abstract
In this paper, we consider the cyclopeptide sequencing problem that arose in computational biology with regard to de novo peptide sequencing in the 2000s. The sequencing problem for cyclic peptides is reduced in mathematics to the one-dimensional beltway problem: given a set of all circular pairwise distances between points, find the coordinates of these points. The beltway problem is one of the few fundamental problems that are neither known to be NP-complete nor solvable by polynomial-time algorithms. We develop an efficient algorithm for the cyclopeptide sequencing problem. The algorithm exploits information on possible elements of sequence and, thus, it makes it possible to restore sequences of lengths up to 160 elements. Numerical simulations sustain the effectiveness of the proposed algorithm.
Methods and tools
- Cyclopeptide beltway reconstruction: Reduces cyclic peptide sequencing from mass spectra to the beltway problem and solves it with an algorithm that restores sequences of up to 160 residues.