ECCC-Report TR01-054https://eccc.weizmann.ac.il/report/2001/054Comments and Revisions published for TR01-054en-usTue, 24 Jul 2001 12:44:01 +0300
Paper TR01-054
| On the Complexity of Positional Sequencing by Hybridization |
Amir Ben-Dor,
Itsik Pe'er,
Roded Sharan,
Ron Shamir
https://eccc.weizmann.ac.il/report/2001/054In 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.
Tue, 24 Jul 2001 12:44:01 +0300https://eccc.weizmann.ac.il/report/2001/054