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.
D000465:Algorithms; D001483:Base Sequence; D004247:DNA / Q000737:chemistry*; D008962:Models, Theoretical; D008969:Molecular Sequence Data; D009693:Nucleic Acid Hybridization; D009838:Oligodeoxyribonucleotides
D009838:Oligodeoxyribonucleotides; D004247:DNA