skip to content

Minimum common supergraphs and haplotype networks

Presented by: 
A Labarre [Libre de Bruxelles]
Friday 21st December 2007 - 11:30 to 11:50
INI Seminar Room 1
Session Chair: 
Mike Steel

In 2005 Cassens, Mardulyn and Milinkovitch proposed a new method for constructing phylogenetic networks in the context of intraspecific genealogies, also known as ``haplotype networks''. The proposed method, called ``Union of Maximum Parsimonious Trees'', is based on the global maximum parsimony approach, which aims at combining all most parsimonious trees into a single graph (in that context, trees are unrooted and undirected). However, their algorithm makes a number of arbitrary choices, produces solutions whose quality depends on the order in which the merging process is performed, and is a heuristic with an unclear objective function. We propose a combinatorial optimisation problem that can be used as a formal model for building such a graph, which consists in finding the minimum common supergraph of a given set of partially labelled trees. We propose a polynomial-time algorithm for solving the problem on two trees of a certain class, and a branch-and-bound algorithm in the case of two arbitrary trees. We will also discuss possible approaches when dealing with more than two trees.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons