Robustness of topological supertree methods for reconciling dense incompatible data

Area of Science:

• Computational Biology
• Phylogenetics
• Bioinformatics

Background:

• Phylogenetic supertrees integrate multiple evolutionary trees.
• Incompatible data often prevents the existence of a perfectly compatible supertree.
• Existing supertree methods may lack robustness, failing to recover the true tree from slightly erroneous data.

Purpose of the Study:

• To introduce a measure of robustness for supertree methods, termed the 'radius' (R).
• To evaluate the robustness of existing supertree and consensus tree methods.
• To develop a novel, robust supertree method with guaranteed maximal robustness.

Main Methods:

• Definition and analysis of the supertree method 'radius' (R) as a measure of robustness.
• Evaluation of the maximal possible radius for any supertree method.
• Development and geometric interpretation of the Normalized Triplet Supertree (NTS) method.
• Demonstration that NTS solves an optimization problem.

Main Results:

• The maximal possible radius for any supertree method is R = 1/2.
• Many common supertree and consensus tree methods have a radius of R = 0, indicating low robustness.
• The proposed Normalized Triplet Supertree (NTS) method achieves the maximal radius of R = 1/2.
• NTS is a polynomial-time algorithm.

Conclusions:

• The radius (R) provides a crucial metric for assessing the reliability of supertree construction methods.
• Many widely used methods exhibit poor robustness, potentially yielding incorrect evolutionary trees.
• The Normalized Triplet Supertree (NTS) method offers a theoretically sound and practically efficient approach to robust phylogenetic supertree construction.