title: On the complexity of positional sequencing by hybridization.
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.
authors.affiliation: Agilent Laboratories.
authors.forename: A
authors.initials: A
authors.lastname: Ben-Dor
authors.forename: I
authors.initials: I
authors.lastname: Pe'er
authors.forename: R
authors.initials: R
authors.lastname: Shamir
authors.forename: R
authors.initials: R
authors.lastname: Sharan
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D009693:Nucleic Acid Hybridization; D017422:Sequence Analysis, DNA / Q000379:methods* / Q000706:statistics & numerical data