With the rapid accumulation of whole genome sequences for a wide diversity of taxa, phylogenetic reconstruction based on changes in gene order and gene content is showing promise, particularly for resolving deep branches. However, reconstruction from gene order data is even more computationally intensive than reconstruction from sequence data, particularly in groups with large numbers of genes and highly rearranged genomes. We have developed a software suite, GRAPPA, that extends the breakpoint analysis (BPanalysis) method of Sankoff and Blanchette while running much faster: in a recent analysis of the Campanulaceae dataset (reported by Robert Jansen) on a 512-processor supercluster, we achieved a one-million-fold speedup over BPAnalysis. GRAPPA currently can use either breakpoint or inversion distance (computed exactly) for its computation, runs on single-processor machines as well as parallel ones, and has been ported to all Unix and Windows OS. Our next release will support analysis of genomes with repeats (using the exemplar strategy proposed by Sankoff) and with (mildly) unequal gene content (using induced breakpoints), while also supporting refinements of promising candidate trees with TBR techniques, and incorporating the IEBP and EDE distance corrections (presented by Robert Jansen).

Key words: breakpoint analysis, gene rearrangement, high-performance computing, phylogeny