Advertisement

Reversals of Fortune

  • David Sankoff
  • Chungfang Zheng
  • Aleksander Lenert
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3678)

Abstract

The objective function of the genome rearrangement problems allows the integration of other genome-level problems so that they may be solved simultaneously. Three examples, all of which are hard: 1) Orientation assignment for unsigned genomes. 2 ) Ortholog identification in the presence of multiple copies of genes. 3) Linearisation of partially ordered genomes. The comparison of traditional genetic maps by rearrangement algorithms poses all these problems. We combine heuristics for the first two problems with an exact algorithm for the third to solve a moderate-sized instance comparing maps of cereal genomes.

Keywords

Directed Acyclic Graph Genome Rearrangement Sign Assignment Black Edge Sorghum Chromosome 
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.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    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) (in press)CrossRefGoogle Scholar
  2. 2.
    Bourque, G., Pevzner, P.A., Tesler, G.: Reconstructing the genomic architecture of ancestral mammals: lessons from human, mouse, and rat genomes. Genome Research 14, 507–516 (2004)CrossRefGoogle Scholar
  3. 3.
    Bourque, G., Yacef, Y., El-Mabrouk, N.: Maximizing synteny blocks to identify ancestral homologs. manuscript (2005)Google Scholar
  4. 4.
    Bourque, G., Zdobnov, E., Bork, P., Pevzner, P., Tesler, G.: Comparative architectures of mammalian and chicken genomes reveal highly variable rates of genomic rearrangements across different lineages. Genome Research 15, 98–110 (2005)CrossRefGoogle Scholar
  5. 5.
    Bowers, J.E., Abbey, C., Anderson, S., Chang, C., Draye, X., Hoppe, A.H., Jessup, R., Lemke, C., Lennington, J., Li, Z., Lin, Y.R., Liu, S.C., Luo, L., Marler, B.S., Ming, R., Mitchell, S.E., Qiang, D., Reischmann, K., Schulze, S.R., Skinner, D.N., Wang, Y.W., Kresovich, S., Schertz, K.F., Paterson, A.H.: A high-density genetic recombination map of sequence-tagged sites for sorghum, as a framework for comparative structural and evolutionary genomics of tropical grains and grasses. Genetics 165, 367–386 (2003)Google Scholar
  6. 6.
    Bryant, D.: The complexity of calculating exemplar distances. In: Sankoff, D., Nadeau, J. (eds.) Comparative Genomics, pp. 207–212. Kluwer, Dordrecht (2000)Google Scholar
  7. 7.
    Caprara, A.: Sorting by reversals is difficult. In: Istrail, S., Pevzner, P.A., Waterman, M.S. (eds.) Proceedings of the First Annual International Conference on Computational Molecular Biology (RECOMB 1997), pp. 75–83. ACM Press, New York (1997)CrossRefGoogle Scholar
  8. 8.
    Caprara, A., Lancia, G., Ng, S.K.: Sorting permutations by reversals through branch-and-price. INFORMS Journal on Computing 13, 224–244 (2001)CrossRefMathSciNetGoogle Scholar
  9. 9.
    Chen, X., Zheng, J., Fu, Z., Nan, P., Zhong, Y., Lonardi, S., Jiang, T.: Assignment of orthologous genes via genome rearrangement. IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) (2005) (in press)Google Scholar
  10. 10.
    Christie, D.A.: Sorting permutations by block interchanges. Information Processing Letters 60, 165–169 (1996)CrossRefMathSciNetGoogle Scholar
  11. 11.
    Friedberg, R., Attie, O., Yancopoulos, S.: Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics (2005) (in press)Google Scholar
  12. 12.
    I-Mabrouk, N., Sankoff, D.: The reconstruction of doubled genomes. SIAM Journal on Computing 32, 754–792 (2003)zbMATHCrossRefMathSciNetGoogle Scholar
  13. 13.
    Gaut, B.S., Doebley, J.F.: DNA sequence evidence for the segmental allotetraploid origin of maize. Proc. Natl. Acad. Sci. U S A. 94, 6809–6814 (1997)CrossRefGoogle Scholar
  14. 14.
    Hannenhalli, S., Pevzner, P.A.: Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals). In: Proc. 27th Annual ACM Symposium on the Theory of Computing, pp. 178–189 (1995)Google Scholar
  15. 15.
    Hannenhalli, S., Pevzner, P.A.: Transforming men into mice (polynomial algorithm for genomic distance problem. In: Proceedings of the IEEE 36th Annual Symposium on Foundations of Computer Science, pp. 581–592 (1995)Google Scholar
  16. 16.
    Hannenhalli, S., Pevzner, P.A.: To cut or not to cut (applications of comparative physical maps in molecular evolution). In: Proceedings of the 7th annual ACM-SIAM symposium on discrete algorithms, pp. 304–313. SIAM, Philadelphia (1996)Google Scholar
  17. 17.
    Kececioglu, J., Sankoff, D.: Exact and approximation algorithms for the inversion distance between two permutations. In: Apostolico, A., Crochemore, M., Galil, Z., Manber, U. (eds.) CPM 1993. LNCS, vol. 684, pp. 87–105. Springer, Heidelberg (1993); Cf. Algorithmica 13, 180–210 (1995)CrossRefGoogle Scholar
  18. 18.
    Menz, M.A., Klein, R.R., Mullet, J.E., Obert, J.A., Unruh, N.C., Klein, P.E.: A high-density genetic map of Sorghum bicolor (L.) Moench based on 2926 AFLP, RFLP and SSR markers. Plant Molecular Biology 48, 483–499 (2002)CrossRefGoogle Scholar
  19. 19.
    Morgan, T.H., Sturtevant, A.H., Muller, H.J., Bridges, C.B.: The mechanism of Mendelian heredity. Henry Holt. and Co., New York (1915)Google Scholar
  20. 20.
    NCBI Human Mouse Homology, http://www.ncbi.nlm.nih.gov/Homology/
  21. 21.
    Nicholas, F.W., Barendse, W., Collins, A., Darymple, B.P., Edwards, J.H., Gregory, S., Hobbs, M., Khatkar, M.S., Liao, W., Maddox, J.F., Raadsma, H.W., Zenger, K.R.: Integrated maps and Oxford grids: maximising the power of comparative mapping. Poster at International Society of Animal Genetics (2004)Google Scholar
  22. 22.
    Nguyen, C.T., Tay, Y.C., Zhang, L.: Divide-and-conquer approach for the exemplar breakpoint distance. Bioinformatics (2005) (in press)Google Scholar
  23. 23.
    Palmer, J.D., Osorio, B., Thompson, W.F.: Evolutionary significance of inversions in legume chloroplast DNAs. Current Genetics 14, 6574 (1988)CrossRefGoogle Scholar
  24. 24.
    Pevzner, P.A., Tesler, G.: Human and mouse genomic sequences reveal extensive breakpoint reuse in mammalian evolution. Proc. Natl. Acad. Sci. U.S.A. 100, 7672–7677 (2003)CrossRefGoogle Scholar
  25. 25.
    Polacco, M.L., Coe Jr., E.: IBM Neighbors: A Consensus Genetic Map (2002), http://www.maizegdb.org/ancillary/IBMneighbors.html
  26. 26.
    Radcliffe, A.J., Scott, A.D., Wilmer, R.E.: Reversals and transpositions over finite alphabets. SIAM Journal on Discrete Math (2005) (in press)Google Scholar
  27. 27.
    Sankoff, D.: Genome rearrangement with gene families. Bioinformatics 15, 909–917 (1999)CrossRefGoogle Scholar
  28. 28.
    Sankoff, D., El-Mabrouk, N.: Duplication, rearrangement and reconciliation. In: Sankoff, D., Nadeau, J.H. (eds.) Comparative Genomics. Kluwer, Dordrecht (2000)Google Scholar
  29. 29.
    Sankoff, D., Leduc, G., Antoine, N., Paquin, B., Lang, B.F., Cedergren, R.: Gene order comparisons for phylogenetic inference: Evolution of the mitochondrial genome. Proc. Natl. Acad. Sci. USA 89, 6575–6579 (1992)CrossRefGoogle Scholar
  30. 30.
    Sturtevant, A.H.: The linear arrangement of six sex-linked factors in Drosophila, as shown by their mode of association. Jour. Exp. Zool. 14, 43–59 (1913)CrossRefGoogle Scholar
  31. 31.
    Sturtevant, A.H.: Genetic studies on Drosophila simulans. II. Sex-linked group of genes. Genetics 6, 43–64 (1921)Google Scholar
  32. 32.
    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
  33. 33.
    Tesler, G.: GRIMM: genome rearrangements web server. Bioinformatics 18, 492–493 (2002)CrossRefGoogle Scholar
  34. 34.
    Tesler, G.: Efficient algorithms for multichromosomal genome rearrangements. Journal of Computer and System Sciences 65, 587–609 (2002)zbMATHCrossRefMathSciNetGoogle Scholar
  35. 35.
    UCSC Genome BrowserGoogle Scholar
  36. 36.
    Ware, D., Jaiswal, P., Ni, J., Pan, X., Chang, K., Clark, K., Teytelman, L., Schmidt, S., Zhao, W., Cartinhour, S., McCouch, S., Stein, L.: Gramene: a resource for comparative grass genomics. Nucleic Acids Research 30, 103–105 (2002)CrossRefGoogle Scholar
  37. 37.
    Zheng, C., Lenert, A., Sankoff, D.: Reversal distance for partially ordered genomes. Bioinformatics 21 (2005) (in press)Google Scholar
  38. 38.
    Zheng, C., Sankoff, D.: Genome rearrangements with partially ordered chromosomes. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 52–62. Springer, Heidelberg (2005) (in press)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • David Sankoff
    • 1
  • Chungfang Zheng
    • 2
  • Aleksander Lenert
    • 3
  1. 1.Department of Mathematics and StatisticsUniversity of OttawaCanada
  2. 2.Department of BiologyUniversity of OttawaCanada
  3. 3.Program in Biopharmaceutical ScienceUniversity of OttawaCanada

Personalised recommendations