### Jan Weyer-Menkhoff (TRACS visitor, Bielefeld, Germany)

#### Reconstructing the evolutionary tree of different species by solving an integer linear optimization problem

*Wednesday 12 September 2001 at 15.30, JCMB 4312*

##### Abstract

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:

- can be "puzzled together" to a bigger structure representing the evolution,
for example to an unrooted binary tree with leaves labelled uniquely by
elements of X;
- and which maximizes the sum of the confidence of the chosen quartet
trees.

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.

### Seminars by year

*Current*
*2016*
*2015*
*2014*
*2013*
*2012*
*2011*
*2010*
*2009*
*2008*
*2007*
*2006*
*2005*
*2004*
*2003*
*2002*
*2001*
*2000*
*1999*
*1998*
*1997*
*1996*