A Simple Approach to the Reconstruction of a Set of Points from the Multiset of n2Pairwise Distances in n2Steps for the Sequencing Problem: II. Algorithm.
A new uniform algorithm based on sequential removal of redundancy from inputs is proposed to solve the turnpike and beltway problems. For error-free inputs that simulate experimental data with high accuracy, the size of inputs decreases from [Formula: see text] to [Formula: see text], which permits one to eliminate exhaustive search almost completely and reconstruct sequences in [Formula: see text] steps. Computational experiments show high efficiency of the algorithm for both the turnpike and beltway cases, with the reconstruction time for sequences of lengths up to several thousand elements being within 1 second on a modern PC.
Institute of Cytology and Genetics , SB RAS, Novosibirsk, Russia .
Eduard
E
Fomin
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D006801:Humans; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software
algorithms; mass spectroscopy; sequences