Algoritmos rápidos para Neighbor-Joining vivo

• Processo: 19/17116-8
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de março de 2020
• Data de Término da vigência: 31 de janeiro de 2021
• Área de 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
• Palavra(s)-Chave do Pesquisador: bioinformática | Engenharia de Algoritmos | Filogenia | Filogenia-viva | Neighbor-Joining | Bioinformática

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.