Graph-based method for constructing consensus trees

¹ Department of Computer Science, University of Sherbrooke, 2500, boul. de l’Université, Sherbrooke, J1K 2R1, QC, Canada
² Graduate School of Informatics, Kyoto University, Yoshida-Honmachi, 606-8501, Japan

^* e-mail: Elio.Torquet@USherbrooke.ca
^** e-mail: jj@i.kyoto-u.ac.jp
^*** e-mail: Nadia.Tahiri@USherbrooke.ca

Abstract

A consensus tree is a phylogenetic tree that synthesizes a given collection of phylogenetic trees, all of which share the same leaf labels but may have different topologies, typically obtained through bootstrapping. Our research focuses on creating a consensus tree from a collection of phylogenetic trees, each detailed with branch-length data. We integrate branch lengths into the consensus to encapsulate the progression rate of genetic mutations. However, traditional consensus trees, such as the strict consensus tree, primarily focus on the topological structure of these trees, often neglecting the informative value of branch lengths. This oversight disregards a crucial aspect of evolutionary study and highlights a notable gap in traditional phylogenetic approaches. In this paper, we extend PrimConsTree, an graph-based method for constructing consensus trees. This algorithm incorporates topological information, edge frequency, clade frequency, and branch length to construct a more robust and comprehensive consensus tree. Our adaptation of the well-known Prim algorithm efficiently identifies the maximum frequency branch and maximum frequency nodes to build the optimal consensus tree. This strategy was pre-processed with clustering steps to calibrate the robustness and accuracy of the consensus tree.

Availability and implementation: The source code of PrimConsTree is freely available on GitHub at https://github.com/tahiri-lab/PrimConsTree.