The Matrix Representation with Flipping problem and the FlipCut heuristic

Abstract:

In computational phylogenetics, supertree methods assemble
phylogenetic trees with non-identical but overlapping taxon sets, into
a larger supertree: These supertrees contains all taxa of all input
trees and describes the evolutionary relationship of these taxa.  This
problem can be formalized in different ways, to cope with
contradictory information in the input, and numerous supertree methods
have been suggested during the last 25 years.

I will concentrate on the Matrix Representation with Flipping (MRF)
framework: The input trees are encoded in a 0/1/?-matrix, and we
search for a minimum set of 0/1-flips such that the resulting matrix
admits a directed perfect phylogeny.  This is an NP-hard problem, but
if all input trees share the same set of taxa, the problem is fixed-
parameter tractable.  Otherwise, the problem is W[2]-hard and cannot
be approximated within a constant factor.  I will present a data
reduction as well as an ILP formulation for the problem which,
unfortunately, both do not work well in practice.

Finally, I will present a novel heuristic for the problem, named
FlipCut supertrees.  Evaluations of the heuristic are extremely
promising: On the standard SMIDGen dataset, our method outperforms the
current gold standard SuperFine as well as all other supertree
methods.
 

About the speaker:

Sebastian Böcker is a full professor at the Friedrich Schiller
University Jena, and leader of the Chair for Bioinformatics at the
Institute for Computer Science.  Previous to his academic career, he
has worked for three years in industry.  He has a long-standing
expertise in bioinformatics, algorithmics, and combinatorial
optimization.  He is author of more than 95 refereed papers.  He is
particularly interested in computational methods for mass
spectrometry, phylogenetics and supertree methods, gene cluster
analysis, and algorithm development for computationally hard problems
in bioinformatics.