DNA sequencing. In genetic engineering, a collection of DNA strings, each of length 10 ft, is concatenated to form one universal string. The genes of individual DNA strings may overlap, thus producing a universal string with length less than the sum of the individual lengths. The matrix ‘Oij ‘ below provides the length in feet of overlaps for a hypothetical case of six DNA strings.

‘Oij ‘ = ¶

- 1 0 3 4 3 1 - 4 5 3 2 0 4 - 3 5 6 3 5 3 - 2 1 4 3 5 2 - 2 3 2 6 1 2 -



Compare the lower bounds on the optimum tour length using both the assignment model and linear programming. Is the assignment model solution optimum for the TSP?