FASTER IMPLEMENTATION OF A SHORTEST SUPERSTRING APPROXIMATION

The shortest superstring problem has recently received renewed attenti on due to its connection to problems in sequencing long pieces of DNA. Most recently, Teng and Yao [6] developed an approximation algorithm for the shortest superstring problem which has a smaller error bound t han the previously best approximation due to Blum, Jiang, Li, Tromp an d Yannakakis [1]. However, the implementation given in [6] is slower t han the implementation suggested by Gusfield, Landau, and Schieber [3] for the approximation method of Blum et al. In this paper we reduce t he worst case running time for the new approximation method of Teng an d Yao, making it's running time competitive with the approximation met hod of Blum et al. We exploit suffix trees and properties of the perio dicity of strings.