Fast algorithms for live Neighbor-Joining

• Grant number: 19/17116-8
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: March 01, 2020
• End date: January 31, 2021
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Guilherme Pimentel Telles
• Grantee: Jhessica Victoria Santos da Silva
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

The distance-based phylogenetic reconstruction problem is the problem of building a tree with weights on its edges where the leaves are the taxonomic units, every internal node has degree 3 and where the sum of weights in paths between pairs of leaves are equal to the distance given in the input matrix. For additive matrices, there are polynomial-time algorithms that correctly reconstruct a tree. For non-additive matrices, a typical situation in practice, formulations of the problem that minimize the difference between the tree and the matrix are NP-hard. The Neighbor-Joining algorithm is widely used to solve the problem and produces good solutions in O(n^3) time. In live phylogeny, zero or more taxonomic units may be internal nodes representing live ancestors, a situation that may occur for the virus, which quickly evolves. The Live Neighbor-Joining is an algorithm for live phylogeny reconstruction with O(n^4) running time. The goal of this project is to propose fast variants of Live Neighbor-Joining. The proposed activities include studying the fast variants for Neighbor-Joining, design, analysis, implementation, and experimentation of the proposed variants. (AU)