Nucleic Acids Research, Vol 27, Issue 11 2369-2376, Copyright © 1999 by Oxford University Press
AL Delcher, S Kasif, RD Fleischmann, J Peterson, O White and SL Salzberg
A new system for aligning whole genome sequences is described. Using an
efficient data structure called a suffix tree, the system is able to
rapidly align sequences containing millions of nucleotides. Its use is
demonstrated on two strains of Mycoplasma tuberculosis, on two less similar
species of Mycoplasma bacteria and on two syntenic sequences from human
chromosome 12 and mouse chromosome 6. In each case it found an alignment of
the input sequences, using between 30 s and 2 min of computation time. From
the system output, information on single nucleotide changes, translocations
and homologous genes can easily be extracted. Use of the algorithm should
facilitate analysis of syntenic chromosomal regions, strain-to-strain
comparisons, evolutionary comparisons and genomic duplications.
ARTICLES
Alignment of whole genomes
Department of Computer Science, Loyola College in Maryland, Baltimore, MD 21210, USA.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  G. S. A. Myers, S. A. Mathews, M. Eppinger, C. Mitchell, K. K. O'Brien, O. R. White, F. Benahmed, R. C. Brunham, T. D. Read, J. Ravel, et al. Evidence that Human Chlamydia pneumoniae Was Zoonotically Acquired J. Bacteriol., December 1, 2009; 191(23): 7225 - 7233. [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]
|
|
|
|
 |
|
 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]
|
|
|
|
|
|
T. Rausch, A.-K. Emde, D. Weese, A. Doring, C. Notredame, and K. Reinert Segment-based multiple sequence alignment Bioinformatics, August 15, 2008; 24(16): i187 - i192. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
N. R. Thomson, M. T.G. Holden, C. Carder, N. Lennard, S. J. Lockey, P. Marsh, P. Skipp, C. D. O'Connor, I. Goodhead, H. Norbertzcak, et al. Chlamydia trachomatis: Genome sequence analysis of lymphogranuloma venereum isolates Genome Res., January 1, 2008; 18(1): 161 - 171. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. V. Zimin, D. R. Smith, G. Sutton, and J. A. Yorke Assembly reconciliation Bioinformatics, January 1, 2008; 24(1): 42 - 45. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 G. A. Pandya, M. H. Holmes, S. Sunkara, A. Sparks, Y. Bai, K. Verratti, K. Saeed, P. Venepally, B. Jarrahi, R. D. Fleischmann, et al. A bioinformatic filter for improved base-call accuracy and polymorphism detection using the Affymetrix GeneChip(R) whole-genome resequencing platform Nucleic Acids Res., December 18, 2007; 35(21): e148 - e148. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
N. L. Hiller, B. Janto, J. S. Hogg, R. Boissy, S. Yu, E. Powell, R. Keefe, N. E. Ehrlich, K. Shen, J. Hayes, et al. Comparative Genomic Analyses of Seventeen Streptococcus pneumoniae Strains: Insights into the Pneumococcal Supragenome J. Bacteriol., November 15, 2007; 189(22): 8186 - 8195. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 C. M. Bergman and H. Quesneville Discovering and detecting transposable elements in genome sequences Brief Bioinform, November 1, 2007; 8(6): 382 - 392. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
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]
|
|
|
|
 |
