An algorithm for computing the restriction scaffold assignment problem in computational biology

Let S and T be two finite sets of points on the real line with vertical bar S vertical bar + vertical bar T vertical bar = n and vertical bar S vertical bar > vertical bar T vertical bar. The restriction scaffold assignment problem in computational biology assigns each point of S to a point of T such that the sum of all the assignment costs is minimized, with the constraint that every element of T must be assigned at least one element of S. The cost of assigning an element s(i) of S to an element t(j) of T is vertical bar s(i) - t(j)vertical bar, i.e., the distance between s(i) and t(j). In 2003 Ben-Dor, Karp, Schwikowski and Shamir [J. Comput. Biol. 10 (2) (2003) 385] published an 0(n log n) time algorithm for this problem. Here we provide a counterexample to their algorithm and present a new algorithm that runs in O(n(2)) time, improving the best previous complexity of O(n(3)). (c) 2005 Elsevier B.V. All rights reserved.