J. Blazewicz, P. Formanowicz, M. Kasprzak, W.T. Markiewicz, J. Weglarz,
"Tabu search for DNA sequencing with false negatives and false positives",
European Journal of Operational Research 125, 2000, pp. 257-265.
Abstract:
The paper deals with the problem of DNA (deoxyribonucleic acid) sequencing
by hybridization. A computational phase of this approach, i.e. a construction
of a DNA sequence from oligonucleotides, is NP-hard in the strong sense in
case of errors. Thus, since the last problem does not admit a polynomial
time solution, a need arises to construct efficient heuristics solving
the problem. In the paper, such a heuristic algorithm based on tabu search
is proposed. Computational tests have proved its low complexity and high
accuracy for both types of errors: false negatives and false positives.
Back to the List of publications
2 Oct 2001