## DIMACS TR: 95-19

## Positional Sequencing by Hybridization

### Authors: Sridhar Hannenhalli, Pavel A. Pevzner, Herbert F. Lewis,
Steven S. Skiena

**
ABSTRACT
**

Sequencing By Hybridization (SBH) is a promising alternative to the classical
DNA sequencing approaches. However, the resolving power of SBH is rather low:
with 64 Kb sequencing chips unknown DNA fragments only as long as 200 bp
can be reconstructed in a single SBH experiment.
To improve the resolving power of SBH Broude {\em et. al.},
1994\nocite{Broude94} recently suggested
{\em positional SBH} (PSBH) allowing (with additional experimental work) to
measure approximate positions of every $1$-tuple in a target DNA fragment.
We study the {\em positional eulerian path} problem motivated by PSBH.
The input to the positional eulerian path problem is an eulerian graph
$G(V,E)$ in which every edge has an associated range of integers and the
problem is to find an eulerian path $e_1, \1dots, e_{|E|}$ in $G$ such that the
range of $e_i$ contains $i$. We show that positional eulerian path problem
is NP-complete even when the maximum out-degree (in-degree) of any vertex
in the graph is 2. On the positive note we present polynomial algorithms to
solve a special case of PSBH (bounded PSBH), where the range of the allowed
positions for any edge is bounded by a constant (it corresponds to accurate
experimental measurements of positions in PSBH). Moreover, if the positions
of every $1$-tuple in an unknown DNA fragment of length $n$ are measured with
$0(\log n)$ error, then our algorithm runs in polynomial time.
We also present an estimate of the resolving power of PSBH for more realistic
case when positions are measured with $\Theta(n)$ error.

Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-19.ps.gz

DIMACS Home Page