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

In this paper we consider graph traversal problems (Euler and Travelling Salesman traversals) that arise from a particular technology for DNA sequencing - sequencing by hybridization (SBH). We first explain the connection of the graph problems to SBH and then focus on the traversal problems. We describe a practical polynomial time solution to the Travelling Salesman Problem in a rich class of directed graphs (including edge weighted binary de Bruijn graphs), and provide bounded-error approximation algorithms for the maximum weight TSP in a superset of those directed graphs. We also establish the existence of a matroid structure defined on the set of Euler and Hamilton paths in the restricted class of graphs. 1998 Published by Elsevier Science B.V. All rights reserved.