In this talk I would like to present an integer linear optimization problem, and some first experiences, made together with the optimization group, how to solve it. It is derived from the so called "Quartet Puzzle Problem" which can be solved to gain information about the evolution of different species, and to reconstruct the phylogenetic tree.
Let X be the set of investigated species. For each four different species a, b, c, and d there exist exactly three possible binary unrooted trees, called quartet trees. They are symbolized by ab|cd, ac|bd, and ad|bc. The set of all quartet trees of X will be called Q.
Assume that genomic sequences are known for each of the investigated species, and assume that, in addition, to each of the quartet trees of Q a real number was calculated which represents the confidence, that the corresponding binary tree represents the true family relation. The Quartet Puzzle Problem is to find a subset of Q which:
The related integer linear problem has got some interesting properties. There are much more constraints than variables, the polytope spaned by the feasible solutions is very symmetric, it is very degenerate in the origin, and most of the variables of the solution of the relaxed solution are anyway integer. So, not many branch and bound steps are needed.
Current 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
