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.