DOI: 10.1101/gr.926603. LAGAN and Multi-LAGAN: Efficient Tools for Large-Scale Multiple Alignment of Genomic DNA

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

10.1101/gr.926603

Crossref journal-article

Cold Spring Harbor Laboratory

Genome Research (246)

Abstract

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 athttp://lagan.stanford.edu.

Bibliography

Brudno, M., Do, C. B., Cooper, G. M., Kim, M. F., Davydov, E., Program, N. C. S., Green, E. D., Sidow, A., & Batzoglou, S. (2003). LAGAN and Multi-LAGAN: Efficient Tools for Large-Scale Multiple Alignment of Genomic DNA. Genome Research, 13(4), 721â731.

Authors 9

Michael Brudno (first)
Chuong B. Do (additional)
Gregory M. Cooper (additional)
Michael F. Kim (additional)
Eugene Davydov (additional)
NISC Comparative Sequencing Program (additional)
Eric D. Green (additional)
Arend Sidow (additional)
Serafim Batzoglou (additional)

References 37 Referenced 880

10.1006/jmbi.1990.9999
10.1093/nar/25.17.3389
10.1089/cmb.1997.4.369 / J. Comp. Biol. / Re-Aligner: A program for refining DNA sequence multialignments. by Anson (1997)
10.1016/0022-2836(87)90316-0
10.1101/gr.10.7.950
10.1016/S0304-3975(99)00324-2
10.1101/gr.789803
Brudno M. Morgenstern B. (2002) Fast and sensitive alignment of large genomic sequences. Proceeding of the IEEE Computer Society Bioinformatics Conference (CSB) .. (10.1186/1471-2105-4-66)
10.1093/nar/27.11.2369
10.1093/nar/30.11.2478
10.1101/gr.142200
10.1145/146637.146656
10.1006/jmbi.1996.0679
10.1101/gr.45502
Gusfield D. (1999) Algorithms on strings, trees, and sequences: Computer science and computational biology (Cambridge University Press, Cambridge, UK), pp 351â353.
10.3109/10425179309015629 / DNA Seq. / Positive and negative regulatory elements of the rabbit Îµ-globin gene revealed by an improved multiple alignment program and functional analysis. by Hardison (1993)
10.1006/geno.1994.1275
10.1073/pnas.89.22.10915
10.1093/bioinformatics/18.suppl_1.S312 / Bioinformatics / Efficient multiple genome alignment. by HÃ¶hl (2002)
10.1093/bioinformatics/17.9.803
10.1101/gr.229202. Article published online before March 2002
10.1101/gr.10.8.1115
10.1093/bioinformatics/16.11.1046
10.1093/bioinformatics/17.5.391
10.1093/bioinformatics/15.3.211
10.1093/bioinformatics/14.3.290
10.1016/0022-2836(70)90057-4
10.1101/gr.194201
10.1006/jmbi.2000.4042
10.1093/bioinformatics/15.11.909
10.1101/gr.10.4.577
10.1073/pnas.042692299
10.1016/0022-2836(81)90087-5
10.1006/jtbi.1996.0213
10.1007/BF02143508
10.1093/nar/22.22.4673
10.1089/cmb.1994.1.337

Dates

Type	When
Created	22 years, 5 months ago (April 1, 2003, 10:44 p.m.)
Deposited	8 months, 3 weeks ago (Dec. 11, 2024, 8:40 p.m.)
Indexed	5 days, 1 hour ago (Aug. 30, 2025, 12:22 p.m.)
Issued	22 years, 5 months ago (March 12, 2003)
Published	22 years, 5 months ago (March 12, 2003)
Published Online	22 years, 5 months ago (March 12, 2003)
Published Print	22 years, 5 months ago (April 1, 2003)

Funders 0

None

BibTeX

