Polynomial-time algorithm for computing translocation distance between genomes | SpringerLink
Skip to main content

Polynomial-time algorithm for computing translocation distance between genomes

  • Conference paper
  • First Online:
Combinatorial Pattern Matching (CPM 1995)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 937))

Included in the following conference series:

Abstract

With the advent of large-scale DNA physical mapping and sequencing, studies of genome rearrangements are becoming increasingly important in evolutionary molecular biology. From a computational perspective, study of evolution based on rearrangements leads to rearrangement distance problem, i.e., computing the minimum number of rearrangement events required to transform one genome into another. Different types of rearrangement events give rise to a spectrum of interesting combinatorial problems. The complexity of most of these problems is unknown. Multichromosomal genomes frequently evolve by a rearrangement event called translocation which exchanges genetic material between different chromosomes. In this paper we study the translocation distance problem, modeling evolution of genomes evolving by translocations. Translocation distance problem was recently studied for the first time by Kececioglu and Ravi, who gave a 2-approximation algorithm for computing translocation distance. In this paper we prove a duality theorem leading to a polynomial algorithm for computing translocation distance for the case when the orientation of the genes are known. This leads to an algorithm generating a most parsimonious (shortest) scenario, transforming one genome into another by translocations.

This work is supported by NSF Young Investigator award CCR-9457784 and NIH grant 1R01 HG00987.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. V. Bafna and P. Pevzner. Genome rearrangements and sorting by reversals. In 34th IEEE Symp. on Foundations of Computer Science, pages 148–157, 1993. (to appear in SIAM J. Computing).

    Google Scholar 

  2. V. Bafna and P. Pevzner. Sorting by reversals: Genome rearrangements in plant organelles and evolutionary history of X chromosome. Mol. Biol. and Evol., 12:239–246, 1995.

    Google Scholar 

  3. V. Bafna and P. Pevzner. Sorting by transpositions. In Proc. of 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 614–623, 1995b.

    Google Scholar 

  4. N. G. Copeland, N. A. Jenkins, D. J. Gilbert, J. T. Eppig, L. J. Maltals, J. C. Miller, W. F. Dietrich, A. Weaver, S. E. Lincoln, R. G. Steen, L. D. Steen, J. H. Nadeau, and E. S. Lander. A genetic linkage map of the mouse: Current applications and future prospects. Science, 262:57–65, 1993.

    PubMed  Google Scholar 

  5. S. Hannenhalli, C. Chappey, E. Koonin, and P. Pevzner. Scenarios for genome rearrangements: Herpesvirus evolution as a test case. In Proc. of 3rd Intl. Conference on Bioinformatics and Complex Genome Analysis, pages 91–106, 1995.

    Google Scholar 

  6. S. Hannenhalli and P. Pevzner. Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals). In Proc. of 27th Annual ACM Symposium on the Theory of Computing, 1995a. (to appear).

    Google Scholar 

  7. S. Hannenhalli and P. Pevzner. Reversals do not cut long strips. Technical Report: CSE-94-074, Department of Computer Science and Engineering, The Pennsylvania State University, 1995c.

    Google Scholar 

  8. J. Kececioglu and R. Ravi. Of mice and men: Evolutionary distances between genomes under translocation. In Proc. of 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 604–613, 1995.

    Google Scholar 

  9. J. Kececioglu and D. Sankoff. Exact and approximation algorithms for the inversion distance between two permutations. In Proc. of 4th Ann. Symp. on Combinatorial Pattern Matching, Lecture Notes in Computer Science 684, pages 87–105. Springer Verlag, 1993. (Extended version has appeared in Algorithmica, 13: 180–210, 1995.).

    Google Scholar 

  10. J. Kececioglu and D. Sankoff. Efficient bounds for oriented chromosome inversion distance. In Proc. of 5th Ann. Symp. on Combinatorial Pattern Matching, Lecture Notes in Computer Science 807, pages 307–325. Springer Verlag, 1994.

    Google Scholar 

  11. B. Lewin. Genes V. Oxford University Press, 1994.

    Google Scholar 

  12. D. Sankoff. Edit distance for genome comparison based on non-local operations. In Proc. of 3rd Ann. Symp. on Combinatorial Pattern Matching, Lecture Notes in Computer Science 644, pages 121–135. Springer Verlag, 1992.

    Google Scholar 

  13. D. Sankoff, R. Cedergren, and Y. Abel. Genomic divergence through gene rearrangement. In Molecular Evolution: Computer Analysis of Protein and Nucleic Acid Sequences, chapter 26, pages 428–438. Academic Press, 1990.

    Google Scholar 

  14. D. Sankoff, G. Leduc, N. Antoine, B. Paquin, B. F. Lang, and R. Cedergren. Gene order comparisons for phylogenetic inference: Evolution of the mitochondrial genome. Proc. Natl. Acad. Sci. USA, 89:6575–6579, 1992.

    PubMed  Google Scholar 

  15. E. Therman and M. Susman. Human Chromosomes, structure, behavior, and effects. Springer-Verlag, 1993.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Zvi Galil Esko Ukkonen

Rights and permissions

Reprints and permissions

Copyright information

© 1995 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Hannenhalli, S. (1995). Polynomial-time algorithm for computing translocation distance between genomes. In: Galil, Z., Ukkonen, E. (eds) Combinatorial Pattern Matching. CPM 1995. Lecture Notes in Computer Science, vol 937. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60044-2_41

Download citation

  • DOI: https://doi.org/10.1007/3-540-60044-2_41

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-60044-2

  • Online ISBN: 978-3-540-49412-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics