FenixEdu™

Dissertação

{en_GB=Community Finding with Applications on Phylogentic Networks} {} EVALUATED

Detalhes: {pt=Com os recentes métodos de sequenciamento de alto rendimento, novas formas de visualizar e analisar dados são necessárias. Apesar de já existirem algumas ferramentas, estas não são escaláveis ou requerem elevado conhecimento técnico para serem úteis em filogenia. O objetivo da tese foi implementar três algoritmos de deteção de comunidades – Louvain, Infomap e Layered Label Propagation (LLP); submetê-los a testes de desempenho, utilizando duas redes sintéticas: Girvan-Newman (GN) e Lancichinetti-Fortunato-Radicchi (LFR); testá-los em redes reais, nomeadamente, numa criada a partir de um perfil de MLST de Staphylococcus aureus; comparar ferramentas de visualização de dados - Cytoscape.js e D3.js, e implementar uma aplicação web englobando tudo isto (mscthesis.herokuapp.com). Louvain, Infomap e LLP foram implementados em JavaScript. Por omissão, as próximas conclusões são válidas para as redes GN e LFR. Louvain foi o mais rápido dos três, e o mais preciso quando executado em redes com comunidades bem definidas. Em redes com maior mistura, LLP apresentou os melhores resultados. Foi vantajoso aumentar o parâmetro de resolução em redes GN mal definidas, contrariamente a bem definidas. Em redes LFR, o aumento do mesmo parâmetro piorou a partição obtida. O aumento do grau médio dos nós melhorou a partição encontrada e sugeriu uma menor deteção fortuita de comunidades. Foi computacionalmente mais exigente gerar redes GN com maior mistura ou grau médio, utilizando o algoritmo aqui desenvolvido ou o da implementação LFR. Em S. aureus, Louvain foi o mais rápido e o preciso na deteção dos conjuntos de estirpes derivadas diretamente do ancestral comum., en=With the advent of high-throughput sequencing methods, new ways of visualizing and analyzing increasingly amounts of data are needed. Although some software already exist, they do not scale well or require advanced skills to be useful in phylogenetics. The aim of this thesis was to implement three community finding algorithms – Louvain, Infomap and Layered Label Propagation (LLP); to benchmark them using two synthetic networks – Girvan-Newman (GN) and Lancichinetti-Fortunato-Radicchi (LFR); to test them in real networks, particularly, in one derived from a Staphylococcus aureus MLST dataset; to compare visualization frameworks – Cytoscape.js and D3.js, and, finally, to make it all available online (mscthesis.herokuapp.com). Louvain, Infomap and LLP were implemented in JavaScript. Unless otherwise stated, next conclusions are valid for GN and LFR. In terms of speed, Louvain outperformed all others. Considering accuracy, in networks with well-defined communities, Louvain was the most accurate. For higher mixing, LLP was the best. Contrarily to weakly mixed, it is advantageous to increase the resolution parameter in highly mixed GN. In LFR, higher resolution decreases the accuracy of detection, independently of the mixing parameter. The increase of the average node degree enhanced partitioning accuracy and suggested detection by chance was minimized. It is computationally more intensive to generate GN with higher mixing or average degree, using the algorithm developed in the thesis or the LFR implementation. In S. aureus network, Louvain was the fastest and the most accurate in detecting the clusters of seven groups of strains directly evolved from the common ancestor.}
Keywords: {pt=Deteção Comunidades, Redes Filogenéticas, Visualização Dados, Aplicação Web, en=Community Finding, Phylogenetic Networks, Data Visualization, Web Application}

Discussão: junho 25, 2019, 14:0