Reconstruction of a String from Substring Precedence Data

A. R. Rubinov, M. S. Gelfand

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)371-381
Number of pages11
JournalJournal of computational biology : a journal of computational molecular cell biology
Issue number2
Publication statusPublished - 1995
Externally publishedYes


Dive into the research topics of 'Reconstruction of a String from Substring Precedence Data'. Together they form a unique fingerprint.

Cite this