https://www.dagstuhl.de/19443

27. – 31. Oktober 2019, Dagstuhl-Seminar 19443

Algorithms and Complexity in Phylogenetics

Organisatoren

Magnus Bordewich (Durham University, GB)
Britta Dorn (Universität Tübingen, DE)
Simone Linz (University of Auckland, NZ)
Rolf Niedermeier (TU Berlin, DE)

Auskunft zu diesem Dagstuhl-Seminar erteilen

Annette Beyer zu administrativen Fragen

Shida Kunz zu wissenschaftlichen Fragen

Dokumente

Programm des Dagstuhl-Seminars (Hochladen)

(Zum Einloggen bitte Seminarnummer und Zugangscode verwenden)

Motivation

Disentangling the evolutionary relationships between species dates back at least to Charles Darwin and his voyage on board the Beagle. Ever since, the research area of phylogenetics focusses on the reconstruction and analysis of rooted leaf-labeled trees, called phylogenetic (evolutionary) trees, to unravel ancestral relationships between entities like species, languages, and viruses. However, processes such as horizontal gene transfer and hybridization challenge the model of a phylogenetic tree since they result in mosaic patterns of relationships that cannot be represented by a single tree. Indeed, it is now widely acknowledged that rooted leaf-labeled digraphs with underlying cycles, called phylogenetic networks, are better suited to represent evolutionary histories.

Biological questions and applications motivate much of the research in phylogenetics. Nevertheless, most of the software that is routinely used by evolutionary biologists has its roots in theoretical research areas which include algorithms, computational complexity, graph theory, algebra, and probability theory. With a shift from phylogenetic trees towards more complex graphs, the development of new algorithms for phylogenetic networks is currently an active area of research that requires deep insight from computer science and mathematics.

This four-day Dagstuhl Seminar aims at facilitating new interactions and collaborations between the two research communities of (i) computational and mathematical phylogenetics and (ii) theoretical computer science with a focus on algorithms and complexity. Specifically, its goal is to advance the development of novel algorithms (with provable performance guarantee) to reconstruct and analyze phylogenetic networks that are grounded in techniques from theoretical computer science such as parameterized and approximation algorithms.

Topics to be discussed in this seminar include:

  1. The development of new kernelization and bounded-search techniques in phylogenetics, e.g. in the context of computing distances between phylogenetic networks. These distances play a crucial role in searching spaces of phylogenetic networks. While several distances between phylogenetic networks have recently been proposed, no algorithms to `efficiently’ compute them exist.
  2. With the availability of new data types and increasingly bigger data sets, the questions evolutionary biologists wish to answer become more intricate. To allow for flexible analyses, we will discuss multi-objective optimization problems and the computation of Pareto-optimal solutions in phylogenetics.
  3. While many heuristics exist to tackle problems on phylogenetic networks, approximation algorithms are much less common. We will explore the use of approximation algorithms in reconstructing phylogenetic networks from sequence data and combinatorial objects and discuss notions of approximability in a parameterized setting.

The seminar will be split between research talks from both communities and breakout sessions in which small groups of participants work on specific problems to kick-start new collaborations.

Motivation text license
  Creative Commons BY 3.0 DE
  Magnus Bordewich, Britta Dorn, Simone Linz, and Rolf Niedermeier

Classification

  • Bioinformatics
  • Data Structures / Algorithms / Complexity

Keywords

  • Approximation algorithms
  • Evolution
  • Parameterized algorithms
  • Phylogenetic trees and networks

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.