imPhy: Imputing Phylogenetic Trees with Missing Information using Mathematical Programming

Loading...
Thumbnail Image
Authors
Yasui, Niko
Vogiatzis, Chrysafis
Yoshida, Ruriko
Fukumizu, Kenji
Subjects
Gene trees
Missing information
Mixed integer non-linear programming
Advisors
Date of Issue
2018
Date
2018
Publisher
IEEE
Language
Abstract
The advances of modern genomics allow researchers to apply phylogenetic analyses on a genome-wide scale. While large volumes of genomic data can be generated cheaply and quickly, data missingness is a non-trivial and somewhat expected problem. Since the available information is often incomplete for a given set of genetic loci and individual organisms, a large proportion of trees that depict the evolutionary history of a single genetic locus, called gene trees, fail to contain all individuals. Data incompleteness causes difficulties in data collection, information extraction, and gene tree inference. Furthermore, identifying outlying gene trees, which can represent horizontal gene transfers, gene duplications, or hybridizations, is difficult when data is missing from the gene trees. The typical approach is to remove all individuals with missing data from the gene trees, and focus the analysis on individuals whose information is fully available – a huge loss of information. In this work, we propose and design an optimization-based imputation approach to infer the missing distances between leaves in a set of gene trees via a mixed integer non-linear programming model. We also present a new research pipeline, imPhy, that can (i) simulate a set of gene trees with leaves randomly missing in each tree, (ii) impute the missing pairwise distances in each gene tree, (iii) reconstruct the gene trees using the Neighbor Joining (NJ) and Unweighted Pair Group Method with Arithmetic Mean (UPGMA) methods, and (iv) analyze and report the efficiency of the reconstruction. To impute the missing leaves, we employ our newly proposed non-linear programming framework, and demonstrate its capability in reconstructing gene trees with incomplete information in both simulated and empirical datasets. In the empirical datasets apicomplexa and lungfish, our imputation has very small normalized mean square errors, even in the extreme case where 50% of the individuals in each gene tree are missing. Data, software, and user manuals can be found at https://github.com/yasuiniko/imPhy.
Type
Article
Description
Series/Report No
Department
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
10 p.
Citation
Yasui, Niko, et al. "imPhy: Imputing phylogenetic trees with missing information using mathematical programming." IEEE/ACM transactions on computational biology and bioinformatics (2018).
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Collections