Phylogeny inference based on spectral graph clustering.

Area of Science:

• Computational Biology
• Bioinformatics
• Phylogenetics

Background:

• Phylogeny inference is crucial in computational biology.
• Traditional methods like maximum parsimony and maximum likelihood become computationally intractable with large datasets.
• Existing distance-based agglomerative algorithms can accumulate errors during recursive merging, leading to inaccurate phylogenetic trees.

Purpose of the Study:

• To propose a novel splitting algorithm for phylogeny inference using spectral graph clustering (SGC).
• To address the limitations of existing agglomerative methods in terms of accuracy and recursive distance matrix estimation.

Main Methods:

• Utilized spectral graph clustering (SGC) technique for phylogeny inference.
• Employed a maximum cut criterion and solved a generalized eigenvalue system to split graphs.
• Developed a heuristic strategy for constructing phylogenies, accommodating non-additive distance functions.

Main Results:

• The SGC algorithm successfully infers phylogeny without recursive distance matrix estimation.
• Demonstrated superior tree topology accuracy compared to the Neighbor-joining (NJ) algorithm on simulated datasets.
• Provided strong support for hypotheses generated by other methods, as evidenced in Baculovirus genome analysis.

Conclusions:

• The spectral graph clustering (SGC) algorithm is an efficient and accurate method for phylogeny inference.
• SGC offers a promising alternative to existing algorithms, particularly for large-scale phylogenetic analyses.
• The heuristic approach enhances phylogenetic construction, even with non-additive distance data.