MORET, BERNARD M. E.1*, DAVID A. BADER2, TANDY WARNOW3, STACIA K. WYMAN3, and MI YAN2. 1Department of Computer Science, University of New Mexico, Albuquerque, NM 87131; 2Department of Electrical and Computer Engineering, University of New Mexico, Albuquerque, NM 87131; 3Department of Computer Sciences, University of Texas, Austin, TX 78712. - GRAPPA: a high-performance computational tool for phylogeny reconstruction from gene-order data.
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