On the tandem duplication-random loss model of genome rearrangement

ABSTRACT

We initiate the algorithmic study of a new model of genome rearrangement, the tandem duplication-random loss model, in which a genome evolves via successive rounds of tandem duplication of a contiguous segment of genes, followed by the loss of one copy of each of the duplicated genes. This model is well-known in the evolutionary biology literature, where it has been used to explain many of the known rearrangements in vertebrate mitochondrial genomes. Based on the model, we formalize a notion of distance between two genomes and show how to compute it efficiently for two interesting regions of the parameter space. We then consider median problems (i.e. finding the point which minimizes the sum of distances to a given set of points under some distance function) in the context of maximum parsimony phylogenetic reconstruction for these two special cases. Surprisingly, one of them turns out to correspond to the well-known rank aggregation problem, while the other corresponds to the biologically interesting case of whole genome duplication and loss, and we give an O(log log n) additive approximation algorithm for the latter.

REFERENCES

• 1: B. Moret, J. Tang, and T. Warnow. Reconstructing phylogenies from gene-content and gene-order data. In O. Gascuel, editor, Mathematics of Evolution and Phylogeny. Oxford Univ. Press, 2004.
• 2: D. Sankoff and J. Nadeau, editors. Comparative Genomics. Kluwer Academic Publishers, 2000.
• 3: Nadia El-Mabrouk, Genome Rearrangement by Reversals and Insertions/Deletions of Contiguous Segments, Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching, p.222-234, June 21-23, 2000
• 4: M. Marron, K. M. Swenson, and B. M. E. Moret. Genomic distances under deletions and insertions. In COCOON, 2003.
• 5: Phylogenetic Reconstruction from Arbitrary Gene-Order Data, Proceedings of the 4th IEEE Symposium on Bioinformatics and Bioengineering, p.592, May 19-21, 2004
• 6: K. M. Swenson, M. Marron, J. V. Earnest-DeYoung, and B. M. E. Moret. Approximating the true evolutionary distance between two genomes. Tech. Report TRCS-2004-15, Univ. of New Mexico, 2004.
• 7: J. L. Boore. The duplication/random loss model for gene rearrangement exemplified by mitochondrial genomes of deuterostome animals. In D. Sankoff and J. Nadeau, editors, Comparative Genomics. Kluwer, 2000.
• 8: R. L. Mueller and J. L. Boore. Molecular mechanisms of extensive mitochondrial gene rearrangement in plethodontid salamanders. Mol. Bio. Evol., 22(10):2104--2112, 2005.
• 9: C. Moritz, T. E. Dowling, and W. M. Brown. Evolution of animal mitochondrial DNA: relvance for population biology and systematics. Annu. Rev. Ecol. Syst., 18:269--292, 1987.
• 10: S. Bensch and A. Härlid. Mitochondrial genomic rearrangements in songbirds. Mol. Biol. Evol., 17:107--113, 2000.
• 11: D. V. Lavrov, J. L. Boore, and W. M. Brown. Complete mtDNA sequences of two millipedes suggest a new model for mitochondrial gene rearrangements: duplication and nonrandom loss. Mol. Biol. Evol., 19(2):163--169, 2002.
• 12: J. G. Inoue, M. Miya, K. Tsukamoto, and M. Nishida. Evolution of the deep-sea gulper eel mitochondrial genomes: large-scale gene rearrangements originated within the eels. Mol. Biol. Evol., 20:1917--1924, November 2003.
• 13: I. Miklos and J. Hein. Genome rearrangement in mitochondria and its computational biology. In J. Lagergren, editor, Comparative Genomics: RECOMB 2004 Int. Workshop, volume 3388. Springer-Verlag, 2005.
• 14: S. Ohno. Evolution by Gene Duplication. Springer, New York, 1970.
• 15: M. Kellis, B. Birren, and E. Lander. Proof and evolutionary analysis of ancient genome duplication in the yeast Saccharomyces cerevisiae. Nature, 428:617--624, 2004.
• 16: O. Jaillon, J. Aury, F. Brunet, J. Petit, N. Stange-Thomann, et al. Genome duplication in the teleost fish Tetraodon nigroviridis reveals the early vertebrate proto-karyotype. Nature, 431:946--957, October 2004.
• 17: J. Felsenstein. Inferring Phylogenies. Sinauer Associates, 2004.
• 18: Cynthia Dwork , Ravi Kumar , Moni Naor , D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the 10th international conference on World Wide Web, p.613-622, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372165]
• 19: Nir Ailon , Moses Charikar , Alantha Newman, Aggregating inconsistent information: ranking and clustering, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060692]
• 20: A. Frieze, A new rounding procedure for the assignment problem with applications to dense graph arrangement problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.21, October 14-16, 1996
• 21: I. Pe'er and R. Shamir. The median problem for breakpoints are NP-complete. Technical Report TR98--071, ECCC, 1998.
• 22: Alberto Caprara, Formulations and hardness of multiple sorting by reversals, Proceedings of the third annual international conference on Computational molecular biology, p.84-93, April 11-14, 1999, Lyon, France [doi>10.1145/299432.299461]
• 23: I. Pe'er and R. Shamir. Approximation algorithms for the permutations median problem in the breakpoint model. In D. Sankoff and J. Nadeau, editors, Comparative Genomics, pages 225--241. Kluwer Academic Press, 2000.
• 24: Guy Even , Joseph Naor , Baruch Schieber , Madhu Sudan, Approximating Minimum Feedback Sets and Multi-Cuts in Directed Graphs, Proceedings of the 4th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.14-28, May 29-31, 1995
• 25: K. G. Helfenbein, W. M. Brown, and J. L. Boore. The complete mitochondrial genome of the articulate brachiopod Terebratalia transversa. Mol. Biol. Evol., 18(9):1734--1744, September 2001.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures; Sequencing and scheduling

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Pattern analysis
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Theory