title: Reconstruction of sequence from its circular partial sums for cyclopeptide sequencing problem.
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.
authors: Institute of Cytology and Genetics, Siberian Branch of the Russian Academy of Sciences, 10 Prospekt Lavrentyeva, Novosibirsk 630090, Russian Federation.
authors: Eduard
authors: E
authors: Fomin
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D010456:Peptides, Cyclic / Q000737:chemistry*; D020539:Sequence Analysis, Protein / Q000379:methods*; D053719:Tandem Mass Spectrometry / Q000379:methods
chemical_list: D010456:Peptides, Cyclic
keywords: Beltway problem; bioinformatics; cyclopeptides