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.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
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).
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.
V. Bafna and P. Pevzner. Sorting by transpositions. In Proc. of 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 614–623, 1995b.
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.
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.
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).
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.
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.
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.).
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.
B. Lewin. Genes V. Oxford University Press, 1994.
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.
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.
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.
E. Therman and M. Susman. Human Chromosomes, structure, behavior, and effects. Springer-Verlag, 1993.
Author information
Authors and Affiliations
Editor information
Rights 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