Genome Research scroll

Home Help [Feedback] [For Subscribers] [Archive] [Search] [Contents]
QUICK SEARCH:   [advanced]


     

Published online before print March 12, 2003, 10.1101/gr.926603
This Article
Right arrow Full Text
Right arrow Full Text (PDF)
Right arrow All Versions of this Article:
GR-9266Rv1
13/4/721    most recent
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Right arrow Citation Map
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Download to citation manager
Right arrow reprints & permissions
Citing Articles
Right arrow Citing Articles via HighWire
Right arrow Citing Articles via Google Scholar
Google Scholar
Right arrow Articles by Brudno, M.
Right arrow Articles by Batzoglou, S.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Brudno, M.
Right arrow Articles by Batzoglou, S.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us   Add to Digg   Add to Reddit   Add to Technorati  
What's this?
Vol 13, Issue 4, 721-731, April 2003

METHODS

LAGAN and Multi-LAGAN: Efficient Tools for Large-Scale Multiple Alignment of Genomic DNA

Michael Brudno1, Chuong B. Do1, Gregory M. Cooper2, Michael F. Kim1, Eugene Davydov1, NISC Comparative Sequencing Program1, Eric D. Green3, Arend Sidow2 and Serafim Batzoglou1,4

1Department of Computer Science, Stanford University, Stanford, California 94305-9010, USA; 2Department of Pathology and Department of Genetics, Stanford University, Stanford, California 94305-5324, USA; 3Genome Technology Branch and NIH Intramural Sequencing Center, National Human Genome Research Institute, National Institutes of Health, Bethesda, Maryland 20892, USA

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. We present LAGAN, a system for rapid global alignment of two homologous genomic sequences, and Multi-LAGAN, a system for multiple global alignment of genomic sequences. We tested our systems on a data set consisting of greater than 12 Mb of high-quality sequence from 12 vertebrate species. All the sequence was derived from the genomic region orthologous to an ~1.5-Mb region on human chromosome 7q31.3. We found that both LAGAN and Multi-LAGAN compare favorably with other leading alignment methods in correctly aligning protein-coding exons, especially between distant homologs such as human and chicken, or human and fugu. Multi-LAGAN produced the most accurate alignments, while requiring just 75 minutes on a personal computer to obtain the multiple alignment of all 12 sequences. Multi-LAGAN is a practical method for generating multiple alignments of long genomic sequences at any evolutionary distance. Our systems are publicly available at http://lagan.stanford.edu.

4 Corresponding author.

E-MAIL serafim{at}cs.stanford.edu; FAX (650) 725-1449.

Article and publication are at http://www.genome.org/cgi/doi/10.1101/gr.926603. Article published online before print in March 2003.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us   Add to Digg Digg   Add to Reddit Reddit   Add to Technorati Technorati    What's this?


This article has been cited by other articles:


Home page
 Brief BioinformHome page
K. Katoh and H. Toh
Recent developments in the MAFFT multiple sequence alignment program
Brief Bioinform, July 1, 2008; 9(4): 286 - 298.
[Abstract] [Full Text] [PDF]

Home page
 J. Virol.Home page
L. M. Smith, A. R. McWhorter, L. L. Masters, G. R. Shellam, and A. J. Redwood
Laboratory Strains of Murine Cytomegalovirus Are Genetically Similar to but Phenotypically Distinct from Wild Strains of Virus
J. Virol., July 1, 2008; 82(13): 6689 - 6696.
[Abstract] [Full Text] [PDF]

Home page
 Mol Biol EvolHome page
C. E. Grover, Y. Yu, R. A. Wing, A. H. Paterson, and J. F. Wendel
A Phylogenetic Analysis of Indel Dynamics in the Cotton Genus
Mol. Biol. Evol., July 1, 2008; 25(7): 1415 - 1428.
[Abstract] [Full Text] [PDF]

Home page
 Mol Biol EvolHome page
S. Pantalacci, A. Chaumot, G. Benoit, A. Sadier, F. Delsuc, E. J. P. Douzery, and V. Laudet
Conserved Features and Evolutionary Shifts of the EDA Signaling Pathway Involved in Vertebrate Skin Appendage Development
Mol. Biol. Evol., May 1, 2008; 25(5): 912 - 928.
[Abstract] [Full Text] [PDF]