|
 H. Yukawa, C. A. Omumasaba, H. Nonaka, P. Kos, N. Okai, N. Suzuki, M. Suda, Y. Tsuge, J. Watanabe, Y. Ikeda, et al. Comparative analysis of the Corynebacterium glutamicum group and complete genome sequence of strain R Microbiology, April 1, 2007; 153(4): 1042 - 1058. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. Choudhary, X. Zanhua, Y. X. Fu, and S. Kaplan Genome Analyses of Three Strains of Rhodobacter sphaeroides: Evidence of Rapid Evolution of Chromosome II J. Bacteriol., March 1, 2007; 189(5): 1914 - 1921. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 Y. Wan, S. L. Broschat, and D. R. Call Validation of Mixed-Genome Microarrays as a Method for Genetic Discrimination Appl. Envir. Microbiol., March 1, 2007; 73(5): 1425 - 1432. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 I. M. Sulaiman, K. Tang, J. Osborne, S. Sammons, and R. M. Wohlhueter GeneChip Resequencing of the Smallpox Virus Genome Can Identify Novel Strains: a Biodefense Application J. Clin. Microbiol., February 1, 2007; 45(2): 358 - 363. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. A. Rasko, M. J. Rosovitz, O. A. Okstad, D. E. Fouts, L. Jiang, R. Z. Cer, A.-B. Kolsto, S. R. Gill, and J. Ravel Complete Sequence Analysis of Novel Plasmids from Emetic and Periodontal Bacillus cereus Isolates Reveals a Common Evolutionary History among the B. cereus-Group Plasmids, Including Bacillus anthracis pXO1 J. Bacteriol., January 1, 2007; 189(1): 52 - 64. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. E. Fouts Phage_Finder: Automated identification and classification of prophage regions in complete bacterial genome sequences Nucleic Acids Res., November 6, 2006; 34(20): 5839 - 5851. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 J.-I. Won, S. Park, J.-H. Yoon, and S.-W. Kim An efficient approach for sequence matching in large DNA databases Journal of Information Science, February 1, 2006; 32(1): 88 - 104. [Abstract] [PDF]
