Springer Protocols: Abstract: 18. Genome Rearrangement by the Double Cut and Join Operation

18. Genome Rearrangement by the Double Cut and Join Operation

By: Richard Friedberg³, Aaron E. Darling⁴, Sophia Yancopoulos⁵

Abstract

Full Text

Download PDF (9042K)

The Double Cut and Join is an operation acting locally at four chromosomal positions without regard to chromosomal context. This chapter discusses its application and the resulting menu of operations for genomes consisting of arbitrary numbers of circular chromosomes, as well as for a general mix of linear and circular chromosomes. In the general case the menu includes: inversion, translocation, transposition, formation and absorption of circular intermediates, conversion between linear and circular chromosomes, block interchange, fission, and fusion. This chapter discusses the well-known edge graph and its dual, the adjacency graph, recently introduced by Bergeron et al. Step-by-step procedures are given for constructing and manipulating these graphs. Simple algorithms are given in the adjacency graph for computing the minimal DCJ distance between two genomes and finding a minimal sorting; and use of an online tool (Mauve) to generate synteny blocks and apply DCJ is described.

Affiliation(s): (3) Department of Physics, Columbia University, New York, NY
(4) ARC Centre of Excellence in Bioinformatics, and Institute for Molecular Bioscience, The University of Queensland, Brisbane, Queensland, Australia
(5) The Feinstein Institute for Medical Research, Manhasset, NY

Book Title: Bioinformatics: Data, Sequence Analysis and Evolution

Series: Methods in Molecular Biology | Volume: 452 | Pub. Date: May-01-2008 | Page Range: 385-416 | DOI: 10.1007/978-1-60327-159-2_18

Subject: Bioinformatics

Key Words: Genome rearrangements - gene order - Mauve - synteny - inversion - reversal - transloca-tion - transposition - block interchange - fission - fusion

References

Download References

1.	Nadeau, J. H., Taylor, B. A. (1984) Lengths of chromosomal segments conserved since divergence of man and mouse. Proc Natl Acad Sci U S A 81, 814–818.

2.	Pevzner, P. A. (2000) Computational Molecular Biology: An Algorithmic Approach. MIT Press, Cambridge, MA.

3.	Yancopoulos, S., Attie, O., Friedberg, R. (2005) Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics 21, 3340–3346

4.	Bergeron, A., Mixtacki, J., Stoye, J. (2006) A unifying view of genome rearrangements. WABI 2006, 163–173.

5.	Christie, D. A. (1996) Sorting permutations by block interchanges. Inform Proc Lett 60,165–169.

6.	Lin, Y. C., et al. (2005) An efficient algorithm for sorting by block-interchanges and its application to the evolution of Vibrio species. J Comput Biol 12, 102112.

7.	Meidanis, J., Dias, Z. (2001) Genome rearrangements distance by fusion, fission, and transposition is easy. In Proceedings of SPIRE'2001—String Processing and Information Retrieval, Laguna de San Rafael, Chile.

8.	Kececioglu, J., Sankoff, D. (1995) Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement. Algorithmica 13, 180–210.

9.	Bergeron, A., private communication.

10.	Bafna, V., Pevzner, P.A. (1993) Genome rearrangements and sorting by reversals. In Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, IEEE Press, Los Alamitos, CA.

11.	Hannenhalli, S., Pevzner, P. A. (1995) Transforming men into mice (polynomial algorithm for genomic distance problem). In Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, Milwaukee, WI.

12.	Darling, A. C. E., Mau, B., Blattner, F. R., et al. (2004) Mauve: multiple alignment of conserved genomic sequence with rearrangements. Genome Res 14, 1394–1403.

13.	Darling, A. E., Treangen, T. J., Zhang, L., et al. (2006) Procrastination leads to efficient filtration for local multiple alignment. Lecture Notes in Bioinformatics. Springer-Verlag, New York.

14.	Darling, A. E., Treangen, T. J., Messeguer, X., et al. (2007) Analyzing patterns of microbial evolution using the Mauve genome alignment system, in (Bergman, ed.), Comparative Genomics. Humana Press, Totowa, NJ, in press.

Comments (Loading...)

Post comment/View all comments