POSITIONAL SEQUENCING BY HYBRIDIZATION

Sequencing by hybridization (SBH) is a promising alternative to the cl assical DNA sequencing approaches. However, the resolving power of SBH is rather low: with 64 kb sequencing chips, unknown DNA fragments onl y as long as 200 bp can be reconstructed in a single SBH experiment. T o improve the resolving power in SBH, positional SBH (PSBH) has recent ly been suggested; this allows (with additional experimental work) app roximate positions of every l-tuple in a target DNA fragment to be mea sured. We study the positional Eulerian path problem motivated by PSBH . The input to the positional eulerian path problem is an Eulerian gra ph G(V, E) in which every edge has an associated range of integers and the problem is to find an Eulerian path e(1),...,e(\E\) in G such tha t the range of e(i) contains i. We show that the positional Eulerian p ath problem is NP-complete even when the maximum out-degree (in-degree ) of any vertex in the graph is 2. On a positive note we present polyn omial algorithms to solve a special case of PSBH (bounded PSBH), where the range of the allowed positions for any edge is bounded by a const ant (it corresponds to accurate experimental measurements of positions in PSBH). Moreover, if the positions of every l-tuple in an unknown D NA fragment of length n are measured with O(log n) error, then our alg orithm runs in polynomial time. We also present an estimate of the res olving power of PSBH for a more realistic case when positions are meas ured with Theta(n) error.