Busca avançada
Ano de início
Entree

Algoritmos rápidos para Neighbor-Joining vivo

Processo: 19/17116-8
Linha de fomento:Bolsas no Brasil - Iniciação Científica
Vigência (Início): 01 de março de 2020
Vigência (Término): 28 de fevereiro de 2021
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Guilherme Pimentel Telles
Beneficiário:Jhessica Victoria Santos da Silva
Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Assunto(s):Biologia computacional   Filogenia   Algoritmos   Grupos de matrizes   Revisão taxonômica

Resumo

O problema da reconstrução filogenética a partir de uma matriz de distâncias entre as unidades taxonômicas é o problema de construir uma árvore com pesos nas arestas em que as unidades taxonômicas são as folhas e todos os nós internos tenham grau 3 e em que a soma dos pesos no caminho entre cada par de vértices seja igual à distância dada na matriz. Para matrizes aditivas existem algoritmos polinomiais que reconstroem a árvore corretamente. Para matrizes não-aditivas, situação comum em situações práticas, formulações do problema que minimizam o desvio da árvore em relação à matriz são NP-difíceis. O algoritmo Neighbor-Joining é bastante usado para resolver o problema e produz boas soluções em tempo O(n^3). Na filogenia viva, admite-se que zero ou mais unidades taxonômicas sejam nós internos que representam ancestrais vivos, uma situação possível por exemplo para vírus, que evoluem rapidamente. O Live Neighbor-Joining é um algoritmo para reconstrução de filogenias vivas com tempo O(n^4). O objetivo deste projeto é propor variantes mais rápidas do Live Neighbor-Joining. As atividades propostas incluem estudar as variantes rápidas para o Neighbor-Joining, projeto, análise, implementação e experimentação das variantes propostas.