title: LAGAN and Multi-LAGAN: efficient tools for large-scale multiple alignment of genomic DNA.
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 approximately 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.
authors.affiliation: Department of Computer Science, Stanford University, Stanford, California 94305-9010, USA.
authors.forename: Michael
authors.initials: M
authors.lastname: Brudno
authors.forename: Chuong B
authors.initials: CB
authors.lastname: Do
authors.forename: Gregory M
authors.initials: GM
authors.lastname: Cooper
authors.forename: Michael F
authors.initials: MF
authors.lastname: Kim
authors.forename: Eugene
authors.initials: E
authors.lastname: Davydov
authors.forename: Eric D
authors.initials: ED
authors.lastname: Green
authors.forename: Arend
authors.initials: A
authors.lastname: Sidow
authors.forename: Serafim
authors.initials: S
authors.lastname: Batzoglou
mesh_terms: D000818:Animals; D001483:Base Sequence; D002417:Cattle; D002645:Chickens; D004285:Dogs; D016678:Genome; D015894:Genome, Human; D006801:Humans; D051379:Mice; D008969:Molecular Sequence Data; D002679:Pan troglodytes; D010215:Papio; D051381:Rats; D016415:Sequence Alignment / Q000379:methods* / Q000706:statistics & numerical data; D017422:Sequence Analysis, DNA / Q000379:methods*; D012689:Sequence Homology, Nucleic Acid; D012984:Software / Q000706:statistics & numerical data; D013552:Swine; D023741:Takifugu; D015027:Zebrafish