J. Blazewicz, P. Formanowicz, M. Kasprzak, W.T. Markiewicz,
"Sequencing by hybridization with isothermic oligonucleotide libraries",
Discrete Applied Mathematics 145, 2004, 40-51.
Download full text
Abstract:
The problem addressed in this paper is concerned with DNA sequencing by hybridization. A new
type of oligonucleotide libraries is proposed for hybridization experiments. The libraries consist of
oligonucleotides of different length dependent on an oligonucleotide A(T) and C(G) content in such
a way that an increment of C(G) is twice of that of A(T) and the sum of increments for each
oligonucleotide is constant for a library. The latter is called an isothermic oligonucleotide library and
the way of its construction will be presented. It will be shown that two such libraries that differ in
their sums of increments by an A(T) increment are sufficient for DNA sequencing by hybridization.
The hybridization experiment using isothermic oligonucleotide libraries should supply data with a
lower number of errors due to the expected similarity of melting temperatures of oligonucleotide
duplexes, thus, offering more stable conditions of the hybridization experiment. The combinatorial
part of the general problem of DNA sequencing (allowing all kinds of errors) with isothermic
libraries will be then formulated, and the ways of solving it will be shown. The general problem will
be proved to be strongly NP-hard, but heuristic algorithms solving this problem are reported to
have better computational features than those for standard libraries.
Back to the List of publications
3 Nov 2004