Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats

Computing the duplication history of a tandem repeated region is an important problem in computational biology (Fitch in Genetics 86:623-644, 1977; Jaitly et al. in J. Comput. Syst. Sci. 65:494-507, 2002; Tang et al. in J. Comput. Biol. 9:429-446, 2002). In this paper, we design a polynomial-time approximation scheme (PTAS) for the case where the size of the duplication block is 1. Our PTAS is faster than the previously best PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494-507, 2002). For example, to achieve a ratio of 1.5, our PTAS takes O (n⁵) time while the PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494-507, 2002) takes O (n¹¹) time. We also design a ratio-6 polynomial-time approximation algorithm for the case where the size of each duplication block is at most 2. This is the first polynomial-time approximation algorithm with a guaranteed ratio for this case.