Tabu search algorithm for DNA sequencing by hybridization with multiplicity information available

The classical DNA sequencing by hybridization (SBH) uses a binary information about oligonucleotide presence in an analyzed DNA sequence. A given oligonucleotide is or is not a part of the sequence. However, the development of the DNA chip technology allows to take into consideration some information about repetitions in the target sequence. Currently, it is not possible to determine the exact data of such type but even partial multiplicity information should be very useful.In this paper two simple but realistic multiplicity information models are taken into account. The first one assumes that it is known if a given oligonucleotide occurs in the analyzed sequence once or more than once. According to the second model it is possible to determine if a given oligonucleotide appears in the target sequence once, twice or at least three times. A tabu search algorithm has been implemented to verify these models. It solves the problem with any kind of hybridization errors. Computational experiment results confirm that the additional information leads to an improvement of the reconstruction process. They also show that the more precise model of information increases the quality of the obtained solutions.Test data sets and the implemented tabu search algorithm are available on: http://bio.cs.put.poznan.pl/files/52234a7c9dfb89b808000001/download.