# PLG

## Seminar

### Minimum common supergraphs and haplotype networks

Seminar Room 1, Newton Institute

#### Abstract

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.

## Comments

Start the discussion!