With
the rapid accumulation of whole genome sequences
for a wide diversity of taxa, especially microbial
taxa, phylogenetic reconstruction based on changes
in gene order and gene content is showing promise,
particularly for resolving deep (i.e., ancient) branch
splits. However, reconstruction from gene-order data
is even more computationally expensive 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 chloroplast genome data for species of
Campanulaceae on a 512-processor Linux supercluster
with Myrinet, we achieved a one-million-fold speedup
over BPAnalysis. GRAPPA can use either breakpoint
or inversion distance (computed exactly) for its
computation and runs on single-processor machines
as well as parallel and high-performance computers.
