https://www.dagstuhl.de/19443

October 27 – 31 , 2019, Dagstuhl Seminar 19443

Algorithms and Complexity in Phylogenetics

Organizers

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

For support, please contact

Annette Beyer for administrative matters

Shida Kunz for scientific matters

Dagstuhl Reports

As part of the mandatory documentation, participants are asked to submit their talk abstracts, working group results, etc. for publication in our series Dagstuhl Reports via the Dagstuhl Reports Submission System.

Documents

List of Participants
Shared Documents
Dagstuhl Seminar Wiki

(Use seminar number and access code to log in)

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

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.