Improved Approximation Algorithms for Reconstructing the History of Tandem Repeats

ABSTRACT

Some genetic diseases in human beings are dominated by short sequences repeated consecutively called tandem repeats. Once a region containing tandem repeats is found, it is of great interest to study the history of creating the repeats. The computational problem of reconstructing the duplication history of tandem repeats has been studied extensively in the literature. Almost all previous studies focused on the simplest case where the size of each duplication block is 1. Only recently we succeeded in giving the first polynomial-time approximation algorithm with a guaranteed ratio for a more general case where the size of each duplication block is at most 2; the algorithm achieves a ratio of 6 and runs in O(n^{11}) time. In this paper, we present two new polynomial-time approximation algorithms for this more general case. One of them achieves a ratio of 5 and runs in O(n^9) time, while the other achieves a ratio of 2.5+\epsilon for any constant \epsilon > 0 but runs slower.

REFERENCES

• 1: Gary Benson , Lan Dong, Reconstructing the Duplication History of a Tandem Repeat, Proceedings of the Seventh International Conference on Intelligent Systems for Molecular Biology, p.44-53, August 06-10, 1999
• 2: Z.-Z. Chen, L. Wang, and Z. Wang, "Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats," Proc. 13th Ann. Int'l Computing and Combinatorics Conf. (COCOON '07), pp. 493-503, 2007.
• 3: W. Fitch, "Phylogenies Constrained by Cross-over Process as Illustrated by Human Hemoglobins in a Thirteen Cycle, Eleven Amino-Acid Repeat in Human Apolipoprotein A I," Genetics, vol. 86, pp. 623-644, 1977.
• 4: O. Gascuel, D. Bertrand, and O. Elemento, "Reconstructing the Duplication History of Tandemly Repeated Sequences," Mathematics of Evolution and Phylogeny, pp. 205-235. Oxford Univ. Press, 2005.
• 5: Deep Jaitly , Paul Kearney , Guohui Lin , Bin Ma, Methods for reconstructing the history of tandem repeats and their application to the human genome, Journal of Computer and System Sciences, v.65 n.3, p.494-507, November 2002 [doi>10.1016/S0022-0000(02)00006-5]
• 6: F. Lillo, S. Basile, and R.N. Mantegna, "Comparative Genomics Study of Inverted Repeats in Bacteria," Bioinformatics, vol. 18, pp. 971-979, 2002.
• 7: J. Macas, T. Mszros, and M. Nouzov, "PlantSat: A Specialized Database for Plant Satellite Repeats," Bioinformatics, vol. 18, pp. 28-35, 2002.
• 8: H.H. Otu and K. Sayood, "A New Sequence Distance Measure for Phylogenetic Tree Construction," Bioinformatics, vol. 19, pp. 2122- 2130, 2004.
• 9: M. Tang, M.S. Waterman, and S. Yooseph, "Zinc Finger Gene Clusters and Tandem Gene Duplication," J. Computational Biology, vol. 9, pp. 429-446, 2002.
• 10: L. Wang, T. Jiang, and E.L. Lawler, "Approximation Algorithms for Tree Alignment with a Given Phylogeny," Algorithmica, vol. 16, pp. 302-315, 1996.
• 11: Lusheng Wang , Tao Jiang , Dan Gusfield, A More Efficient Approximation Scheme for Tree Alignment, SIAM Journal on Computing, v.30 n.1, p.283-299, 2000 [doi>10.1137/S0097539796313507]
• 12: L. Zhang, B. Ma, L. Wang, and Y. Xu, "Greedy Method for Inferring Tandem Duplication History," Bioinformatics, vol. 19, pp. 1497-1504, 2003.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

General Terms:
Algorithms, Design, Theory

Keywords:
Computational biology, approximation algorithms.