|
|
|
|
|
|
A. Caspi and L. Pachter Identification of transposable elements using multiple alignments of related genomes Genome Res., February 1, 2006; 16(2): 260 - 270. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 D. Shapira and J. A. Storer In Place Differential File Compression The Computer Journal, November 1, 2005; 48(6): 677 - 691. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C. L. Lu, T. C. Wang, Y. C. Lin, and C. Y. Tang ROBIN: a tool for genome rearrangement of block-interchanges Bioinformatics, June 1, 2005; 21(11): 2780 - 2782. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
H. L. Chan, T. W. Lam, W. K. Sung, P. W. H. Wong, S. M. Yiu, and X. Fan The mutated subsequence problem and locating conserved genes Bioinformatics, May 15, 2005; 21(10): 2271 - 2278. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. D. Wu and C. K. Watanabe GMAP: a genomic mapping and alignment program for mRNA and EST sequences Bioinformatics, May 1, 2005; 21(9): 1859 - 1875. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. L. Bishop, S. Baker, S. Jenks, M. Fookes, P. O Gaora, D. Pickard, M. Anjum, J. Farrar, T. T. Hien, A. Ivens, et al. Analysis of the Hypervariable Region of the Salmonella enterica Genome Associated with tRNAleuX J. Bacteriol., April 1, 2005; 187(7): 2469 - 2482. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. Itoh, S. Goto, T. Akutsu, and M. Kanehisa Fast and accurate database homology search using upper bounds of local alignment scores Bioinformatics, April 1, 2005; 21(7): 912 - 921. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
X. H. Zheng, F. Lu, Z.-Y. Wang, F. Zhong, J. Hoover, and R. Mural Using shared genomic synteny and shared protein functions to enhance the identification of orthologous gene pairs Bioinformatics, March 15, 2005; 21(6): 703 - 710. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
P. A. Pevzner, H. Tang, and G. Tesler De Novo Repeat Classification and Fragment Assembly Genome Res., September 1, 2004; 14(9): 1786 - 1796. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. W. Ussery, M. S. Jensen, T. R. Poulsen, and P. F. Hallin Genome Update: alignment of bacterial chromosomes Microbiology, August 1, 2004; 150(8): 2491 - 2493. [Full Text] [PDF]
|
|
|
|
|
|
A. C.E. Darling, B. Mau, F. R. Blattner, and N. T. Perna Mauve: Multiple Alignment of Conserved Genomic Sequence With Rearrangements Genome Res., July 1, 2004; 14(7): 1394 - 1403. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. Choudhary, Y.-X. Fu, C. Mackenzie, and S. Kaplan DNA Sequence Duplication in Rhodobacter sphaeroides 2.4.1: Evidence of an Ancient Partnership between Chromosomes I and II J. Bacteriol., April 1, 2004; 186(7): 2019 - 2027. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. L. T. O. Nascimento, A. I. Ko, E. A. L. Martins, C. B. Monteiro-Vitorello, P. L. Ho, D. A. Haake, S. Verjovski-Almeida, R. A. Hartskeerl, M. V. Marques, M. C. Oliveira, et al. Comparative Genomics of Two Leptospira interrogans Serovars Reveals Novel Insights into Physiology and Pathogenesis J. Bacteriol., April 1, 2004; 186(7): 2164 - 2172. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. A. Rasko, J. Ravel, O. A. Okstad, E. Helgason, R. Z. Cer, L. Jiang, K. A. Shores, D. E. Fouts, N. J. Tourasse, S. V. Angiuoli, et al. The genome sequence of Bacillus cereus ATCC 10987 reveals metabolic adaptations and a large plasmid related to Bacillus anthracis pXO1 Nucleic Acids Res., February 11, 2004; 32(3): 977 - 988. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 H. J. Greenberg, W. E. Hart, and G. Lancia Opportunities for Combinatorial Optimization in Computational Biology INFORMS Journal on Computing, January 1, 2004; 16(3): 211 - 231. [Abstract] [PDF]
|
|
|
|
|
|
M. Pop, D. S. Kosack, and S. L. Salzberg Hierarchical Scaffolding With Bambus Genome Res., January 1, 2004; 14(1): 149 - 159. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
V. Gotea, V. Veeramachaneni, and W. Makalowski Mastering seeds for genomic size nucleotide BLAST searches Nucleic Acids Res., December 1, 2003; 31(23): 6935 - 6941. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. A. F. T. van Hijum, A. L. Zomer, O. P. Kuipers, and J. Kok Projector: automatic contig mapping for gap closure purposes Nucleic Acids Res., November 15, 2003; 31(22): e144 - e144. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
L. Herron-Olson, J. Freeman, Q. Zhang, E. F. Retzel, and V. Kapur MGView: an alignment and visualization tool to enhance gap closure of microbial genomes Nucleic Acids Res., September 1, 2003; 31(17): e106 - e106. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. C.-C. Shih and W.-H. Li GS-Aligner: A Novel Tool for Aligning Genomic Sequences Using Bit-Level Operations Mol. Biol. Evol., August 1, 2003; 20(8): 1299 - 1309. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. Farre, R. Roset, M. Huerta, J. E. Adsuara, L. Rosello, M. M. Alba, and X. Messeguer Identification of patterns in biological sequences at the ALGGEN server: PROMO and MALGEN Nucleic Acids Res., July 1, 2003; 31(13): 3651 - 3653. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 C. W. Bogue Genetic Models in Applied Physiology: Invited Review: Functional genomics in the mouse: powerful techniques for unraveling the basis of human development and disease J Appl Physiol, June 1, 2003; 94(6): 2502 - 2509. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
I. Nakagawa, K. Kurokawa, A. Yamashita, M. Nakata, Y. Tomiyasu, N. Okahashi, S. Kawabata, K. Yamazaki, T. Shiba, T. Yasunaga, et al. Genome Sequence of an M3 Strain of Streptococcus pyogenes Reveals a Large-Scale Genomic Rearrangement in Invasive Strains and New Insights into Phage Evolution Genome Res., June 1, 2003; 13(6): 1042 - 1055. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
N. Volfovsky, B. J. Haas, and S. L. Salzberg Computational Discovery of Internal Micro-Exons Genome Res., June 1, 2003; 13(6): 1216 - 1221. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. Brudno, C. B. Do, G. M. Cooper, M. F. Kim, E. Davydov, N. C. S. Program, E. D. Green, A. Sidow, and S. Batzoglou LAGAN and Multi-LAGAN: Efficient Tools for Large-Scale Multiple Alignment of Genomic DNA Genome Res., April 1, 2003; 13(4): 721 - 731. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. Alexandersson, S. Cawley, and L. Pachter SLAM: Cross-Species Gene Finding and Alignment with a Generalized Pair Hidden Markov Model Genome Res., March 1, 2003; 13(3): 496 - 502. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. A. Van Sluys, M. C. de Oliveira, C. B. Monteiro-Vitorello, C. Y. Miyaki, L. R. Furlan, L. E. A. Camargo, A. C. R. da Silva, D. H. Moon, M. A. Takita, E. G. M. Lemos, et al. Comparative Analyses of the Complete Genome Sequences of Pierce's Disease and Citrus Variegated Chlorosis Strains of Xylella fastidiosa J. Bacteriol., February 1, 2003; 185(3): 1018 - 1026. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
O. Couronne, A. Poliakov, N. Bray, T. Ishkhanov, D. Ryaboy, E. Rubin, L. Pachter, and I. Dubchak Strategies and Tools for Whole-Genome Alignments Genome Res., January 1, 2003; 13(1): 73 - 80. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
N. Bray, I. Dubchak, and L. Pachter AVID: A Global Alignment Program Genome Res., January 1, 2003; 13(1): 97 - 102. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
R. D. Fleischmann, D. Alland, J. A. Eisen, L. Carpenter, O. White, J. Peterson, R. DeBoy, R. Dodson, M. Gwinn, D. Haft, et al. Whole-Genome Comparison of Mycobacterium tuberculosis Clinical and Laboratory Strains J. Bacteriol., October 1, 2002; 184(19): 5479 - 5490. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C. Mathe, M.-F. Sagot, T. Schiex, and P. Rouze Current methods of gene prediction, their strengths and weaknesses Nucleic Acids Res., October 1, 2002; 30(19): 4103 - 4117. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
K. Katoh, K. Misawa, K.-i. Kuma, and T. Miyata MAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transform Nucleic Acids Res., July 15, 2002; 30(14): 3059 - 3066. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
L. Y.Y. Chen, S.-H. Lu, E. S.C. Shih, and M.-J. Hwang Single Nucleotide Polymorphism Mapping Using Genome-Wide Unique Sequences Genome Res., July 1, 2002; 12(7): 1106 - 1111. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 T. D. Read, S. L. Salzberg, M. Pop, M. Shumway, L. Umayam, L. Jiang, E. Holtzapple, J. D. Busch, K. L. Smith, J. M. Schupp, et al. Comparative Genome Sequencing for Discovery of Novel Polymorphisms in Bacillus anthracis Science, June 14, 2002; 296(5575): 2028 - 2033. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. L. Delcher, A. Phillippy, J. Carlton, and S. L. Salzberg Fast algorithms for large-scale genome alignment and comparison Nucleic Acids Res., June 1, 2002; 30(11): 2478 - 2483. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
R. J. Mural, M. D. Adams, E. W. Myers, H. O. Smith, G. L. G. Miklos, R. Wides, A. Halpern, P. W. Li, G. G. Sutton, J. Nadeau, et al. A Comparison of Whole-Genome Shotgun-Derived Mouse Chromosome 16 and the Human Genome Science, May 31, 2002; 296(5573): 1661 - 1671. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 J. C. Smoot, K. D. Barbian, J. J. Van Gompel, L. M. Smoot, M. S. Chaussee, G. L. Sylva, D. E. Sturdevant, S. M. Ricklefs, S. F. Porcella, L. D. Parkins, et al. Genome sequence and comparative microarray analysis of serotype M18 group A Streptococcus strains associated with acute rheumatic fever outbreaks PNAS, March 21, 2002; (2002) 62526099. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. Kerlavage, V. Bonazzi, M. di Tommaso, C. Lawrence, P. Li, F. Mayberry, R. Mural, M. Nodell, M. Yandell, J. Zhang, et al. The Celera Discovery SystemTM Nucleic Acids Res., January 1, 2002; 30(1): 129 - 136. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Kurtz, J. V. Choudhuri, E. Ohlebusch, C. Schleiermacher, J. Stoye, and R. Giegerich REPuter: the manifold applications of repeat analysis on a genomic scale Nucleic Acids Res., November 15, 2001; 29(22): 4633 - 4642. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
Z. Ning, A. J. Cox, and J. C. Mullikin SSAHA: A Fast Search Method for Large DNA Databases Genome Res., October 1, 2001; 11(10): 1725 - 1729. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. Wiehe, S. Gebauer-Jung, T. Mitchell-Olds, and R. Guigo SGP-1: Prediction and Validation of Homologous Genes Based on Sequence Alignments Genome Res., September 1, 2001; 11(9): 1574 - 1583. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
P. V. Benos, M. K. Gatt, L. Murphy, D. Harris, B. Barrell, C. Ferraz, S. Vidal, C. Brun, J. Demaille, E. Cadieu, et al. From First Base: The Sequence of the Tip of the X Chromosome of Drosophila melanogaster, a Comparison of Two Sequencing Strategies Genome Res., May 1, 2001; 11(5): 710 - 730. [Abstract] [Full Text]
|
|
|
|
 |
