95-19 Positional Sequencing by Hybridization

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