Home page
 GeneticsHome page
D. Bensasson, M. Zarowiecki, A. Burt, and V. Koufopanou
Rapid Evolution of Yeast Centromeres in the Absence of Drive
Genetics, April 1, 2008; 178(4): 2161 - 2167.
[Abstract] [Full Text] [PDF]

Home page
 Proc. Natl. Acad. Sci. USAHome page
I. J. Tsai, D. Bensasson, A. Burt, and V. Koufopanou
Population genomics of the wild yeast Saccharomyces paradoxus: Quantifying the life cycle
PNAS, March 25, 2008; 105(12): 4957 - 4962.
[Abstract] [Full Text] [PDF]

Home page
 Physiol. GenomicsHome page
R. B. White and M. R. Ziman
Genome-wide discovery of Pax7 target genes during development
Physiol Genomics, March 10, 2008; 33(1): 41 - 49.
[Abstract] [Full Text] [PDF]

Home page
 Genome Res.Home page
G. Lunter, A. Rocco, N. Mimouni, A. Heger, A. Caldeira, and J. Hein
Uncertainty in homology inferences: Assessing and improving genomic sequence alignment
Genome Res., February 1, 2008; 18(2): 298 - 309.
[Abstract] [Full Text] [PDF]

Home page
 BloodHome page
W. T. Nottingham, A. Jarratt, M. Burgess, C. L. Speck, J.-F. Cheng, S. Prabhakar, E. M. Rubin, P.-S. Li, J. Sloane-Stanley, J. Kong-a-San, et al.
Runx1-mediated hematopoietic stem-cell emergence is controlled by a Gata/Ets/SCL-regulated enhancer
Blood, December 15, 2007; 110(13): 4188 - 4197.
[Abstract] [Full Text] [PDF]

Home page
 Brief BioinformHome page
B. S. Srinivasan, N. H. Shah, J. A. Flannick, E. Abeliuk, A. F. Novak, and S. Batzoglou
Current progress in network research: toward reference networks for key model organisms
Brief Bioinform, September 1, 2007; 8(5): 318 - 332.
[Abstract] [Full Text] [PDF]

Home page
 Mol Biol EvolHome page
D. E. Neafsey and J. E. Galagan
Dual Modes of Natural Selection on Upstream Open Reading Frames
Mol. Biol. Evol., August 1, 2007; 24(8): 1744 - 1751.
[Abstract] [Full Text] [PDF]

Home page
 Mol Biol EvolHome page
G. A. Huttley, M. J. Wakefield, and S. Easteal
Rates of Genome Evolution and Branching Order from Whole Genome Analysis
Mol. Biol. Evol., August 1, 2007; 24(8): 1722 - 1730.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
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]

Home page
 Nucleic Acids ResHome page
D. Das, T. A. Clark, A. Schweitzer, M. Yamamoto, H. Marr, J. Arribere, S. Minovitsky, A. Poliakov, I. Dubchak, J. E. Blume, et al.
A correlation with exon expression approach to identify cis-regulatory elements for tissue-specific alternative splicing
Nucleic Acids Res., July 10, 2007; (2007) gkm485v1.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
A. Vishnoi, R. Roy, and A. Bhattacharya
Comparative analysis of bacterial genomes: identification of divergent regions in mycobacterial strains using an anchor-based approach
Nucleic Acids Res., June 28, 2007; 35(11): 3654 - 3667.
[Abstract] [Full Text] [PDF]

Home page
 Genome Res.Home page
E. H. Margulies, G. M. Cooper, G. Asimenos, D. J. Thomas, C. N. Dewey, A. Siepel, E. Birney, D. Keefe, A. S. Schwartz, M. Hou, et al.
Analyses of deep mammalian sequence alignments and constraint predictions for 1% of the human genome
Genome Res., June 1, 2007; 17(6): 760 - 774.
[Abstract] [Full Text] [PDF]

Home page
 Genome Res.Home page
D. Zheng, A. Frankish, R. Baertsch, P. Kapranov, A. Reymond, S. W. Choo, Y. Lu, F. Denoeud, S. E. Antonarakis, M. Snyder, et al.
Pseudogenes in the ENCODE regions: Consensus annotation, analysis of transcription, and evolution
Genome Res., June 1, 2007; 17(6): 839 - 851.
[Abstract] [Full Text] [PDF]

