Bioinformatics Vol. 19 Suppl. 1 2003
Pages i54-i62
© 2003 Oxford University Press
Glocal alignment: finding rearrangements during alignment
1 Department of Computer Science, Stanford University,
Stanford, CA 94305
2 Life Sciences Division, Lawrence Berkeley
National Laboratory, Berkeley, CA 94720,
USA
Received on January 6, 2003
; accepted on February 20, 2000
Motivation: To compare entire genomes from different species, biologists increasingly need alignment methods that are efficient enough to handle long sequences, and accurate enough to correctly align the conserved biological features between distant species. The two main classes of pairwise alignments are global alignment, where one string is transformed into the other, and local alignment, where all locations of similarity between the two strings are returned. Global alignments are less prone to demonstrating false homology as each letter of one sequence is constrained to being aligned to only one letter of the other. Local alignments, on the other hand, can cope with rearrangements between non-syntenic, orthologous sequences by identifying similar regions in sequences; this, however, comes at the expense of a higher false positive rate due to the inability of local aligners to take into account overall conservation maps.
Results: In this paper we introduce the notion of glocal alignment, a combination of global and local methods, where one creates a map that transforms one sequence into the other while allowing for rearrangement events. We present Shuffle-LAGAN, a glocal alignment algorithm that is based on the CHAOS local alignment algorithm and the LAGAN global aligner, and is able to align long genomic sequences. To test Shuffle-LAGAN we split the mouse genome into BAC-sized pieces, and aligned these pieces to the human genome. We demonstrate that Shuffle-LAGAN compares favorably in terms of sensitivity and specificity with standard local and global aligners. From the alignments we conclude that about 9% of human/mouse homology may be attributed to small rearrangements, 63% of which are duplications.
Availability: Our systems, supplemental information, and the alignment of the human and mouse genomes using Shuffle-LAGAN are available at http://lagan.stanford.edu/glocal
Contact: serafim{at}cs.stanford.edu
* To whom correspondence should be addressed.
These authors contributed equally to
the work.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  V. Ravi, K. Lam, B.-H. Tay, A. Tay, S. Brenner, and B. Venkatesh Elephant shark (Callorhinchus milii) provides insights into the evolution of Hox gene clusters in gnathostomes PNAS, September 22, 2009; 106(38): 16327 - 16332. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 T.-C. Chu, T. Liu, D. T. Lee, G. C. Lee, and A. C.-C. Shih GR-Aligner: an algorithm for aligning pairwise genomic sequences containing rearrangement events Bioinformatics, September 1, 2009; 25(17): 2188 - 2193. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 G. Elgar Pan-vertebrate conserved non-coding sequences associated with developmental regulation Briefings in Functional Genomics, July 1, 2009; 8(4): 256 - 265. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 I. Dubchak, A. Poliakov, A. Kislyuk, and M. Brudno Multiple whole-genome alignments without a reference organism Genome Res., April 1, 2009; 19(4): 682 - 689. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
B. Paten, J. Herrero, S. Fitzgerald, K. Beal, P. Flicek, I. Holmes, and E. Birney Genome-wide nucleotide-level mammalian ancestor reconstruction Genome Res., November 1, 2008; 18(11): 1829 - 1843. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
B. Paten, J. Herrero, K. Beal, S. Fitzgerald, and E. Birney Enredo and Pecan: Genome-wide mammalian consistency-based multiple alignment with paralogs Genome Res., November 1, 2008; 18(11): 1814 - 1828. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
L. Z. Holland, R. Albalat, K. Azumi, E. Benito-Gutierrez, M. J. Blow, M. Bronner-Fraser, F. Brunet, T. Butts, S. Candiani, L. J. Dishaw, et al. The amphioxus genome illuminates vertebrate origins and cephalochordate biology Genome Res., July 1, 2008; 18(7): 1100 - 1111. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 R. Alvarez-Medina, J. Cayuso, T. Okubo, S. Takada, and E. Marti Wnt canonical pathway restricts graded Shh/Gli patterning activity through the regulation of Gli3 expression Development, January 15, 2008; 135(2): 237 - 247. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
P. G. Engstrom, S. J. Ho Sui, O. Drivenes, T. S. Becker, and B. Lenhard Genomic regulatory blocks underlie extensive microsynteny conservation in insects Genome Res., December 1, 2007; 17(12): 1898 - 1908. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 M. Brudno, A. Poliakov, S. Minovitsky, I. Ratnere, and I. Dubchak Multiple whole genome alignments and novel biomedical applications at the VISTA portal Nucleic Acids Res., July 13, 2007; 35(suppl_2): W669 - W674. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
K. S. Small, M. Brudno, M. M. Hill, and A. Sidow Extreme genomic variation in a natural population PNAS, March 27, 2007; 104(13): 5698 - 5703. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Kumar and A. Filipski Multiple sequence alignment: In pursuit of homologous DNA positions Genome Res., February 1, 2007; 17(2): 127 - 135. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. Tran, P. Havlak, and J. Miller MicroRNA enrichment among short 'ultraconserved' sequences in insects. Nucleic Acids Res., January 1, 2006; 34(9): e65 - e65. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
G. M. Cooper, E. A. Stone, G. Asimenos, NISC Comparative Sequencing Program, E. D. Green, S. Batzoglou, and A. Sidow Distribution and intensity of constraint in mammalian genomic sequence Genome Res., July 1, 2005; 15(7): 901 - 913. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. Brudno, A. Poliakov, A. Salamov, G. M. Cooper, A. Sidow, E. M. Rubin, V. Solovyev, S. Batzoglou, and I. Dubchak Automated Whole-Genome Multiple Alignment of Rat, Mouse, and Human Genome Res., April 1, 2004; 14(4): 685 - 692. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. E. Abbas and S. P. Holmes Bioinformatics and Management Science: Some Common Tools and Techniques Operations Research, March 1, 2004; 52(2): 165 - 190. [Abstract] [PDF]
|
|