LAGAN and Multi-LAGAN: Efficient tools for large-scale multiple alignment of genomic DNA
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The Lagan algorithm is based on dynamic programming and uses anchoring to subdivide the alignment into small anchors.
“The Lagan algorithm is based on dynamic programming as it uses anchoring to subdivide the alignment into small anchors [28].”
From Whole-Genome Alignment: Methods, Challenges, and Future Directions (2024) · cites this paper as [28]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Basic local alignment search tool
Altschul, S. F., Gish, W., Miller, W., Myers, E. W., & Lipman, D. J. (1990) · Journal of Molecular Biology · doi:10.1006/jmbi.1990.9999 · Cited by 98,669 · see citing works
Gapped BLAST and PSI-BLAST: a new generation of protein database search programs
Altschul, S. (1997) · Nucleic Acids Research · doi:10.1093/nar/25.17.3389 · Cited by 73,302 · see citing works
Needleman, S. B., & Wunsch, C. D. (1970) · Journal of Molecular Biology · doi:10.1016/0022-2836(70)90057-4 · Cited by 11,288 · see citing works
Flagged first, then by citations
Research works printed but not linked: 4
- Brudno, M. and Morgenstern, B. 2002. Fast and sensitive alignment of large genomic sequences. Proceeding of the IEEE Computer Society Bioinformatics Conference (CSB).
- Gusfield, D. 1999. Algorithms on strings, trees, and sequences: Computer science and computational biology, pp. 351-353. Cambridge University Press, Cambridge, UK.
- Henikoff, S. and Henikoff, J.G. 1992. Amino acid substitution matrices from protein blocks. Proc. Natl. Acad. Sci. 89: 10,915-10,919.
- Simon A., Stone, E.A., and Sidow, A. 2002. Inference of functional regions in proteins by quantification of evolutionary constraints. Proc. Natl. Acad. Sci. 99: 2912-2917.
Cited by
Sorted by citations
MUSCLE: multiple sequence alignment with high accuracy and high throughput
Edgar, R. C. (2004) · Nucleic Acids Research · doi:10.1093/nar/gkh340 · Cited by 44,662 · see citing works
The ENCODE Project Consortium (2007) · Nature · doi:10.1038/nature05874 · Cited by 5,223 · see citing works
Evolutionarily conserved elements in vertebrate, insect, worm, and yeast genomes
Siepel, A., Bejerano, G., Pedersen, J. S., Hinrichs, A. S., Hou, M., Rosenbloom, K., Clawson, H., Spieth, J., Hillier, L. W., Richards, S., et al. (2005) · Genome Research · doi:10.1101/gr.3715005 · Cited by 4,408 · see citing works
Distribution and intensity of constraint in mammalian genomic sequence
Cooper, G. M., Stone, E. A., Asimenos, G., Green, E. D., Batzoglou, S., & Sidow, A. (2005) · Genome Research · doi:10.1101/gr.3577405 · Cited by 1,359 · see citing works
Self-citationThe DNA sequence of the human X chromosome
Ross, M. T., Grafham, D. V., Coffey, A. J., Scherer, S., McLay, K., Muzny, D., Platzer, M., Howell, G. R., Burrows, C., Bird, C. P., et al. (2005) · Nature · doi:10.1038/nature03440 · Cited by 1,129 · see citing works
Highly Conserved Non-Coding Sequences Are Associated with Vertebrate Development
Woolfe, A., Goodson, M., Goode, D. K., Snell, P., McEwen, G. K., Vavouri, T., Smith, S. F., North, P., Callaway, H., Kelly, K., et al. (2004) · PLoS Biology · doi:10.1371/journal.pbio.0030007 · Cited by 970 · see citing works
Genome analysis of the platypus reveals unique signatures of evolution
paper, A. L. O. A. A. T. A. A. A. T. E. O. T. (2008) · Nature · doi:10.1038/nature06936 · Cited by 719 · see citing works
Hare, E. E., Peterson, B. K., Iyer, V. N., Meier, R., & Eisen, M. B. (2008) · PLoS Genetics · doi:10.1371/journal.pgen.1000106 · Cited by 302 · see citing works
Conservation of core gene expression in vertebrate tissues
Chan, E. T., Quon, G. T., Chua, G., Babak, T., Trochesset, M., Zirngibl, R. A., Aubin, J., Ratcliffe, M. J., Wilde, A., Brudno, M., et al. (2009) · Journal of Biology · doi:10.1186/jbiol130 · Cited by 190 · see citing works
Self-citationNair, S., Doh, S. T., Chan, J. Y., Kong, A.-N., & Cai, L. (2008) · British Journal of Cancer · doi:10.1038/sj.bjc.6604703 · Cited by 167 · see citing works
Variability of CYP3A7 expression in human fetal liver
Leeder, J. S., Gaedigk, R., Marcucci, K. A., Gaedigk, A., Vyhlidal, C. A., Schindel, B. P., & Pearce, R. E. (2005) · The Journal of Pharmacology and Experimental Therapeutics · doi:10.1124/jpet.105.086504 · Cited by 136 · see citing works
Genome-wide prediction of transcription factor binding sites using an integrated model
Won, K.-J., Ren, B., & Wang, W. (2010) · Genome Biology · doi:10.1186/gb-2010-11-1-r7 · Cited by 116 · see citing works
Neuroadaptations in Human Chronic Alcoholics: Dysregulation of the NF-κB System
Ökvist, A., Johansson, S., Kuzmin, A., Bazov, I., Merino-Martinez, R., Ponomarev, I., Mayfield, R. D., Harris, R. A., Sheedy, D., Garrick, T., et al. (2007) · PLoS ONE · doi:10.1371/journal.pone.0000930 · Cited by 84 · see citing works
Cole, S. (2007) · doi:10.1186/gb-2007-8-1-r1 · Cited by 4 · see citing works
Haplotype Block Structure Is Conserved across Mammals
Guryev, V., Smits, B. M. G., de Belt, J. V., Verheul, M., Hubner, N., & Cuppen, E. (2006) · PLoS Genetics · doi:10.1371/journal.pgen.0020121 · Cited by 69 · see citing works
Application of a superword array in genome assembly
Huang, X. (2006) · Nucleic Acids Research · doi:10.1093/nar/gkj419 · Cited by 30 · see citing works
CEGA—a catalog of conserved elements from genomic alignments
Dousse, A., Junier, T., & Zdobnov, E. M. (2016) · Nucleic Acids Research · doi:10.1093/nar/gkv1163 · Cited by 20 · see citing works
Whole-Genome Alignment: Methods, Challenges, and Future Directions
Saada, B., Zhang, T., Siga, E., Zhang, J., & Magalhães Muniz, M. M. (2024) · Applied Sciences · doi:10.3390/app14114837 · Cited by 15 · see citing works
- Authors
- Brudno, M., Do, C. B., Cooper, G. M., Kim, M. F., Davydov, E., Program, N. C. S., Green, E. D., Sidow, A., & Batzoglou, S.
- Affiliations
- National Institutes of Health (US)
- Venue
- Genome Research
- Publisher
- Cold Spring Harbor Laboratory
- Published
- 2003-03-12
- Volume
- 13
- Issue
- 4
- Pages
- 721-731
- ISSN
- 1088-9051 (ISSN-L)
- 1549-5469
- PMC
- PMC430158
- OpenAlex
- W2155237411
- Cited by
- 1,115
- References
- 3
- Citations by year
- 2026: 19 · 2025: 26 · 2024: 38 · 2023: 38 · 2022: 27 · 2021: 20 · 2020: 34 · 2019: 26 · 2018: 26 · 2017: 26 · 2016: 20 · 2015: 39 · 2014: 45 · 2013: 43 · 2012: 29
- Type
- posted content
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Genome Research (publishedVersion)
- PubMed Central (publishedVersion)
- PubMed (publishedVersion)
- Funders
- National Science Foundation
- National Human Genome Research Institute
- Topics
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Fractal and DNA sequence analysis
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Genetics › Genome Rearrangement Algorithms
- Keywords
- global sequence alignment, multiple sequence alignment, homologous sequences, vertebrate genomes, orthologous regions, alignment accuracy
- MeSH terms
- Animals, Base Sequence, Cattle, Chickens, Pan troglodytes, Dogs, Humans, Molecular Sequence Data, Papio, Sequence Homology, Nucleic Acid, Software, Swine, Zebrafish, Genome, Human, Sequence Alignment, Genome, Sequence Analysis, DNA, Takifugu, Mice, Rats
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
