A R Rubinov | PubMed Health

PubMed1995

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.

Algorithms↗

PubMed1993

Non-similarity combinatorial problems.

Similarity problems intensively investigated in computational molecular biology have the following two stringology models: find the longest string included in any string of a given finite language, and find the shortest string including every string of a given finite language. These two problems are exemplified by the two well-known pairs of problems, the longest common subsequence (or substring) problem and the shortest common supersequence (or superstring) problem, interpretations. In this paper we consider opposite problems connected with string non-inclusion relations: find the shortest string included in no string of a given finite language and find the longest string including no string of a given finite language. The predicate "string alpha is not included in string beta" is interpreted either as "alpha is not a subsequence of beta" or as "alpha is not a substring of beta". The main purpose is to determine the complexity status of the non-similarity problems. Using graph approaches, we present NP-hardness proofs for the first interpretation and polynomial-time algorithms for the second one. Special cases of the problems, and related issues are discussed.

Algorithms↗