Reconstruction of a String from Substring Precedence Data

Abstract

ABSTRACT

The problem of reconstructing of a symbol string given the data about precedence of fixed length substrings arises in the method of nucleic acid sequencing by nested strand hybridization. We reformulate the problem in the graph-theoretical terms, describe the structure of the set of solutions, and present polynomial time algorithms that check existence and uniqueness of a solution or finiteness of the solution set, and then construct the solutions.