An O(n log n)-time algorithm for the restriction scaffold assignment problem

Justin Colannino, Mirela Damian, Ferran Hurtado, John Iacono, Henk Meijer, Suneeta Ramaswami, Godfried Toussaint

Research output: Contribution to journalArticlepeer-review


The restriction scaffold assignment problem takes as input two finite point sets S and T (with S containing more points than T) and establishes a correspondence between points in S and points in T, such that each point in S maps to exactly one point in T and each point in T maps to at least one point in S. An algorithm is presented that finds a minimum-cost solution for this problem in O(n log n) time, provided that the points in S and T are restricted to lie on a line and the cost function δ is the L1 metric. This algorithm runs in linear time, if S and T are presorted. This improves the previously best-known O(n2)-time algorithm for this problem.

Original languageEnglish (US)
Pages (from-to)979-989
Number of pages11
JournalJournal of Computational Biology
Issue number4
StatePublished - May 2006


  • Algorithm
  • Assignment
  • Linear
  • Matching
  • Minimum cost
  • Restricted scaffold

ASJC Scopus subject areas

  • Modeling and Simulation
  • Molecular Biology
  • Genetics
  • Computational Mathematics
  • Computational Theory and Mathematics


Dive into the research topics of 'An O(n log n)-time algorithm for the restriction scaffold assignment problem'. Together they form a unique fingerprint.

Cite this