Article ID: | iaor20011345 |
Country: | Netherlands |
Volume: | 125 |
Issue: | 2 |
Start Page Number: | 257 |
End Page Number: | 265 |
Publication Date: | Sep 2000 |
Journal: | European Journal of Operational Research |
Authors: | Kasprzak M., Formanowicz P., Blaewicz J., Markiewicz W.T., Wglarz J. |
Keywords: | programming: integer |
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.