Development of a large-scale comparative genome system and its application to the analysis of mycobacteria genomes

As the number of whole genome sequences available continues to increase rapidly, the raw scale of the sequence data being used in analysis is the first hurdle for comparative genome analysis. When performing whole genome alignments, large-scale rearrangements make it necessary to first find out roughly which short well-conserved segments correspond to what other segments (termed anchors). Successful results have been achieved by adapting tools like BLAT and BLASTZ on a problem-to-problem basis, but the work required to perform a single alignment is considerable. Recently, new programs such as Mauve and Pattern-Hunter can handle slightly larger inputs, but the memory/time requirements for sequences like Human and Chimp X chromosomes are prohibitive for most computational environments. Our novel algorithm, which we have implemented in a program called Murasaki (available at http://murasaki.dna.bio.keio.ac.jp), makes it possible to identify anchors of multiple large sequences on the scale of several hundred megabases (e.g. three mammal chromosomes) in a matter of minutes. We also demonstrate an application of Murasaki to the comparative analysis of multiple mycobacteria genomes.