imPhy: Imputing Phylogenetic Trees with Missing Information Using Mathematical Programming.

Area of Science:

• Genomics
• Computational Biology
• Evolutionary Biology

Background:

• Genome-wide phylogenetic analyses are advancing rapidly.
• Genomic data often suffers from missingness, complicating evolutionary tree reconstruction.
• Existing methods for handling missing data in gene trees lead to significant information loss.

Purpose of the Study:

• To develop an optimization-based imputation method for inferring missing distances in gene trees.
• To introduce imPhy, a research pipeline for simulating, imputing, and reconstructing gene trees with missing data.
• To evaluate the effectiveness of the imputation approach on both simulated and empirical datasets.

Main Methods:

• A mixed integer non-linear programming model for inferring missing pairwise distances.
• The imPhy pipeline: simulation of gene trees with missing leaves, imputation, and reconstruction using Neighbor Joining (NJ) and Unweighted Pair Group Method with Arithmetic Mean (UPGMA).
• Evaluation using normalized mean square errors on simulated and empirical (Apicomplexa, lungfish) datasets.

Main Results:

• The proposed imputation method successfully reconstructs gene trees with incomplete information.
• Very small normalized mean square errors were achieved, even with up to 50% missing data.
• The imPhy pipeline provides a comprehensive solution for handling missing data in phylogenetic analyses.

Conclusions:

• Optimization-based imputation is an effective strategy for overcoming data missingness in phylogenetic analyses.
• The imPhy pipeline offers a robust solution for reconstructing accurate gene trees from incomplete genomic data.
• This approach preserves valuable information that would otherwise be discarded, improving evolutionary inference.