Graph Splitting: A Graph-Based Approach for Superfamily-Scale Phylogenetic Tree Reconstruction

Area of Science:

• Evolutionary biology
• Bioinformatics
• Computational biology

Background:

• Protein superfamilies evolve diverse functions over long evolutionary periods.
• Phylogenetic analysis of divergent protein sequences is challenging due to poor multiple sequence alignment (MSA) performance.

Purpose of the Study:

• To develop a novel phylogenetic method for reconstructing protein superfamily-scale evolutionary trees.
• To address limitations of existing phylogenetic methods when dealing with highly diverged protein sequences.

Main Methods:

• Proposing the Graph Splitting (GS) method, a graph-based approach for rapid phylogenetic tree reconstruction.
• Utilizing evolutionary simulations to assess the accuracy and robustness of the GS method.

Main Results:

• The GS method accurately reconstructs phylogenetic trees for divergent protein sequences.
• The method demonstrates robustness against issues like biased taxon sampling, heterogeneous evolutionary rates, and long-branch attraction.
• Application to the triosephosphate isomerase (TIM)-barrel superfamily revealed rapid evolution of pyrimidine biosynthesis.
• The GS method improves the performance of widely used MSA methods by providing accurate guide trees.

Conclusions:

• The Graph Splitting method offers a robust solution for phylogenetic analysis of protein superfamilies.
• This advancement facilitates the study of early protein evolution and the origins of biological functions.
• The GS method has practical implications for improving multiple sequence alignment accuracy.