02. February 2017, 16:15 p.m.

Ernst-Abbe-Platz 2, seminar room 3423

Bad Character Deletion Supertrees

Markus Fleischauer
(Chair for Bioinformatics, Institute of Computer Science, FSU Jena)

Supertree methods combine a set of phylogenetic trees into a single supertree. Similar to supermatrix methods, these methods provide a way to reconstruct larger parts of the Tree of Life. Different from them, supertree methods allow us to analyze large datasets without constructing and analyzing a multiple sequence alignment for the complete set of taxa. Therefore, supertree methods can be used as part of divide-and-conquer meta techniques, potentially evading the computational complexity of phylogenetic inference methods such as maximum likelihood without using their accuracy. Currently the combining step of such divide-and-conquer techniques relies on supertree methods that have to solve NP-hard optimization problems (MRP).

In my talk, I will explain the Bad Character Deletion (BCD) supertree method and why it is the missing piece for a more powerful divide and conquer approach to estimate large scale phylogenies. BCD adapts the FlipCut heuristic to remove the minimum number of clades from the source trees so that they are compatible. Furthermore, I show how to use bootstrap values when removing bad clades. On simulated datasets, BCD outperforms the state-of-the-art algorithms SuperFine and Matrix Representation with Parsimony. BCD supertrees simultaneously produces high-quality supertrees and has guaranteed polynomial running time.