Genes Order and Phylogenetic Reconstruction: Application to γ-Proteobacteria

  • Guillaume Blin
  • Cedric Chauve
  • Guillaume Fertin
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3678)


We study the problem of phylogenetic reconstruction based on gene order for whole genomes. We define three genomic distances between whole genomes represented by signed sequences, based on the matching of similar segments of genes and on the notions of breakpoints, conserved intervals and common intervals. We use these distances and distance based phylogenetic reconstruction methods to compute a phylogeny for a group of 12 complete genomes of γ-Proteobacteria.


Phylogenetic reconstruction breakpoints common intervals conserved intervals γ-Proteobacteria gene families 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Altschul, S.F., Maden, T.L., Schaffer, A.A., Zhang, J., Zhang, Z., Miller, W., Lipman, D.J.: Gapped blast and psi-blast: a new generation of protein database search programs. Nucleic Acids Res. 25(17), 3389–3402 (1997)CrossRefGoogle Scholar
  2. 2.
    Belda, E., Moya, A., Silva, F.J.: Genome rearrangement distances and gene order phylogeny in γ-proteobacteria. Mol. Biol. Evol. 22(6), 1456–1467 (2005)CrossRefGoogle Scholar
  3. 3.
    Bérard, S., Bergeron, A., Chauve, C.: Conserved structures in evolution scenarios. In: Lagergren, J. (ed.) RECOMB-WS 2004. LNCS (LNBI), vol. 3388, pp. 1–15. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  4. 4.
    Bergeron, A., Stoye, J.: On the similarity of sets of permutations and its applications to genome comparison. In: Warnow, T.J., Zhu, B. (eds.) COCOON 2003. LNCS, vol. 2697, pp. 68–79. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  5. 5.
    Blanchette, M., Kunisawa, T., Sankoff, D.: Gene order breakpoint evidence in animal mitochondrial phylogeny. J. Mol. Evol. 49(2), 193–203 (1999)CrossRefGoogle Scholar
  6. 6.
    Blin, G., Chauve, C., Fertin, G.: The breakpoints distance for signed sequences. In: 1st International Conference on Algorithms and Computational Methods for Biochemical and Evolutionary Networks, CompBioNets 2004. Texts in Algorithms, vol. 3, pp. 3–16. KCL Publications (2004)Google Scholar
  7. 7.
    Blin, G., Rizzi, R.: Conserved interval distance computation between non-trivial genomes. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 22–31. Springer, Heidelberg (2005) (to appear)CrossRefGoogle Scholar
  8. 8.
    Bourque, G., Pevzner, P.A., Tesler, G.: Reconstructing the genomic architecture of ancestral mammals: lessons from human, mouse and rat genomes. Genome Res. 14(4), 507–516 (2004)CrossRefGoogle Scholar
  9. 9.
    Bourque, G., Zdobnov, E.M., Bork, P., Pevzner, P.A., Tesler, G.: Comparative architectures of mammalian and chicken genomes reveal highly variable rates of genomic rearrangements across different lineages. Genome Res. 15(1), 98–110 (2005)CrossRefGoogle Scholar
  10. 10.
    Chen, X., Zheng, J., Fu, Z., Nan, P., Zhong, Y., Lonardi, S., Jiang, T.: Computing the assignment of orthologous genes via genome rearrangement. In: 3rd Asia-Pacific Bioinformatics Conference 2005, pp. 363–378. Imperial College Press (2005)Google Scholar
  11. 11.
    Earnest-DeYoung, J.V., Lerat, E., Moret, B.M.E.: Reversing gene erosion: Reconstructing ancestral bacterial genomes from gene-content and order data. In: Jonassen, I., Kim, J. (eds.) WABI 2004. LNCS (LNBI), vol. 3240, pp. 1–13. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  12. 12.
    Gascuel, O. (ed.): Mathematics of Evolution and Phylogeny. Oxford University Press, Oxford (2005)zbMATHGoogle Scholar
  13. 13.
    Herbeck, J.T., Degnan, P.H., Wernegreen, J.J.: Nonhomogeneous model of sequence evolution indicates independent origins of primary endosymbionts within the enterobacteriales (γ-proteobacteria). Mol. Biol. Evol. 22(3), 520–532 (2004)CrossRefGoogle Scholar
  14. 14.
    Lefebvre, J.-F., El-Mabrouk, N., Tillier, E., Sankoff, D.: Detection and validation of single gene inversions. Bioinformatics 19(suppl. 1), i190–i196 (2003)Google Scholar
  15. 15.
    Lerat, E., Daubin, V., Moran, N.A.: From gene tree to organismal phylogeny in prokaryotes: the case of γ-proteobacteria. PLoS Biology 1(1), 101–109 (2003)CrossRefGoogle Scholar
  16. 16.
    Sankoff, D.: Genome rearrangement with gene families. Bioinformatics 15(11), 909–917 (1999)CrossRefGoogle Scholar
  17. 17.
    Sankoff, D.: Short inversions and conserved gene clusters. Bioinformatics 18(10), 1305–1308 (2002)CrossRefGoogle Scholar
  18. 18.
    Sankoff, D., Lefebvre, J.-F., Tillier, E., Maler, A., El-Mabrouk, N.: The distribution of inversion lengths in prokaryotes. In: Lagergren, J. (ed.) RECOMB-WS 2004. LNCS (LNBI), vol. 3388, pp. 97–108. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  19. 19.
    Swenson, K.M., Marron, M., Earnest-DeYoung, J.V., Moret, B.M.E.: Approximating the true evolutionary distance between two genomes. In: Proceedings of the seventh Workshop on Algorithms Engineering and Experiments and Second Workshop on Analytic Algorithmics and Combinatorics (ALENEX/ANALCO 2005), SIAM, Philadelphia (2005)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Guillaume Blin
    • 1
  • Cedric Chauve
    • 2
  • Guillaume Fertin
    • 1
  1. 1.LINA FRE CNRS 2729Université de NantesNantes Cedex 3France
  2. 2.LaCIM et Département d’InformatiqueUniversité du Québec À MontréalMontréal (QC)Canada

Personalised recommendations