Industrial applications of high-performance computing for phylogeny reconstruction

David A. Bader, Bernard M.E. Moret, Lisa Vawter

Research output: Contribution to journalArticlepeer-review

37 Scopus citations


Phylogenies (that is, tree-of-life relationships) derived from gene order data may prove crucial in answering some fundamental open questions in biomolecular evolution. Real-world interest is strong in determining these relationships. For example, pharmaceutical companies may use phylogeny reconstruction in drug discovery for discovering synthetic pathways unique to organisms that they wish to target. Health organizations study the phylogenies of organisms such as HIV in order to understand their epidemiologies and to aid in predicting the behaviours of future outbreaks. And governments are interested in aiding the production of such foodstuffs as rice, wheat and potatoes via genetics through understanding of the phylogenetic distribution of genetic variation in wild populations. Yet few techniques are available for difficult phylogenetic reconstruction problems. Appropriate tools for analysis of such data may aid in resolving some of the phylogenetic problems that have been analyzed without much resolution for decades. 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 break-point or inversion distance (computed exactly) for its computation and runs on single-processor machines as well as parallel and high-performance computers.

Original languageEnglish (US)
Pages (from-to)159-168
Number of pages10
JournalProceedings of SPIE - The International Society for Optical Engineering
Issue number1
StatePublished - Jul 27 2001
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Electronic, Optical and Magnetic Materials
  • Condensed Matter Physics
  • Computer Science Applications
  • Applied Mathematics
  • Electrical and Electronic Engineering


  • Breakpoint analysis
  • Computational genomics
  • Drag discovery
  • Gene rearrangement
  • High-performance computing
  • Phylogeny reconstruction


Dive into the research topics of 'Industrial applications of high-performance computing for phylogeny reconstruction'. Together they form a unique fingerprint.

Cite this