A Framework for Orthology Assignment from Gene Rearrangement Data

  • Krister M. Swenson
  • Nicholas D. Pattengale
  • B. M. E. Moret
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3678)


Gene rearrangements have been used successfully in phylogenetic reconstruction and comparative genomics, but usually under the assumption that all genomes have the same gene content and that no gene is duplicated. While these assumptions allow one to work with organellar genomes, they are too restrictive for nuclear genomes. The main challenge in handling more realistic data is how to deal with gene families, specifically, how to identify orthologs. While searching for orthologies is a common task in computational biology, it is usually done using sequence data. Sankoff first addressed the problem in 1999, introducing the notion of exemplar, but his approach uses an NP-hard optimization step to discard all but one member (the exemplar) of each gene family, losing much valuable information in the process. We approach the problem using all available data in the gene orders and gene families, provide an optimization framework in which to phrase the problem, and present some preliminary theoretical results.


Gene Family Multigene Family Cycle Count Elementary Cycle Edit Sequence 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Bader, D.A., Moret, B.M.E., Yan, M.: A fast linear-time algorithm for inversion distance with an experimental comparison. J. Comput. Biol. 8(5), 483–491 (2001)CrossRefGoogle Scholar
  2. 2.
    Blanchette, M., Kunisawa, T., Sankoff, D.: Gene order breakpoint evidence in animal mitochondrial phylogeny. J. Mol. Evol. 49, 193–203 (1999)CrossRefGoogle Scholar
  3. 3.
    Boore, J.L.: Phylogenies derived from rearrangements of the mitochondrial genome. In: Saitou, N. (ed.) Proc. Int’l Inst. for Advanced Studies Symp. on Biodiversity, Kyoto, Japan, pp. 9–20 (1999)Google Scholar
  4. 4.
    Boore, J.L., Brown, W.M.: Big trees from little genomes: Mitochondrial gene order as a phylogenetic tool. Curr. Opinion Genet. Dev. 8(6), 668–674 (1998)CrossRefGoogle Scholar
  5. 5.
    Boore, J.L., Collins, T., Stanton, D., Daehler, L., Brown, W.M.: Deducing the pattern of arthropod phylogeny from mitochondrial DNA rearrangements. Nature 376, 163–165 (1995)CrossRefGoogle Scholar
  6. 6.
    Bryant, D.: The complexity of calculating exemplar distances. In: Sankoff, D., Nadeau, J. (eds.) Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics, Map Alignment, and the Evolution of Gene Families, pp. 207–212. Kluwer Academic Publishers, Dordrecht (2000)Google Scholar
  7. 7.
    Caprara, A.: On the tightness of the alternating-cycle lower bound for sorting by reversals. J. Combin. Optimization 3, 149–182 (1999)zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    Chen, X., Zheng, J., Fu, Z., Nan, P., Zhong, Y., Lonardi, S., Jiang, T.: Computing the assignment of orthologous genes via genome rearrangement. In: Proc. 3rd Asia Pacific Bioinformatics Conf. (APBC 2005), pp. 363–378. Imperial College Press, London (2005)CrossRefGoogle Scholar
  9. 9.
    Cosner, M.E., Jansen, R.K., Moret, B.M.E., Raubeson, L.A., Wang, L., Warnow, T., Wyman, S.K.: An empirical comparison of phylogenetic methods on chloroplast gene order data in Campanulaceae. In: Sankoff, D., Nadeau, J.H. (eds.) Comparative Genomics, pp. 99–122. Kluwer Academic Publishers, Dordrecht (2000)Google Scholar
  10. 10.
    Downie, S.R., Palmer, J.D.: Use of chloroplast DNA rearrangements in reconstructing plant phylogeny. In: Soltis, D.E., Soltis, P.S., Doyle, J.J. (eds.) Molecular Systematics of Plants, pp. 14–35. Chapman and Hall, New York (1992)Google Scholar
  11. 11.
    Earnest-DeYoung, J., Lerat, E., Moret, B.M.E.: Reversing gene erosion: reconstructing ancestral bacterial genomes from gene-content and gene-order data. In: Jonassen, I., Kim, J. (eds.) WABI 2004. LNCS (LNBI), vol. 3240, pp. 1–13. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  12. 12.
    El-Mabrouk, N.: Genome rearrangement by reversals and insertions/deletions of contiguous segments. In: Giancarlo, R., Sankoff, D. (eds.) CPM 2000. LNCS, vol. 1848, pp. 222–234. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  13. 13.
    El-Mabrouk, N.: Reconstructing an ancestral genome using minimum segments duplications and reversals. J. Comput. Syst. Sci. 65, 442–464 (2002)zbMATHCrossRefMathSciNetGoogle Scholar
  14. 14.
    Hannenhalli, S., Pevzner, P.A.: Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals). In: Proc. 27th Ann. ACM Symp. Theory of Comput. (STOC 1995), pp. 178–189. ACM Press, New York (1995)CrossRefGoogle Scholar
  15. 15.
    Larget, B., Simon, D.L., Kadane, J.B.: Bayesian phylogenetic inference from animal mitochondrial genome arrangements. J. Royal Stat. Soc. B 64(4), 681–694 (2002)zbMATHCrossRefMathSciNetGoogle Scholar
  16. 16.
    Marron, M., Swenson, K.M., Moret, B.M.E.: Genomic distances under deletions and insertions. Theor. Computer Science 325(3), 347–360 (2004)zbMATHCrossRefMathSciNetGoogle Scholar
  17. 17.
    Moret, B.M.E., Tang, J., Warnow, T.: Reconstructing phylogenies from gene-content and gene-order data. In: Gascuel, O. (ed.) Mathematics of Evolution and Phylogeny, pp. 321–352. Oxford University Press, UK (2005)Google Scholar
  18. 18.
    Thach Nguyen, C., Tay, Y.C., Zhang, L.: Divide-and-conquer approach for the exemplar breakpoint distance. Bioinformatics 21(10), 2171–2176 (2005)CrossRefGoogle Scholar
  19. 19.
    Sankoff, D.: Genome rearrangement with gene families. Bioinformatics 15(11), 990–917 (1999)Google Scholar
  20. 20.
    Sankoff, D., Blanchette, M.: The median problem for breakpoints in comparative genomics. In: Jiang, T., Lee, D.T. (eds.) COCOON 1997. LNCS, vol. 1276, pp. 251–264. Springer, Heidelberg (1997)CrossRefGoogle Scholar
  21. 21.
    Sankoff, D., Blanchette, M.: Multiple genome rearrangement and breakpoint phylogeny. J. Comput. Biol. 5, 555–570 (1998)CrossRefGoogle Scholar
  22. 22.
    Sankoff, D., Bryant, D., Deneault, M., Lang, B.F., Burger, G.: Early Eukaryote evolution based on mitochondrial gene order breakpoints. J. Comput. Biol. 7(3), 521–536 (2000)CrossRefGoogle Scholar
  23. 23.
    Sankoff, D., Nadeau, J. (eds.): Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics, Map Alignment, and the Evolution of Gene Families. Kluwer Academic Publishers, Dordrecht (2000)zbMATHGoogle Scholar
  24. 24.
    Setubal, J.C., Meidanis, J.: Introduction to Computational Molecular Biology. PWS Publishers, Boston (1997)Google Scholar
  25. 25.
    Swenson, K.M., Marron, M., Earnest-DeYoung, J.V., Moret, B.M.E.: Approximating the true evolutionary distance between two genomes. In: Proc. 7th SIAM Workshop on Algorithm Engineering & Experiments (ALENEX 2005). SIAM Press, Philadelphia (2005)Google Scholar
  26. 26.
    Tang, J., Moret, B.M.E., Cui, L., de Pamphilis, C.W.: Phylogenetic reconstruction from arbitrary gene-order data. In: Proc. 4th IEEE Symp. on Bioinformatics and Bioengineering BIBE 2004, pp. 592–599. IEEE Press, Piscataway (2004)CrossRefGoogle Scholar
  27. 27.
    Tesler, G.: Efficient algorithms for multichromosomal genome rearrangements. J. Comput. Syst. Sci. 65(3), 587–609 (2002)zbMATHCrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Krister M. Swenson
    • 1
  • Nicholas D. Pattengale
    • 1
  • B. M. E. Moret
    • 1
  1. 1.Department of Computer ScienceUniversity of New MexicoAlbuquerqueUSA

Personalised recommendations