|
 Q. Yuan, J. Quackenbush, R. Sultana, M. Pertea, S. L. Salzberg, and C. R. Buell Rice Bioinformatics. Analysis of Rice Sequence Data and Leveraging the Data to Other Plant Species Plant Physiology, March 1, 2001; 125(3): 1166 - 1174. [Abstract] [Full Text]
|
|
|
|
|
|
J. D. Peterson, L. A. Umayam, T. Dickinson, E. K. Hickey, and O. White The Comprehensive Microbial Resource Nucleic Acids Res., January 1, 2001; 29(1): 123 - 125. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. C. Betts, P. Dodson, S. Quan, A. P. Lewis, P. J. Thomas, K. Duncan, and R. A. McAdam Comparison of the proteome of Mycobacterium tuberculosis strain H37Rv with clinical isolate CDC 1551 Microbiology, December 1, 2000; 146(12): 3205 - 3216. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
L. Florea, C. Riemer, S. Schwartz, Z. Zhang, N. Stojanovic, W. Miller, and M. McClelland Web-based visualization tools for bacterial genome alignments Nucleic Acids Res., September 15, 2000; 28(18): 3486 - 3496. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
Q. Yuan, F. Liang, J. Hsiao, V. Zismann, M.-I. Benito, J. Quackenbush, R. Wing, and R. Buell Anchoring of rice BAC clones to the rice genetic map in silico Nucleic Acids Res., September 15, 2000; 28(18): 3636 - 3641. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. D. Read, R. C. Brunham, C. Shen, S. R. Gill, J. F. Heidelberg, O. White, E. K. Hickey, J. Peterson, T. Utterback, K. Berry, et al. Genome sequences of Chlamydia trachomatis MoPn and Chlamydia pneumoniae AR39 Nucleic Acids Res., March 15, 2000; 28(6): 1397 - 1406. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C. A. Hutchison III, S. N. Peterson, S. R. Gill, R. T. Cline, O. White, C. M. Fraser, H. O. Smith, and J. Craig Venter Global Transposon Mutagenesis and a Minimal Mycoplasma Genome Science, December 10, 1999; 286(5447): 2165 - 2169. [Abstract] [Full Text]
|
|
|
|
|
|
J. C. Smoot, K. D. Barbian, J. J. Van Gompel, L. M. Smoot, M. S. Chaussee, G. L. Sylva, D. E. Sturdevant, S. M. Ricklefs, S. F. Porcella, L. D. Parkins, et al. Genome sequence and comparative microarray analysis of serotype M18 group A Streptococcus strains associated with acute rheumatic fever outbreaks PNAS, April 2, 2002; 99(7): 4668 - 4673. [Abstract] [Full Text] [PDF]
|
|