High-performance algorithm engineering for computational phylogenetics

Bernard M.E. Moret, David A. Bader, Tandy Warnow

Research output: Contribution to journalArticle

Abstract

A phylogeny is the evolutionary history of a group of organisms; systematists (and other biologists) attempt to reconstruct this history from various forms of data about contemporary organisms. Phylogeny reconstruction is a crucial step in the understanding of evolution as well as an important tool in biological, pharmaceutical, and medical research. Phylogeny reconstruction from molecular data is very difficult: almost all optimization models give rise to NP-hard (and thus computationally intractable) problems. Yet approximations must be of very high quality in order to avoid outright biological nonsense. Thus many biologists have been willing to run farms of processors for many months in order to analyze just one dataset. High-performance algorithm engineering offers a battery of tools that can reduce, sometimes spectacularly, the running time of existing phylogenetic algorithms, as well as help designers produce better algorithms. We present an overview of algorithm engineering techniques, illustrating them with an application to the "breakpoint analysis" method of Sankoff et al., which resulted in the GRAPPA software suite. GRAPPA demonstrated a speedup in running time by over eight orders of magnitude over the original implementation on a variety of real and simulated datasets. We show how these algorithmic engineering techniques are directly applicable to a large variety of challenging combinatorial problems in computational biology.

Original languageEnglish (US)
Article number397940
Pages (from-to)99-111
Number of pages13
JournalJournal of Supercomputing
Volume22
Issue number1
DOIs
StatePublished - May 2002
Externally publishedYes

Keywords

  • Breakpoint analysis
  • Computational genomics
  • Genome rearrangement
  • High-performance computing
  • Phylogeny reconstruction
  • Sorting by reversals

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Hardware and Architecture
  • Electrical and Electronic Engineering
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'High-performance algorithm engineering for computational phylogenetics'. Together they form a unique fingerprint.

  • Cite this