Efficient multiple genome alignment
Michael Höhl, Stefan Kurtz, Enno Ohlebusch · Bioinformatics · 2002
Abstract Motivation: To allow a direct comparison of the genomic DNA sequences of sufficiently similar organisms, there is an urgent need for software tools that can align more than two genomic sequences. Results: We developed new algorithms and a software tool ‘Multiple Genome Aligner’ (MGA for short) that efficiently computes multiple genome alignments of large, closely related DNA sequences. For example, it can align 85% percent of the complete genomes of six human adenoviruses (average length 35305 bp.) in 159 seconds. An alignment of 74% of the complete genomes of three of strains of E. coli (lengths: 5528445; 5498450; 4639221~bp.) is produced in 30 minutes. Availability: The software MGA is available free of charge for non-commercial research institutions. For details see http://bibiserv.techfak.uni-bielefeld.de/mga/ Contact: kurtz@techfak.uni-bielefeld.deenno@techfak.uni-bielefeld.de Keywords: genome comparison; multiple alignment; efficient algorithms; graph algorithms; suffix trees.
Cited by 159 works. doi:10.1093/bioinformatics/18.suppl_1.s312
Authors
References
- Gapped BLAST and PSI-BLAST: a new generation of protein database search programs
- CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice
- A general method applicable to the search for similarities in the amino acid sequence of two proteins
- Introduction to Algorithms
- Linear pattern matching algorithms
- A Space-Economical Suffix Tree Construction Algorithm
- Algorithms on strings, trees, and sequences
- Suffix Arrays: A New Method for On-Line String Searches
- Alignment of whole genomes
- Biological sequence analysis