Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-054 | 12th April 2001 00:00

On the Complexity of Positional Sequencing by Hybridization

RSS-Feed




TR01-054
Authors: Amir Ben-Dor, Itsik Pe'er, Roded Sharan, Ron Shamir
Publication: 24th July 2001 12:44
Downloads: 2927
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint