Modeling of Partial Digest Problem as a Network flows problem

Abstract

Restriction Site Mapping is one of the interesting tasks in Computational Biology. A DNA strand can be thought of as a string on the letters A, T, C, and G. When a particular restriction enzyme is added to a DNA solution, the DNA is cut at particular restriction sites. The goal of the restriction site mapping is to determine the location of every site for a given enzyme. In partial digest method, all pairwise distances between restriction sites are produced. Mathematically, given pairwise distances between n points on a line segment, the goal is to find that points. This problem has been named Partial Digest Problem(PDP). In this paper we present a new model for PDP using generalized network flows. Since complexity class of this problem is one of the most important open problems in bioinformatics (there is no polynomial algorithm and no proof for Np-completeness) reducing to a network flow problem create a new viewpoint to challenge with this problem.