Maximizing Synteny Blocks to Identify Ancestral Homologs

  • Guillaume Bourque
  • Yasmine Yacef
  • Nadia El-Mabrouk
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3678)


Most genome rearrangement studies are based on the assumption that the compared genomes contain unique gene copies. This is clearly unsuitable for species with duplicated genes or when local alignment tools provide many ambiguous hits for the same gene. In this paper, we compare different measures of order conservation to select, among a gene family, the pair of copies in two genomes that best reflects the common ancestor. Specifically, we present algorithms to identify ancestral homologs, or exemplars [1] , by maximizing synteny blocks between genomes. Using simulated data, we validate our approach and show the merits of using a conservative approach when making such assignments.


Genome Rearrangement Conjunctive Normal Form Synteny Block False Prediction Breakpoint Distance 
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.
    Sankoff, D.: Genome rear. with gene fam. Bioinformatics 15, 909–917 (1999)Google Scholar
  2. 2.
    Kececioglu, J., Sankoff, D.: Exact and approx. algo. for sorting by reversals, with application to genome rear. Algorithmica 13, 180–210 (1995)zbMATHCrossRefMathSciNetGoogle Scholar
  3. 3.
    Hannenhalli, S., Pevzner, P.A.: Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals). J. ACM 48, 1–27 (1999)CrossRefMathSciNetGoogle Scholar
  4. 4.
    Kaplan, H., Shamir, R., Tarjan, R.E.: A faster and simpler algorithm for sorting signed permutations by reversals. SIAM Journal on Computing 29, 880–892 (2000)zbMATHCrossRefMathSciNetGoogle Scholar
  5. 5.
    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
  6. 6.
    Bergeron, A.: A very elementary presentation of the Hannenhalli-Pevzner theory. In: Amir, A., Landau, G.M. (eds.) CPM 2001. LNCS, vol. 2089, p. 106. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  7. 7.
    Bafna, V., Pevzner, P.A.: Sorting by transpositions. SIAM Journal on Discrete Mathematics 11(2), 224–240 (1998)zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    Walter, M.E., Dias, Z., Meidanis, J.: Reversal and transposition distance of linear chromosomes. In: String Proc. Information Retrieval (SPIRE 1998) (1998)Google Scholar
  9. 9.
    Hartman, T.: A simpler 1.5-approximation algorithm for sorting by transpositions. In: Baeza-Yates, R., Chávez, E., Crochemore, M. (eds.) CPM 2003. LNCS, vol. 2676, pp. 156–169. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  10. 10.
    Hannenhalli, S., Pevzner, P.A.: Transforming men into mice (polynomial algorithm for genomic distance problem). In: Proc. IEEE 36th Ann. Symp. Found. Comp. Sci., pp. 581–592 (1995)Google Scholar
  11. 11.
    Tesler, G.: Efficient algorithms for multichromosomal genome rearrangements. J. Comp. System Sci. 65(3), 587–609 (2002)zbMATHCrossRefMathSciNetGoogle Scholar
  12. 12.
    Ozery-Flato, M., Shamir, R.: Two notes on genome rearrangnements. J. of Bioinf. and Comput. Biol. 1(1), 71–94 (2003)CrossRefGoogle Scholar
  13. 13.
    Burgetz, I.J., Shariff, S., Pang, A., Tillier, E.: Positional homology in bacterial genomes. manuscript (2005)Google Scholar
  14. 14.
    Bergeron, A., Stoye, J.: On the similarity of sets of permutations and its app. to genome comparison. In: Warnow, T.J., Zhu, B. (eds.) COCOON 2003. LNCS, vol. 2697, pp. 68–79. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  15. 15.
    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)CrossRefGoogle Scholar
  16. 16.
    Figeac, M., Varré, J.S.: Sorting by reversals with common intervals. In: Jonassen, I., Kim, J. (eds.) WABI 2004. LNCS (LNBI), vol. 3240, pp. 26–37. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  17. 17.
    Bérard, S., Bergeron, A., Chauve, C.: Conservation of combinatorial structures in evolution scenarios. In: Lagergren, J. (ed.) RECOMB-WS 2004. LNCS (LNBI), vol. 3388, pp. 1–14. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  18. 18.
    Tang, J., Moret, B.M.E.: Phylogenetic reconstruction from gene rearrangement data with unequal gene contents. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol. 2748, pp. 37–46. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  19. 19.
    Chen, X., Zheng, J., Fu, Z., Nan, P., Zhing, Y., Lonardi, S., Jiang, T.: Assignment of orthologous genes via genome rearrangement. In: TCCB (2005) (accepted)Google Scholar
  20. 20.
    Bryant, D.: The complexity of calculating exemplar distances. In: Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics, Map alignment and the Evolution of Gene Families. Series in Computational Biology, vol. 1. Kluwer Academic Publishers, Dordrecht (2000)Google Scholar
  21. 21.
    Nguyen, C.T., Tay, Y.C., Zhang, L.: Divide-and-conquer approach for the exemplar breakpoint distance. Bioinformatics (2005)Google Scholar
  22. 22.
    Blin, G., Chauve, C., Fertin, G.: The breakpoint distance for signed sequences. In: Texts in Algorithm, vol. 3, pp. 3–16. KCL publications (2004)Google Scholar
  23. 23.
    Marron, M., Swenson, K.M., Moret, B.M.E.: Genomic distances under deletions and insertions. Theoretical Computer Science 325, 347–360 (2004)zbMATHCrossRefMathSciNetGoogle Scholar
  24. 24.
    Swenson, K.M., Marron, M., Earnest-DeYoung, J.V., Moret, B.M.E.: Approximating the true evolutionary distance between two genomes. In: 7th Workshop on Algorithm Engineering and Experiments (ALENEX 2005). SIAM Press, Philadelphia (2005)Google Scholar
  25. 25.
    Lefebvre, J.F., El-Mabrouk, N., Tillier, E., Sankoff, D.: Detection and validation of single gene inversions. Bioinformatics 19, 190i–196i (2003)Google Scholar
  26. 26.
    Pevzner, P., Tesler, G.: Human and mouse genomic sequences reveal extensive breakpoint reuse in mamm. evol. PNAS, U.S.A. 100(13), 7672–7677 (2003)CrossRefGoogle Scholar
  27. 27.

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Guillaume Bourque
    • 1
  • Yasmine Yacef
    • 2
  • Nadia El-Mabrouk
    • 2
  1. 1.Genome Institute of SingaporeSingapore
  2. 2.DIROUniversité de MontréalCanada

Personalised recommendations