Home page
 Mol. Endocrinol.Home page
M. Ono, D. J. Chia, R. Merino-Martinez, A. Flores-Morales, T. G. Unterman, and P. Rotwein
Signal Transducer and Activator of Transcription (Stat) 5b-Mediated Inhibition of Insulin-Like Growth Factor Binding Protein-1 Gene Transcription: A Mechanism for Repression of Gene Expression by Growth Hormone
Mol. Endocrinol., June 1, 2007; 21(6): 1443 - 1457.
[Abstract] [Full Text] [PDF]

Home page
 Genome Res.Home page
O. Emanuelsson, U. Nagalakshmi, D. Zheng, J. S. Rozowsky, A. E. Urban, J. Du, Z. Lian, V. Stolc, S. Weissman, M. Snyder, et al.
Assessing the performance of different high-density tiling microarray strategies for mapping transcribed regions of the human genome
Genome Res., June 1, 2007; 17(6): 886 - 897.
[Abstract] [Full Text] [PDF]

Home page
 Plant CellHome page
M. Freeling, L. Rapaka, E. Lyons, B. Pedersen, and B. C. Thomas
G-Boxes, Bigfoot Genes, and Environmental Response: Characterization of Intragenomic Conserved Noncoding Sequences in Arabidopsis
PLANT CELL, May 1, 2007; 19(5): 1441 - 1457.
[Abstract] [Full Text] [PDF]

Home page
 Mol Biol EvolHome page
S. W. Roy, D. Penny, and D. E. Neafsey
Evolutionary Conservation of UTR Intron Boundaries in Cryptococcus
Mol. Biol. Evol., May 1, 2007; 24(5): 1140 - 1148.
[Abstract] [Full Text] [PDF]

Home page
 Proc. Natl. Acad. Sci. USAHome page
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]

Home page
 BloodHome page
W. Y. I. Chan, G. A. Follows, G. Lacaud, J. E. Pimanda, J.-R. Landry, S. Kinston, K. Knezevic, S. Piltz, I. J. Donaldson, L. Gambardella, et al.
The paralogous hematopoietic regulators Lyl1 and Scl are coregulated by Ets and GATA factors, but Lyl1 cannot rescue the early Scl-/- phenotype
Blood, March 1, 2007; 109(5): 1908 - 1916.
[Abstract] [Full Text] [PDF]

Home page
 Genome Res.Home page
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]

Home page
 BioinformaticsHome page
J. Kim and S. Sinha
Indelign: a probabilistic framework for annotation of insertions and deletions in a multiple alignment
Bioinformatics, February 1, 2007; 23(3): 289 - 297.
[Abstract] [Full Text] [PDF]

Home page
 Mol Biol EvolHome page
M. M. Hoffman and E. Birney
Estimating the Neutral Rate of Nucleotide Substitution Using Introns
Mol. Biol. Evol., February 1, 2007; 24(2): 522 - 531.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
X. Huang and D. L. Brutlag
Dynamic use of multiple parameter sets in sequence alignment
Nucleic Acids Res., January 28, 2007; 35(2): 678 - 686.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
D. J. Thomas, K. R. Rosenbloom, H. Clawson, A. S. Hinrichs, H. Trumbower, B. J. Raney, D. Karolchik, G. P. Barber, R. A. Harte, J. Hillman-Jackson, et al.
The ENCODE Project at UC Santa Cruz
Nucleic Acids Res., January 12, 2007; 35(suppl_1): D663 - D667.
[Abstract] [Full Text] [PDF]

Home page
 Mol. Endocrinol.Home page
O. M. Vidal, R. Merino, E. Rico-Bautista, L. Fernandez-Perez, D. J. Chia, J. Woelfle, M. Ono, B. Lenhard, G. Norstedt, P. Rotwein, et al.
In Vivo Transcript Profiling and Phylogenetic Analysis Identifies Suppressor of Cytokine Signaling 2 as a Direct Signal Transducer and Activator of Transcription 5b Target in Liver
Mol. Endocrinol., January 1, 2007; 21(1): 293 - 311.
[Abstract] [Full Text] [PDF]

Home page
 Genome Res.Home page
