High-performance algorithm engineering for computational phylogenetics

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations


Phylogeny reconstruction from molecular data poses complex optimization problems: almost all optimization models are NP-hard and thus computationally intractable. 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. 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 million-fold speedup in running time (on a variety of real and simulated datasets) over the original implementation. We show how algorithmic engineering techniques are directly applicable to a large variety of challenging combinatorial problems in computational biology.

Original languageEnglish (US)
Title of host publicationComputational Science – ICCS 2001 - International Conference, Proceedings
EditorsVassil N. Alexandrov, Jack J. Dongarra, Benjoe A. Juliano, Rene S. Renner, C.J. Kenneth Tan
PublisherSpringer Verlag
Number of pages10
ISBN (Print)3540422331, 9783540422334
StatePublished - 2001
Externally publishedYes
EventInternational Conference on Computational Science, ICCS 2001 - San Francisco, United States
Duration: May 28 2001May 30 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceInternational Conference on Computational Science, ICCS 2001
Country/TerritoryUnited States
CitySan Francisco

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


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

Cite this