IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Algorithms for optimizing production DNA sequencing

A 1999 Preprint by É. Czabarka, G. Konjevod, M. Marathe, A. Percus, and D. Torney

  • 1999:05
  • We discuss the problem of optimally "finishing" a partially sequenced, reconstructed DNA segment. At first sight, this appears to be computationally hard. We construct a series of increasingly realistic models for the problem and show that all of these can in fact be solved to optimality in polynomial time, with near-optimal solutions available in linear time. Implementation of our algorithms could result in a substantial efficiency gain for automated DNA sequencing.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster