Modelagem filogenética das cepas de SARS-CoV-2 via árvore de extensão mínima

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.