Approximating the true evolutionary distance between two genomes

ABSTRACT

As more and more genomes are sequenced, evolutionary biologists are becoming increasingly interested in evolution at the level of whole genomes, in scenarios in which the genome evolves through insertions, duplications, deletions, and movements of genes along its chromosomes. In the mathematical model pioneered by Sankoff and others, a unichromosomal genome is represented by a signed permutation of a multiset of genes; Hannenhalli and Pevzner showed that the edit distance between two signed permutations of the same set can be computed in polynomial time when all operations are inversions. El-Mabrouk extended that result to allow deletions and a limited form of insertions (which forbids duplications); in turn we extended it to compute a nearly optimal edit sequence between an arbitrary genome and the identity permutation. In this paper we generalize our approach to compute distances between two arbitrary genomes, but focus on approximating the true evolutionary distance rather than the edit distance. We present experimental results showing that our algorithm produces excellent estimates of the true evolutionary distance up to a (high) threshold of saturation; indeed, the distances thus produced are good enough to enable the simple neighbor-joining procedure to reconstruct our test trees with high accuracy.

REFERENCES

• 1: Andelfinger, G., Hitte, C., Etter, L., Guyon, R., Bourque, G., Tesler, G., Pevzner, P., Kirkness, E., Galibert, F., and Benson, D. W. 2004. Detailed four-way comparative mapping and gene order analysis of the canine ctvm locus reveals evolutionary chromosome rearrangements. Genomics 83, 1053--1062.
• 2: Bader, D. A., Moret, B. M. E., and Yan, M. 2001. A fast linear-time algorithm for inversion distance with an experimental comparison. J. Comp. Biol. 8, 5, 483--491.
• 3: Alberto Caprara, Sorting by reversals is difficult, Proceedings of the first annual international conference on Computational molecular biology, p.75-83, January 20-23, 1997, Santa Fe, New Mexico, United States [doi>10.1145/267521.267531]
• 4: 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]
• 5: Xin Chen , Jie Zheng , Zheng Fu , Peng Nan , Yang Zhong , Stefano Lonardi , Tao Jiang, Assignment of Orthologous Genes via Genome Rearrangement, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.2 n.4, p.302-315, October 2005 [doi>10.1109/TCBB.2005.48]
• 6: Downie, S. and Palmer, J. 1992. Use of chloroplast DNA rearrangements in reconstructing plant phylogeny. In Plant Molecular Systematics. P. Soltis, D. Soltis, and J. Doyle, eds. Chapman and Hall, London. 14--35.
• 7: Earnest-deyoung, J., Lerat, E., and Moret, B. M. E. 2004. Reversing gene erosion: reconstructing ancestral bacterial genomes from genecontent and geneorder data. In Proc. 4th Workshop on Algs. in Bioinformatics WABI'04, volume 3240 of Lecture Notes in Computer Science. Springer-Verlag, New York. 1--13.
• 8: 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
• 9: Sridhar Hannenhalli , Pavel Pevzner, Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.178-189, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225112]
• 10: Heard, S. B. 1996. Patterns in phylogenetic tree balance with variable and evolving speciation rates. Evolution 50, 2141--2148.
• 11: Li, W.-H. and Graur, D. 2000. Fundamentals of Molecular Evolution. Sinauer and Associates.
• 12: Mark Marron , Krister M. Swenson , Bernard M. E. Moret, Genomic distances under deletions and insertions, Theoretical Computer Science, v.325 n.3, p.347-360, 6 October 2004 [doi>10.1016/j.tcs.2004.02.039]
• 13: Bernard M. E. Moret , Jijun Tang , Li-San Wang , Tandy Warnow, Steps toward accurate reconstructions of phylogenies from gene-order data, Journal of Computer and System Sciences, v.65 n.3, p.508-525, November 2002 [doi>10.1016/S0022-0000(02)00007-7]
• 14: Moret, B. M. E., Tang, J., and Warnow, T. 2005. Reconstructing phylogenies from gene-content and gene-order data. In Mathematics of Evolution and Phylogeny. O. Gascuel, ed. Oxford University Press, Oxford. 321--352.
• 15: Nakhleh, L., Moret, B. M. E., Roshan, U., st. John, K., Sun, J., and Vvarnow, T. 2002. The accuracy of fast phylogenetic methods for large datasets In Proc. 7th Pacific Symp. on Biocomputing PSB'O2. World Scientific Pub. 211--222.
• 16: Olmstead, R. and Palmer, J. 1994. Chloroplast DNA systematics: a review of methods and data analysis. Amer. J. Bot. 81, 1205--1224.
• 17: Palmer, J. 1992. Chloroplast and mitochondrial genome evolution in land plants. In Cell Organelles. R. Herrmann, ed. Springer Verlag, New York. 99--133.
• 18: Pattengale, N. D., Swenson, K. M., and Moret, B. M. E. Approximation algorithms for orthology assignment from gene rearrangement data. Journal of Computer and Systems Sciences. Submitted.
• 19: Raubeson L. and Jansen, R. 1992. Chloroplast DNA evidence on the ancient evolutionary split in vascular land plants. Science 255, 1697--1699.
• 20: Robinson, D. R. and Foulds, L. R. 1981. Comparison of phylogenetic trees. Mathematical Biosciences, 53, 131--147.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
Evolution, duplications, inversions, pairwise distances, whole-genome data