@article{Brudno_2003, title={LAGAN and Multi-LAGAN: Efficient Tools for Large-Scale Multiple Alignment of Genomic DNA}, volume={13}, ISSN={1549-5469}, url={http://dx.doi.org/10.1101/gr.926603}, DOI={10.1101/gr.926603}, number={4}, journal={Genome Research}, publisher={Cold Spring Harbor Laboratory}, author={Brudno, Michael and Do, Chuong B. and Cooper, Gregory M. and Kim, Michael F. and Davydov, Eugene and Program, NISC Comparative Sequencing and Green, Eric D. and Sidow, Arend and Batzoglou, Serafim}, year={2003}, month=mar, pages={721–731} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        8,
        30
      ]
    ],
    "date-time": "2025-08-30T16:22:18Z",
    "timestamp": 1756570938357,
    "version": "3.30.2"
  },
  "reference-count": 37,
  "publisher": "Cold Spring Harbor Laboratory",
  "issue": "4",
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        2003,
        4,
        1
      ]
    ]
  },
  "abstract": "<jats:p>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 \u223c1.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<jats:ext-link xmlns:xlink=\"http://www.w3.org/1999/xlink\" ext-link-type=\"uri\" xlink:href=\"http://lagan.stanford.edu\" xlink:type=\"simple\">http://lagan.stanford.edu</jats:ext-link>.</jats:p>",
  "DOI": "10.1101/gr.926603",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2003,
        4,
        2
      ]
    ],
    "date-time": "2003-04-02T03:44:29Z",
    "timestamp": 1049255069000
  },
  "page": "721-731",
  "source": "Crossref",
  "is-referenced-by-count": 880,
  "title": "LAGAN and Multi-LAGAN: Efficient Tools for Large-Scale Multiple Alignment of Genomic DNA",
  "prefix": "10.1101",
  "volume": "13",
  "author": [
    {
      "given": "Michael",
      "family": "Brudno",
      "sequence": "first",
      "affiliation": []
    },
    {
      "given": "Chuong B.",
      "family": "Do",
      "sequence": "additional",
      "affiliation": []
    },
    {
      "given": "Gregory M.",
      "family": "Cooper",
      "sequence": "additional",
      "affiliation": []
    },
    {
      "given": "Michael F.",
      "family": "Kim",
      "sequence": "additional",
      "affiliation": []
    },
    {
      "given": "Eugene",
      "family": "Davydov",
      "sequence": "additional",
      "affiliation": []
    },
    {
      "given": "NISC Comparative Sequencing",
      "family": "Program",
      "sequence": "additional",
      "affiliation": []
    },
    {
      "given": "Eric D.",
      "family": "Green",
      "sequence": "additional",
      "affiliation": []
    },
    {
      "given": "Arend",
      "family": "Sidow",
      "sequence": "additional",
      "affiliation": []
    },
    {
      "given": "Serafim",
      "family": "Batzoglou",
      "sequence": "additional",
      "affiliation": []
    }
  ],
  "member": "246",
  "published-online": {
    "date-parts": [
      [
        2003,
        3,
        12
      ]
    ]
  },
  "reference": [
    {
      "key": "2021111810480624000_13.4.721.1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1006/jmbi.1990.9999"
    },
    {
      "key": "2021111810480624000_13.4.721.2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1093/nar/25.17.3389"
    },
    {
      "key": "2021111810480624000_13.4.721.3",
      "doi-asserted-by": "crossref",
      "first-page": "369",
      "DOI": "10.1089/cmb.1997.4.369",
      "article-title": "Re-Aligner: A program for refining DNA sequence multialignments.",
      "volume": "4",
      "author": "Anson",
      "year": "1997",
      "journal-title": "J. Comp. Biol."
    },
    {
      "key": "2021111810480624000_13.4.721.4",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0022-2836(87)90316-0"
    },
    {
      "key": "2021111810480624000_13.4.721.5",
      "doi-asserted-by": "publisher",
      "DOI": "10.1101/gr.10.7.950"
    },
    {
      "key": "2021111810480624000_13.4.721.6",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/S0304-3975(99)00324-2"
    },
    {
      "key": "2021111810480624000_13.4.721.7",
      "doi-asserted-by": "publisher",
      "DOI": "10.1101/gr.789803"
    },
    {
      "key": "2021111810480624000_13.4.721.8",
      "doi-asserted-by": "crossref",
      "unstructured": "Brudno M. Morgenstern B. (2002) Fast and sensitive alignment of large genomic sequences. Proceeding of the IEEE Computer Society Bioinformatics Conference (CSB) ..",
      "DOI": "10.1186/1471-2105-4-66"
    },
    {
      "key": "2021111810480624000_13.4.721.9",
      "doi-asserted-by": "publisher",
      "DOI": "10.1093/nar/27.11.2369"
    },
    {
      "key": "2021111810480624000_13.4.721.10",
      "doi-asserted-by": "publisher",
      "DOI": "10.1093/nar/30.11.2478"
    },
    {
      "key": "2021111810480624000_13.4.721.11",
      "doi-asserted-by": "publisher",
      "DOI": "10.1101/gr.142200"
    },
    {
      "key": "2021111810480624000_13.4.721.12",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/146637.146656"
    },
    {
      "key": "2021111810480624000_13.4.721.13",
      "doi-asserted-by": "publisher",
      "DOI": "10.1006/jmbi.1996.0679"
    },
    {
      "key": "2021111810480624000_13.4.721.14",
      "doi-asserted-by": "publisher",
      "DOI": "10.1101/gr.45502"
    },
    {
      "key": "2021111810480624000_13.4.721.15",
      "unstructured": "Gusfield D. (1999) Algorithms on strings, trees, and sequences: Computer science and computational biology (Cambridge University Press, Cambridge, UK), pp 351\u00e2\u0080\u0093353."
    },
    {
      "key": "2021111810480624000_13.4.721.16",
      "doi-asserted-by": "crossref",
      "first-page": "163",
      "DOI": "10.3109/10425179309015629",
      "article-title": "Positive and negative regulatory elements of the rabbit \u00ce\u00b5-globin gene revealed by an improved multiple alignment program and functional analysis.",
      "volume": "4",
      "author": "Hardison",
      "year": "1993",
      "journal-title": "DNA Seq."
    },
    {
      "key": "2021111810480624000_13.4.721.17",
      "doi-asserted-by": "publisher",
      "DOI": "10.1006/geno.1994.1275"
    },
    {
      "key": "2021111810480624000_13.4.721.18",
      "doi-asserted-by": "publisher",
      "DOI": "10.1073/pnas.89.22.10915"
    },
    {
      "key": "2021111810480624000_13.4.721.19",
      "doi-asserted-by": "crossref",
      "first-page": "312",
      "DOI": "10.1093/bioinformatics/18.suppl_1.S312",
      "article-title": "Efficient multiple genome alignment.",
      "volume": "18",
      "author": "H\u00c3\u00b6hl",
      "year": "2002",
      "journal-title": "Bioinformatics"
    },
    {
      "key": "2021111810480624000_13.4.721.20",
      "doi-asserted-by": "publisher",
      "DOI": "10.1093/bioinformatics/17.9.803"
    },
    {
      "key": "2021111810480624000_13.4.721.21",
      "doi-asserted-by": "publisher",
      "DOI": "10.1101/gr.229202. Article published online before March 2002"
    },
    {
      "key": "2021111810480624000_13.4.721.22",
      "doi-asserted-by": "publisher",
      "DOI": "10.1101/gr.10.8.1115"
    },
    {
      "key": "2021111810480624000_13.4.721.23",
      "doi-asserted-by": "publisher",
      "DOI": "10.1093/bioinformatics/16.11.1046"
    },
    {
      "key": "2021111810480624000_13.4.721.24",
      "doi-asserted-by": "publisher",
      "DOI": "10.1093/bioinformatics/17.5.391"
    },
    {
      "key": "2021111810480624000_13.4.721.25",
      "doi-asserted-by": "publisher",
      "DOI": "10.1093/bioinformatics/15.3.211"
    },
    {
      "key": "2021111810480624000_13.4.721.26",
      "doi-asserted-by": "publisher",
      "DOI": "10.1093/bioinformatics/14.3.290"
    },
    {
      "key": "2021111810480624000_13.4.721.27",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0022-2836(70)90057-4"
    },
    {
      "key": "2021111810480624000_13.4.721.28",
      "doi-asserted-by": "publisher",
      "DOI": "10.1101/gr.194201"
    },
    {
      "key": "2021111810480624000_13.4.721.29",
      "doi-asserted-by": "publisher",
      "DOI": "10.1006/jmbi.2000.4042"
    },
    {
      "key": "2021111810480624000_13.4.721.30",
      "doi-asserted-by": "publisher",
      "DOI": "10.1093/bioinformatics/15.11.909"
    },
    {
      "key": "2021111810480624000_13.4.721.31",
      "doi-asserted-by": "publisher",
      "DOI": "10.1101/gr.10.4.577"
    },
    {
      "key": "2021111810480624000_13.4.721.32",
      "doi-asserted-by": "publisher",
      "DOI": "10.1073/pnas.042692299"
    },
    {
      "key": "2021111810480624000_13.4.721.33",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0022-2836(81)90087-5"
    },
    {
      "key": "2021111810480624000_13.4.721.34",
      "doi-asserted-by": "publisher",
      "DOI": "10.1006/jtbi.1996.0213"
    },
    {
      "key": "2021111810480624000_13.4.721.35",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF02143508"
    },
    {
      "key": "2021111810480624000_13.4.721.36",
      "doi-asserted-by": "publisher",
      "DOI": "10.1093/nar/22.22.4673"
    },
    {
      "key": "2021111810480624000_13.4.721.37",
      "doi-asserted-by": "publisher",
      "DOI": "10.1089/cmb.1994.1.337"
    }
  ],
  "container-title": "Genome Research",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://syndication.highwire.org/content/doi/10.1101/gr.926603",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2024,
        12,
        12
      ]
    ],
    "date-time": "2024-12-12T01:40:51Z",
    "timestamp": 1733967651000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "http://genome.cshlp.org/lookup/doi/10.1101/gr.926603"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        2003,
        3,
        12
      ]
    ]
  },
  "references-count": 37,
  "journal-issue": {
    "issue": "4",
    "published-print": {
      "date-parts": [
        [
          2003,
          4,
          1
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1101/gr.926603"
  ],
  "URL": "http://dx.doi.org/10.1101/gr.926603",
  "relation": {},
  "ISSN": [
    "1088-9051",
    "1549-5469"
  ],
  "subject": [],
  "container-title-short": "Genome Res.",
  "published": {
    "date-parts": [
      [
        2003,
        3,
        12
      ]
    ]
  }
}