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

Dagstuhl Service Team

Documents

Dagstuhl Report, Volume 9, Issue 10 Dagstuhl Report
Aims & Scope
List of Participants
Shared Documents
Dagstuhl's Impact: Documents available

Summary

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.

The objective of the seminar was to facilitate interactions 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 was 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.

This four-day seminar brought together 27 researchers from ten countries, whose research spans theoretical computer science and algorithms, (discrete) mathematics, and computational and mathematical phylogenetics. The seminar program included six overview talks, nine research talks (one of which via Skype), a rump session for short five-minute contributions, and slots for discussions and group work on open problems. More specifically, the overview talks provided introductions to techniques and current trends in parameterized algorithms, combinatorial decompositions, and enumeration algorithms on one hand, and introductions to spaces of phylogenetic trees and networks, and the reconstruction of networks from smaller networks and trees on the other hand. Additionally, each overview talk included open questions and challenges that provided a foundation for discussions and group work throughout the week. The research talks, of which three were given by postgraduate students, covered topical streams of research, including phylogenetic split theory, the placement of phylogenetic problems in higher classes of the polynomial hierarchy, new insight into the popular so-called Tree Containment problem, and phylogenetic diversity and biodiversity indices. Moreover, five working groups were formed on the second day of the seminar. While the research projects that were initiated in these groups are ongoing, some groups obtained first results during the seminar that were presented on the last day.

By building on initially existing synergies between the two research communities, the seminar has taken a leap towards developing new and fostering existing collaborations between both communities. Collaborative work was encouraged and put into practice over formal and informal discussions as well as three group work sessions. Since a significant number of open problems in phylogenetics require the combined expertise of experts in phylogenetics and theoretical computer science, we expect the collaborations formed at Schloss Dagstuhl to make progress on problems across the traditional discipline boundaries and, ideally, lead to joint peer-reviewed journal or conference publications.

To conclude, this seminar has acknowledged that exchange and connection between the two research communities of theoretical computer science and phylogenetics is fruitful for both sides. Techniques and methods from algorithms and complexity as well as theoretical considerations in general enable, account for, and foster new insights in problems from phylogenetics. Conversely, the specific features and problem structures appearing in the context of phylogenetic trees and networks provide novel theoretical challenges and new directions for foundational research in algorithms and computational complexity.

We thank all participants for their contributions and for openly sharing their ideas and research questions that led to a positive working atmosphere and many discussions throughout the seminar. Furthermore, we sincerely thank the team of Schloss Dagstuhl for their excellent support and communication as well as for providing an enjoyable seminar environment.

Summary text license
  Creative Commons BY 3.0 Unported license
  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.