Graph traversals, genes and matroids: an efficient case of the travelling salesman problem

In this paper we consider graph traversal problems (Euler and Travelling Sa lesman traversals) that arise from a particular technology for DNA sequenci ng - sequencing by hybridization (SBH). We first explain the connection of the graph problems to SBH and then focus on the traversal problems. We desc ribe a practical polynomial time solution to the Travelling Salesman Proble m in a rich class of directed graphs (including edge weighted binary de Bru ijn graphs), and provide bounded-error approximation algorithms for the max imum weight TSP in a superset of those directed graphs. We also establish t he existence of a matroid structure defined on the set of Euler and Hamilto n paths in the restricted class of graphs. 1998 Published by Elsevier Scien ce B.V. All rights reserved.