Anthony Labarre

Algorithms for computing genome distances and for designing phylogenetic networks

Motivated by applications in biology, the research project consists of two parts:

1. Genome Rearrangements Problems
   Genomes can be modelled for instance by (signed) permutations or by collections of subsets. Operations on these structures are studied, which are thought to model mutations in evolution. The distance between two genomes is defined as the minimum number of operations that transform the first genome into the second one. Computing the distance and finding the corresponding sequence of transformations is the problem of "sorting by Xs" (in the case of permutations), where X is one (or several) operation(s) allowed. Among many unsolved problems, we investigate
   1. the complexity of computing the distance,
   2. the maximal values of the distance and,
   3. which operations best model evolution in practice.
   Also under analysis are the relations between several distances, and possible ways to weight the miscelleaneous operations in the distance definition.

2. Phylogenetic Networks
   Phylogenetic trees have been used for quite a long time in genetics. The parsimony criterion is applied for choosing a tree that best models the evolution within a group of species. However, a lot of equally good trees can be constructed in general. Since no such tree should be viewed as the best one, geneticists have been led to consider phylogenetic networks which summarize families of trees, wherein several paths between two species are kept instead of just one as in trees. Several approaches have been proposed for building a network for a given family of parsimonious trees. We are working on the design of an algorithm that obtains the most correct graph (that is, the one closest to the true genealogy).

Supervisor:
Prof. J.-P. Doignon (ULB, Belgium).