Projects per year
Abstract
We survey the use of fixedparameter 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
socalled 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 NPcomplete, but for many
natural parametrizations they can be solved using
fixedparameter algorithms.
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
socalled 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 NPcomplete, but for many
natural parametrizations they can be solved using
fixedparameter 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  507535 
Publication status  Published  2008 
Projects
 1 Finished

Complexity of haplotyping problems
Tantau, T., Schnoor, I., Elberfeld, M., Kuczewski, J. & Pohlmann, J.
01.01.05 → 31.12.10
Project: DFG Projects › DFG Individual Projects