Efficient multiple genome alignment

Abstract

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.