Dagstuhl-Seminar 19443
Algorithms and Complexity in Phylogenetics
( 27. Oct – 31. Oct, 2019 )
(zum Vergrößern in der Bildmitte klicken)
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/19443
Organisatoren
- Magnus Bordewich (Durham University, GB)
- Britta Dorn (Universität Tübingen, DE)
- Simone Linz (University of Auckland, NZ)
- Rolf Niedermeier (TU Berlin, DE)
Kontakt
- Shida Kunz (für wissenschaftliche Fragen)
- Annette Beyer (für administrative Fragen)
Impacts
- On the maximum agreement subtree conjecture for balanced trees : article - Bordewich, Magnus; Linz, Simone; Owen, Megan; St. John, Katherine; Semple, Charles; Wicke, Kristina - Cornell University : arXiv.org, 2020. - 21 pp..
- Reflections on kernelizing and computing unrooted agreement forests : article - Wersch, Rim van; Kelk, Steven; Linz, Simone; Stamoulis, Georgios - Berlin : Springer, 2021. - pp. 425-451 - (Annals of operations research ; 309. 2021).
- Phylogenetic diversity indices from an affine and projective viewpoint - Moulton, Vincent; Spillner, Andreas; Wicke, Kristina - Cornell University : arXiv.org, 2021. - 23 pp..
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:
- 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.
- 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.
- 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.
Creative Commons BY 3.0 DE
Magnus Bordewich, Britta Dorn, Simone Linz, and Rolf Niedermeier
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.
Magnus Bordewich, Britta Dorn, Simone Linz, and Rolf Niedermeier
- Allan Bai (University of Canterbury - Christchurch, NZ)
- Magnus Bordewich (Durham University, GB) [dblp]
- Laurent Bulteau (University Paris-Est - Marne-la-Vallée, FR) [dblp]
- Janosch Döcker (Universität Tübingen, DE) [dblp]
- Britta Dorn (Universität Tübingen, DE) [dblp]
- Anne-Sophie Himmel (TU Berlin, DE) [dblp]
- Katharina T. Huber (University of East Anglia - Norwich, GB) [dblp]
- Mark E. L. Jones (CWI - Amsterdam, NL) [dblp]
- Christian Komusiewicz (Universität Marburg, DE) [dblp]
- Simone Linz (University of Auckland, NZ) [dblp]
- Marefatollah Mansouri (TU Wien, AT)
- Catherine McCartin (Massey University, NZ) [dblp]
- Vincent Moulton (University of East Anglia - Norwich, GB) [dblp]
- André Nichterlein (TU Berlin, DE) [dblp]
- Rolf Niedermeier (TU Berlin, DE) [dblp]
- Megan Owen (Lehman College - New York, US) [dblp]
- Charles Semple (University of Canterbury - Christchurch, NZ) [dblp]
- Katherine St. John (CUNY Hunter College - New York, US) [dblp]
- Leen Stougie (CWI - Amsterdam, NL) [dblp]
- Till Tantau (Universität zu Lübeck, DE) [dblp]
- Nihan Tokac (Antalya International University, TR) [dblp]
- Alexandru Tomescu (University of Helsinki, FI)
- Leo van Iersel (TU Delft, NL) [dblp]
- Mathias Weller (University Paris-Est - Marne-la-Vallée, FR) [dblp]
- Kristina Wicke (Universität Greifswald, DE) [dblp]
- Norbert Zeh (Dalhousie University - Halifax, CA) [dblp]
Klassifikation
- bioinformatics
- data structures / algorithms / complexity
Schlagworte
- approximation algorithms
- evolution
- parameterized algorithms
- phylogenetic trees and networks