L. Elnitski, V. X. Jin, P. J. Farnham, and S. J.M. Jones
Locating mammalian transcription factor binding sites: A survey of computational and experimental techniques
Genome Res., December 1, 2006; 16(12): 1455 - 1464.
[Abstract] [Full Text] [PDF]

Home page
 J. Bacteriol.Home page
L. Shen, X. Feng, Y. Yuan, X. Luo, T. P. Hatch, K. T. Hughes, J. S. Liu, and Y.-x. Zhang
Selective Promoter Recognition by Chlamydial {sigma}28 Holoenzyme
J. Bacteriol., November 1, 2006; 188(21): 7364 - 7377.
[Abstract] [Full Text] [PDF]

Home page
 J. Virol.Home page
E. R. Tulman, G. Delhon, C. L. Afonso, Z. Lu, L. Zsak, N. T. Sandybaev, U. Z. Kerembekova, V. L. Zaitsev, G. F. Kutish, and D. L. Rock
Genome of horsepox virus.
J. Virol., September 1, 2006; 80(18): 9244 - 9258.
[Abstract] [Full Text] [PDF]

Home page
 Genome Res.Home page
J. Flannick, A. Novak, B. S. Srinivasan, H. H. McAdams, and S. Batzoglou
Graemlin: General and robust alignment of multiple large interaction networks
Genome Res., September 1, 2006; 16(9): 1169 - 1181.
[Abstract] [Full Text] [PDF]

Home page
 Proc. Natl. Acad. Sci. USAHome page
W. Salerno, P. Havlak, and J. Miller
Scale-invariant structure of strongly conserved sequence in genomic intersections and alignments
PNAS, August 29, 2006; 103(35): 13121 - 13125.
[Abstract] [Full Text] [PDF]

Home page
 Genes Dev.Home page
T. Pramila, W. Wu, S. Miles, W. S. Noble, and L. L. Breeden
The Forkhead transcription factor Hcm1 regulates chromosome segregation genes and fills the S-phase gap in the transcriptional circuitry of the cell cycle.
Genes & Dev., August 15, 2006; 20(16): 2266 - 2278.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
K. Szafranski, N. Jahn, and M. Platzer
tuple_plot: Fast pairwise nucleotide sequence comparison with noise suppression
Bioinformatics, August 1, 2006; 22(15): 1917 - 1918.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
D. GuhaThakurta
Computational identification of transcriptional regulatory elements in DNA sequence
Nucleic Acids Res., July 19, 2006; 34(12): 3585 - 3598.
[Abstract] [Full Text] [PDF]

Home page
 Genome Res.Home page
S. Prabhakar, F. Poulin, M. Shoukry, V. Afzal, E. M. Rubin, O. Couronne, and L. A. Pennacchio
Close sequence comparisons are sufficient to identify human cis-regulatory elements
Genome Res., July 1, 2006; 16(7): 855 - 863.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
S. Sinha, Y. Liang, and E. Siggia
Stubb: a program for discovery and analysis of cis-regulatory modules.
Nucleic Acids Res., July 1, 2006; 34(Web Server issue): W555 - W559.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
A. Lardenois, F. Chalmel, L. Bianchetti, J.-A. Sahel, T. Leveillard, and O. Poch
PromAn: an integrated knowledge-based web server dedicated to promoter analysis.
Nucleic Acids Res., July 1, 2006; 34(Web Server issue): W578 - W583.
[Abstract] [Full Text] [PDF]

Home page
 BloodHome page
J. E. Pimanda, W.Y. I. Chan, I. J. Donaldson, M. Bowen, A. R. Green, and B. Gottgens
Endoglin expression in the endothelium is regulated by Fli-1, Erg, and Elf-1 acting on the promoter and a -8-kb enhancer
Blood, June 15, 2006; 107(12): 4737 - 4745.
[Abstract] [Full Text] [PDF]

Home page
 Proc. Natl. Acad. Sci. USAHome page
A. P. Lee, E. G. L. Koh, A. Tay, S. Brenner, and B. Venkatesh
Highly conserved syntenic blocks at the vertebrate Hox loci and conserved regulatory elements within and outside Hox gene clusters
PNAS, May 2, 2006; 103(18): 6994 - 6999.
[Abstract] [Full Text] [PDF]

