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

Abstract

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
Pages1012-1021
Number of pages10
ISBN (Print)3540422331, 9783540422334
DOIs
StatePublished - Jan 1 2001
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)
Volume2074
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherInternational Conference on Computational Science, ICCS 2001
CountryUnited States
CitySan Francisco
Period5/28/015/30/01

Fingerprint

Algorithm Engineering
Phylogenetics
High Performance
Phylogeny
Computational Biology
Combinatorial Problems
Optimization Model
Battery
Speedup
Fold
NP-complete problem
Optimization Problem
Engineering
Farms
Software
Approximation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Moret, B. M. E., Bader, D. A., & Warnow, T. (2001). High-performance algorithm engineering for computational phylogenetics. In V. N. Alexandrov, J. J. Dongarra, B. A. Juliano, R. S. Renner, & C. J. Kenneth Tan (Eds.), Computational Science – ICCS 2001 - International Conference, Proceedings (pp. 1012-1021). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2074). Springer-Verlag. https://doi.org/10.1007/3-540-45718-6_107

High-performance algorithm engineering for computational phylogenetics. / Moret, Bernard M.E.; Bader, David A.; Warnow, Tandy.

Computational Science – ICCS 2001 - International Conference, Proceedings. ed. / Vassil N. Alexandrov; Jack J. Dongarra; Benjoe A. Juliano; Rene S. Renner; C.J. Kenneth Tan. Springer-Verlag, 2001. p. 1012-1021 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2074).

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

Moret, BME, Bader, DA & Warnow, T 2001, High-performance algorithm engineering for computational phylogenetics. in VN Alexandrov, JJ Dongarra, BA Juliano, RS Renner & CJ Kenneth Tan (eds), Computational Science – ICCS 2001 - International Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2074, Springer-Verlag, pp. 1012-1021, International Conference on Computational Science, ICCS 2001, San Francisco, United States, 5/28/01. https://doi.org/10.1007/3-540-45718-6_107
Moret BME, Bader DA, Warnow T. High-performance algorithm engineering for computational phylogenetics. In Alexandrov VN, Dongarra JJ, Juliano BA, Renner RS, Kenneth Tan CJ, editors, Computational Science – ICCS 2001 - International Conference, Proceedings. Springer-Verlag. 2001. p. 1012-1021. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-45718-6_107
Moret, Bernard M.E. ; Bader, David A. ; Warnow, Tandy. / High-performance algorithm engineering for computational phylogenetics. Computational Science – ICCS 2001 - International Conference, Proceedings. editor / Vassil N. Alexandrov ; Jack J. Dongarra ; Benjoe A. Juliano ; Rene S. Renner ; C.J. Kenneth Tan. Springer-Verlag, 2001. pp. 1012-1021 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{ae6118455e58406993b211f32d2d58ed,
title = "High-performance algorithm engineering for computational phylogenetics",
abstract = "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.",
author = "Moret, {Bernard M.E.} and Bader, {David A.} and Tandy Warnow",
year = "2001",
month = "1",
day = "1",
doi = "10.1007/3-540-45718-6_107",
language = "English (US)",
isbn = "3540422331",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag",
pages = "1012--1021",
editor = "Alexandrov, {Vassil N.} and Dongarra, {Jack J.} and Juliano, {Benjoe A.} and Renner, {Rene S.} and {Kenneth Tan}, C.J.",
booktitle = "Computational Science – ICCS 2001 - International Conference, Proceedings",

}

TY - GEN

T1 - High-performance algorithm engineering for computational phylogenetics

AU - Moret, Bernard M.E.

AU - Bader, David A.

AU - Warnow, Tandy

PY - 2001/1/1

Y1 - 2001/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=23044528420&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=23044528420&partnerID=8YFLogxK

U2 - 10.1007/3-540-45718-6_107

DO - 10.1007/3-540-45718-6_107

M3 - Conference contribution

AN - SCOPUS:23044528420

SN - 3540422331

SN - 9783540422334

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1012

EP - 1021

BT - Computational Science – ICCS 2001 - International Conference, Proceedings

A2 - Alexandrov, Vassil N.

A2 - Dongarra, Jack J.

A2 - Juliano, Benjoe A.

A2 - Renner, Rene S.

A2 - Kenneth Tan, C.J.

PB - Springer-Verlag

ER -