TR01-054 Authors: Amir Ben-Dor, Itsik Pe'er, Roded Sharan, Ron Shamir

Publication: 24th July 2001 12:44

Downloads: 1957

Keywords:

In sequencing by hybridization (SBH),

one has to reconstruct a sequence

from its $l$-long substrings.

SBH was proposed as

an alternative to

gel-based

DNA sequencing approaches, but in its original form the method

is

not competitive.

Positional SBH (PSBH) is a recently proposed

enhancement of SBH

in which one has additional information about the

possible

positions of each substring along the target sequence.

We give

a linear time algorithm for solving PSBH when

each substring has at most

two possible positions. On the other

hand, we prove that the problem is

NP-complete

if each substring has at most three possible positions.

We

also show that PSBH is NP-complete if the set of allowed positions

for

each substring is an interval of length $k$, and provide

a fast

algorithm for the latter problem when $k$ is bounded.