Home page
 Mol. Cell. Biol.Home page
D. Antonini, B. Rossi, R. Han, A. Minichiello, T. Di Palma, M. Corrado, S. Banfi, M. Zannini, J. L. Brissette, and C. Missero
An Autoregulatory Loop Directs the Tissue-Specific Expression of p63 through a Long-Range Evolutionarily Conserved Enhancer
Mol. Cell. Biol., April 15, 2006; 26(8): 3308 - 3318.
[Abstract] [Full Text] [PDF]

Home page
 Hum Mol GenetHome page
C. N. Dewey and L. Pachter
Evolution at the nucleotide level: the problem of multiple whole-genome alignment.
Hum. Mol. Genet., April 15, 2006; 15(suppl_1): R51 - R56.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
T. Sauer, E. Shelest, and E. Wingender
Evaluating phylogenetic footprinting for human-rodent comparisons
Bioinformatics, February 15, 2006; 22(4): 430 - 437.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
X. Huang, S.-P. Yang, A. T. Chinwalla, L. W. Hillier, P. Minx, E. R. Mardis, and R. K. Wilson
Application of a superword array in genome assembly
Nucleic Acids Res., January 5, 2006; 34(1): 201 - 205.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
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]

Home page
 Genome Res.Home page
S. J. Cooper, N. D. Trinklein, E. D. Anton, L. Nguyen, and R. M. Myers
Comprehensive analysis of transcriptional promoter structure and function in 1% of the human genome
Genome Res., January 1, 2006; 16(1): 1 - 10.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
E. Blanco, D. Farre, M. M. Alba, X. Messeguer, and R. Guigo
ABS: a database of Annotated regulatory Binding Sites from orthologous promoters
Nucleic Acids Res., January 1, 2006; 34(suppl_1): D63 - D67.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
W. Huang, D. M. Umbach, and L. Li
Accurate anchoring alignment of divergent sequences
Bioinformatics, January 1, 2006; 22(1): 29 - 34.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
E. Birney, D. Andrews, M. Caccamo, Y. Chen, L. Clarke, G. Coates, T. Cox, F. Cunningham, V. Curwen, T. Cutts, et al.
Ensembl 2006
Nucleic Acids Res., January 1, 2006; 34(suppl_1): D556 - D561.
[Abstract] [Full Text] [PDF]

Home page
 J. Med. Genet.Home page
S Sammalisto, T Hiekkalinna, E Suviolahti, K Sood, A Metzidis, P Pajukanta, H E Lilja, A Soro-Paavonen, M-R Taskinen, T Tuomi, et al.
A male-specific quantitative trait locus on 1p21 controlling human stature
J. Med. Genet., December 1, 2005; 42(12): 932 - 939.
[Abstract] [Full Text] [PDF]

Home page
 J. Gen. Virol.Home page
G. Li, N. Chen, R. L. Roper, Z. Feng, A. Hunter, M. Danila, E. J. Lefkowitz, R. M. L. Buller, and C. Upton
Complete coding sequences of the rabbitpox virus genome
J. Gen. Virol., November 1, 2005; 86(11): 2969 - 2977.
[Abstract] [Full Text] [PDF]

Home page
 Hum Mol GenetHome page
N. Ahituv, S. Prabhakar, F. Poulin, E. M. Rubin, and O. Couronne
Mapping cis-regulatory domains in the human genome using multi-species conservation of synteny
Hum. Mol. Genet., October 15, 2005; 14(20): 3057 - 3063.
[Abstract] [Full Text] [PDF]

Home page
 BloodHome page
J.-R. Landry, S. Kinston, K. Knezevic, I. J. Donaldson, A. R. Green, and B. Gottgens
Fli1, Elf1, and Ets1 regulate the proximal promoter of the LMO2 gene in endothelial cells
Blood, October 15, 2005; 106(8): 2680 - 2687.
[Abstract] [Full Text] [PDF]

Home page
 Genome Res.Home page
D. S. Johnson, Q. Zhou, K. Yagi, N. Satoh, W. Wong, and A. Sidow
De novo discovery of a tissue-specific gene regulatory module in a chordate
Genome Res., October 1, 2005; 15(10): 1315 - 1324.
[Abstract] [Full Text] [PDF]