"DNA sequencing by hybridization and graph theory"
                Jacek Blazewicz

The talk deals with the problem of DNA de novo sequencing by
hybridization. Firstly, the problem with  isometric oligonucleotide
libraries is considered. A computational phase of this approach, i.e. a
construction of a DNA sequence from oligonucleotides, may be modeled as a
path construction problem in the newly introduced DNA graphs. In an
error-free case this problem is solvable in polynomial time. On the other
hand, it turns to be  NP-hard in the strong sense in  case of errors. 
Thus, since the last problem does not admit a
polynominal time solution, a need arises to construct efficient heuristics
solving the problem. In the talk, such a heuristic algorithm based on tabu
search is discussed.  Computational tests have proved its low complexity
and high accuracy for both types of errors: false negatives and false
positives. The case of isothermic oligonucleotide libraries is also
discussed.