A Simple Approach to the Reconstruction of a Set of Points from the Multiset of n 2 Pairwise Distances in n 2 Steps for the Sequencing Problem: II. Algorithm
Eduard S. Fomin · Journal of Computational Biology · 2016
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 $$O ( {n^2} )$$ to $$O ( n )$$, which permits one to eliminate exhaustive search almost completely and reconstruct sequences in $${n^2}$$ 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.