Description: There are two components to this project : UPGMA and Neighbor Join implementation.

(i) UPGMA: Your input (sample files are [login to view URL] and [login to view URL]) are distance matrix inputs on UPGMA. You will run the centroid linkage based UPGMA algorithm. Calculate average inter-cluster distances efficiently without needing to look again at individual pairwise distances in original distance matrix. During program execution, your output to the console should indicate at each step which two clusters are being merged in addition to the average distance between them. Your final UPGMA output to the console should include the phylogenetic tree in the parentheses-based Newick format. An inefficient implementation of UPGMA is uploaded as [login to view URL] with I/O expectations consistent here. Your input s (sample files are [login to view URL] and [login to view URL]) are distance matrix inputs. You will run the Neighbor Joining algorithm on such distance matrix inputs. From the initial distance matrix as well as after each merge step, you are to recomputed the average distances r, the transition distance matrix, and the updated distance matrix. You are to output these to the console upon their computation. I have uploaded a perl implementation of NeighborJoin as [login to view URL] which you are encouraged to run and test. Your output should be consistent with that program’s output.