Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/31504
Título: | Modelagem filogenética das cepas de SARS-CoV-2 via árvore de extensão mínima |
Título(s) alternativo(s): | Phylogenetic modeling of SARS-CoV-2 strains via minimal spanning tree |
Autor(es): | Barreta, Guilherme Augusto |
Orientador(es): | Casanova, Dalcimar |
Palavras-chave: | COVID-19 (Doença) Representações dos grafos Algorítmos computacionais COVID-19 (Disease) Representations of graphs Computer algorithms |
Data do documento: | 28-Abr-2022 |
Editor: | Universidade Tecnológica Federal do Paraná |
Câmpus: | Dois Vizinhos |
Citação: | BARRETA, Guilherme Augusto. Modelagem filogenética das cepas de SARS-CoV-2 via árvore de extensão mínima. 2022. Monografia (Especialização em Ciência de Dados) - Universidade Tecnológica Federal do Paraná, Dois Vizinhos, 2022. |
Resumo: | Desde a pandemia iniciada em Wuhan na China, em 12 de dezembro de 2019, surgiram muitas cepas do SARS-CoV-2. Na esteira da pandemia um esforço internacional para o sequenciamento genômico foi instalado, com o objetivo de monitorar a evolução do vírus e auxiliar na tomada de decisão. No entanto a análise de sequências genéticas não é trivial e requer algumas transformações a fim de facilitar a análise. A estratégia utilizada nesse trabalho é a construção da árvore filogenética e, para isso, é necessário abstrair o problema como um grafo e aplicar um algoritmo de árvore de extensão mínima. As arestas são resultantes das dissimilaridades entre sequências genéticas. Essa dissimilaridade é medida com a distância de Levenshtein. A complexidade dessa abordagem é O(n 2 (k) 2 ), sendo n o número de sequências e k o tamanho médio das sequências. Para reduzir a complexidade desse algoritmo, foi proposto também um algoritmo heurístico. Dessa maneira a complexidade passa a ser O(n(f(n) + r(n))(k) 2 ), sendo f o número médio de folhas visitadas e r o número médio de nós visitados (com exceção das folhas) até encontra o ótimo local. Também é válido que f(n) + r(n) ≤ n. Os resultados indicam que o tempo de execução relativo ao algoritmo determinístico tende a diminuir ao mesmo tempo em que a soma mínima de arestas apresenta um erro médio de 6%. Espera-se que, com os resultados apresentados, esse trabalho possa servir como base de compreensão e predição de mutações do coronavírus em trabalhos futuros. |
Abstract: | Since the pandemic that started in Wuhan, China, on December 12, 2019, many strains of SARS-CoV-2 appear. With that, monitoring was necessary. Fortunately, there is a international effort for genomic sequencing and makes these data publicly available. Data alone do not produce relevant information until some strategy is used to manipulate them. The strategy used in this work is the construction of the phylogenetic tree. For this, it is necessary to abstract the problem as a graph and apply a minimum spanning tree (MST). The edges are the result of dissimilarities between genetic sequences. This dissimilarity is measured with Levenshtein distance. The complexity of this approach is O(n 2 (k) 2 ), where n is the number of sequences and k is the average size of the sequences. To reduce the complexity of this algorithm, a heuristic algorithm was also proposed. In this way the complexity becomes O(n(f(n)+r(n))(k) 2 ), where f is the average number of visited leaves and r is the average number of visited nodes (with the exception of leaves) until it finds the optimal location. It is also valid that f(n) + r(n) ≤ n. The results indicate that the time of execution relative to the deterministic algorithm tends to decrease at the same time that the minimal sum of edges has an average error of 6%. It is expected that, with the results presented, this work can serve as a basis for understanding and predicting mutations in the coronavirus in future work. |
URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/31504 |
Aparece nas coleções: | DV - Ciência de Dados |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
modelagemsars-cov-2.pdf | 1,67 MB | Adobe PDF | Visualizar/Abrir |
Este item está licenciada sob uma Licença Creative Commons