Reconstruction of a string from substring precedence data.

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.