Tabu search for DNA sequencing with false negatives and false positives

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...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2000-09, Vol.125 (2), p.257-265
Main Authors: Błażewicz, J, Formanowicz, P, Kasprzak, M, Markiewicz, W.T, Wȩglarz, J
Format: Article
Language:English
Subjects:
Algorithms
Computational complexity
Deoxyribonucleic acid
DNA
DNA sequencing with errors
Error analysis
Heuristic methods
Integer linear programming
Integer programming
Linear programming
Polynomials
Searches
Statistical methods
Studies
Tabu search
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0377-2217
1872-6860
DOI:10.1016/S0377-2217(99)00456-7