Fixed-Parameter Algorithms in Phylogenetics

Jens  Gramm; Arfst Nickelsen; Till Tantau

Fixed-Parameter Algorithms in Phylogenetics

Jens Gramm, Arfst Nickelsen, Till Tantau

Institute of Theoretical Computer Science

Robert Bosch GmbH

1 Citation (Scopus)

Abstract

We survey the use of fixed-parameter algorithms in
phylogenetics. A central computational problem in
this field is the construction of a likely phylogeny
(genealogical tree) for a set of species based on
observed differences in the phenotype, on
differences in the genotype, or on given partial
phylogenies. Ideally, one would like to construct
so-called perfect phylogenies, which arise from an
elementary evolutionary model, but in practice one
must often be content with phylogenies whose
"distance from perfection" is as small as
possible. The computation of phylogenies also has
applications in seemingly unrelated areas such as
genomic sequencing and finding and understanding
genes. The numerous computational problems arising
in phylogenetics are often NP-complete, but for many
natural parametrizations they can be solved using
fixed-parameter algorithms.

Original language	English
Title of host publication	Methods in Molecular Biology : Bioinformatics: Volume I: Data, Sequence Analysis and Evolution
Volume	452
Publisher	Springer Berlin Heidelberg
Publication date	2008
Pages	507-535
Publication status	Published - 2008

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 9 Industry, Innovation, and Infrastructure

Complexity of haplotyping problems
Tantau, T. (Principal Investigator (PI)), Schnoor, I. (Project Staff), Elberfeld, M. (Project Staff), Kuczewski, J. (Project Staff) & Pohlmann, J. (Associated Staff)
01.01.05 → 31.12.10
Project: DFG Individual Projects

Cite this

@inbook{887be08a28c845a78519214d4c75cc26,

title = "Fixed-Parameter Algorithms in Phylogenetics",

abstract = "We survey the use of fixed-parameter algorithms in phylogenetics. A central computational problem in this field is the construction of a likely phylogeny (genealogical tree) for a set of species based on observed differences in the phenotype, on differences in the genotype, or on given partial phylogenies. Ideally, one would like to construct so-called perfect phylogenies, which arise from an elementary evolutionary model, but in practice one must often be content with phylogenies whose {"}distance from perfection{"} is as small as possible. The computation of phylogenies also has applications in seemingly unrelated areas such as genomic sequencing and finding and understanding genes. The numerous computational problems arising in phylogenetics are often NP-complete, but for many natural parametrizations they can be solved using fixed-parameter algorithms.",

author = "Jens Gramm and Arfst Nickelsen and Till Tantau",

year = "2008",

language = "English",

volume = "452",

pages = "507--535",

booktitle = "Methods in Molecular Biology",

publisher = "Springer Berlin Heidelberg",

}

Fixed-Parameter Algorithms in Phylogenetics. / Gramm, Jens ; Nickelsen, Arfst; Tantau, Till.
Methods in Molecular Biology: Bioinformatics: Volume I: Data, Sequence Analysis and Evolution. Vol. 452 Springer Berlin Heidelberg, 2008. p. 507-535.

Research output: Chapters in Books/Reports/Conference Proceedings › Contributions to collected editions/anthologies › Research › peer-review

TY - CHAP

T1 - Fixed-Parameter Algorithms in Phylogenetics

AU - Gramm, Jens

AU - Nickelsen, Arfst

AU - Tantau, Till

PY - 2008

Y1 - 2008

N2 - We survey the use of fixed-parameter algorithms in phylogenetics. A central computational problem in this field is the construction of a likely phylogeny (genealogical tree) for a set of species based on observed differences in the phenotype, on differences in the genotype, or on given partial phylogenies. Ideally, one would like to construct so-called perfect phylogenies, which arise from an elementary evolutionary model, but in practice one must often be content with phylogenies whose "distance from perfection" is as small as possible. The computation of phylogenies also has applications in seemingly unrelated areas such as genomic sequencing and finding and understanding genes. The numerous computational problems arising in phylogenetics are often NP-complete, but for many natural parametrizations they can be solved using fixed-parameter algorithms.

AB - We survey the use of fixed-parameter algorithms in phylogenetics. A central computational problem in this field is the construction of a likely phylogeny (genealogical tree) for a set of species based on observed differences in the phenotype, on differences in the genotype, or on given partial phylogenies. Ideally, one would like to construct so-called perfect phylogenies, which arise from an elementary evolutionary model, but in practice one must often be content with phylogenies whose "distance from perfection" is as small as possible. The computation of phylogenies also has applications in seemingly unrelated areas such as genomic sequencing and finding and understanding genes. The numerous computational problems arising in phylogenetics are often NP-complete, but for many natural parametrizations they can be solved using fixed-parameter algorithms.

M3 - Contributions to collected editions/anthologies

VL - 452

SP - 507

EP - 535

BT - Methods in Molecular Biology

PB - Springer Berlin Heidelberg

ER -

Fixed-Parameter Algorithms in Phylogenetics

Abstract

UN SDGs

Projects

Complexity of haplotyping problems

Cite this