A Simple Approach to the Reconstruction of a Set of Points from the Multiset of n2 Pairwise Distances in n2 Steps for the Sequencing Problem: I. Theory

The problem of the reconstruction of the order of sequence elements in de novo sequencing of linear and cyclic peptides is reduced to the known turnpike and beltway problems, the latter of which having no polynomial time algorithm in the general case. A new simple approach is proposed to solve both problems. It is based on sequential removal of redundancy from the inputs. For the error-free inputs that simulate mass spectra with accuracy to 10(-3) Da, the size of inputs decreases from O(n(2)) to O(n). In this way, exhaustive search can be almost completely removed from the algorithms, and the number of steps to reconstruct a sequence is in direct ratio to the input size, n(2).