Bom dia a todos,

Teremos no dia 25 de Outubro, sexta-feira, pelas 11:00, a apresentação e 
discussão da tese de mestrado do Joaquim Espada, "Large scale phylogenetic 
inference from noisy data based on minimum weight spanning arborescences".

Resumo: 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. The running time
complexity of algorithms for finding spanning arborescences of minimum weight
such as Edmonds' algorithm, for example, is at least quadratic therefore the
running time may still be problematic for analyzing large data sets.  The aim
of this thesis was to study and evaluate strategies to speed up the
calculation of minimum spanning arborescences in phylogenetic context. Here we
present an implementation of Edmonds' algorithm that runs in O(|E| log |V|)
time, where V denotes the set of vertices and E denotes the set of edges of a
directed graph G=(V,E). Furthermore, we applied techniques in order to
maintain a minimum spanning arborescence for an underlying graph which is
modified repeatedly by having an edge removed or added. Our implementation of
the dynamic minimum spanning arborescence proved to be two times faster than
calculating Edmonds' algorithm over a sequence of m operations.

Saudações,

Alexandre Francisco