Bom dia a todos,

Teremos no dia 22 de Janeiro, terça-feira, pelas 15:00, a apresentação 
e discussão do projecto de tese de mestrado do Joaquim Espada, "Large 
scale phylogenetic inference from noisy data based on minimum weight 
spanning arborescences and local optimization".

Abstract: Current methods struggle to reconstruct phylogenetic 
relationships and evolution patterns of more than a few thousands of 
bacterial genomes. Calculating minimum spanning trees from legacy MLST 
is quick and efficient since legacy MLST is based on only seven loci and 
there is no missing data. Recently, it was shown that finding minimum 
spanning arborescences can help with this problem by considering 
directed graphs instead of undirected ones. The present approach 
depends on a fully connected graph and the running time complexity of 
algorithms for finding spanning arborescences of minimum weight, such as 
the Edmond’s algorithm, is at least quadratic, therefore, the running 
time may still be problematic for analyzing large data sets. The aim of 
this project is to research and evaluate strategies to speed up the 
computation of minimum spanning arborescences in this context. We also 
aim to apply techniques in order to maintain a minimum spanning 
arborescences for an underlying graph which is modified repeatedly by 
having an edge removed, added or the weight updated.

Temos reservada a sala 418 no INESC-ID.

Saudações,

Alexandre Francisco