Reconstruction of sequence from its circular partial sums for cyclopeptide sequencing problem

摘要

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.