Species tree estimation is frequently based on phylogenomic approaches that use multiple genes from throughout the genome. However, for a combination of reasons (ranging from sampling biases to more biological causes, as in gene birth and loss), gene trees are often incomplete, meaning that not all species of interest have a common set of genes. Incomplete gene trees can potentially impact the accuracy of phylogenomic inference. We, for the first time, introduce the problem of imputing the quartet distribution induced by a set of incomplete gene trees, which involves adding the missing quartets back to the quartet distribution. We present Quartet based Gene tree Imputation using Deep Learning (QT-GILD), an automated and specially tailored unsupervised deep learning technique, accompanied by cues from natural language processing, which learns the quartet distribution in a given set of incomplete gene trees and generates a complete set of quartets accordingly. QT-GILD is a general-purpose technique needing no explicit modeling of the subject system or reasons for missing data or gene tree heterogeneity. Experimental studies on a collection of simulated and empirical datasets suggest that QT-GILD can effectively impute the quartet distribution, which results in a dramatic improvement in the species tree accuracy. Remarkably, QT-GILD not only imputes the missing quartets but can also account for gene tree estimation error. Therefore, QT-GILD advances the state-of-the-art in species tree estimation from gene trees in the face of missing data.
BayzidMS, WarnowT.Estimating optimal species trees from incomplete gene trees under deep coalescence. J Comput Biol, 2012;19(6):591–605; doi: 10.1089/cmb.2012.0037.
BayzidMS, WarnowT.Gene tree parsimony for incomplete gene trees: Addressing true biological loss. Algorithms Mol Biol, 2018;13(1):1–12; doi: 10.1186/s13015-017-0120-1.
6.
BurleighJG, HiluKW, SoltisDE. Inferring phylogenies with incomplete data sets: A 5-gene, 567-taxon analysis of angiosperms. BMC Evol Biol, 2009;9(1):1–11; doi: 10.1186/1471-2148-9-61.
7.
ChifmanJ, KubatkoL.Quartet from SNP data under the coalescent model. Bioinformatics, 2014;30(23):3317–3324; doi: 10.1093/bioinformatics/btu530.
8.
ChristensenS, MolloyEK, VachaspatiP, et al.Octal: Optimal completion of gene trees in polynomial time. Algorithms Mol Biol, 2018;13(1):1–18; doi: 10.1186/s13015-018-0124-5.
DegnanJH, DeGiorgioM, BryantD, et al.Properties of consensus methods for inferring species trees from gene trees. Syst Biol, 2009;58(1):35–54; doi: 10.1093/sysbio/syp008.
11.
DegnanJH, RosenbergNA. Discordance of species trees with their most likely gene trees. PLoS Genet, 2006;2(5):e68; doi: 10.1371/journal.pgen.0020068.
12.
DegnanJH, RosenbergNA. Gene tree discordance, phylogenetic inference and the multispecies coalescent. Trends Ecol Evol, 2009;26(6):332–340; doi: 10.1016/j.tree.2009.01.009.
13.
DegnanJH, SalterLA. Gene tree distributions under the coalescent process. Evolution, 2005;59(1):24–37.
14.
DrewBT, RuhfelBR, SmithSA, et al.Another look at the root of the angiosperms reveals a familiar tale. Syst Biol, 2014;63(3):368–382; doi: 10.1093/sysbio/syt108.
15.
FarahIT, IslamM, ZinatKT, et al.Species tree estimation from gene trees by minimizing deep coalescence and maximizing quartet consistency: A comparative study and the presence of pseudo species tree terraces. Syst Biol, 2021;70(6):1213–1231; doi: 10.1093/sysbio/syab026.
16.
FugledeB, TopsoeF.Jensen-shannon divergence and hilbert space embedding. In: International Symposium on Information Theory, 2004. ISIT 2004. Proceedings. IEEE, 2004; 31 pages.
17.
GoodfellowI, BengioY, CourvilleA.Deep learning. MIT Press; Cambridge, Massachusetts, 2016.
18.
GoremykinVV, NikiforovaSV, BiggsPJ, et al.The evolutionary root of flowering plants. Syst Biol, 2013;62(1):50–61; doi: 10.1093/sysbio/sys070.
19.
HeledJ, DrummondAJ. Bayesian inference of species trees from multilocus data. Mol Biol Evol, 2010;27(3):570–580; doi: 10.1093/molbev/msp274.
20.
HosnerPA, FairclothBC, GlennTC, et al.Avoiding missing data biases in phylogenomic inference: An empirical study in the landfowl (aves: Galliformes). Mol Biol Evol, 2016;33(4):1110–1125; doi: 10.1093/molbev/msv347.
21.
HudsonRR.Testing the constant-rate neutral allele model with protein sequence data. Evolution, 1983;37(1):203–217; doi: 10.1111/j.1558-5646.1983.tb05528.x.
22.
IslamM, SarkerK, DasT, et al.Stelar: A statistically consistent coalescent-based species tree estimation method by maximizing triplet consistency. BMC Genomics, 2020;21(1):1–13; doi: 10.1186/s12864-020-6519-y.
23.
KubatkoLS, CarstensBC, KnowlesLL. Stem: Species tree estimation using maximum likelihood for gene trees under coalescence. Bioinformatics, 2009;25(7):971–973; doi: 10.1093/bioinformatics/btp079.
24.
KubatkoLS, DegnanJH. Inconsistency of phylogenetic estimates from concatenated data under coalescence. Syst Biol, 2007;56(1):17–24; doi: 10.1080/10635150601146041.
25.
LargetB, KothaSK, DeweyCN, et al.BUCKy: Gene tree/species tree reconciliation with the Bayesian concordance analysis. Bioinformatics, 2010;26(22):2910–2911; doi: 10.1093/bioinformatics/btq539.
26.
LeachéAD, RannalaB.The accuracy of species tree estimation under simulation: A comparison of methods. Syst Biol, 2011;60(2):126–137; doi: 10.1093/sysbio/syq073.
27.
LemmonAR, BrownJM, Stanger-HallK, et al.The effect of ambiguous data on phylogenetic estimates obtained by maximum likelihood and bayesian inference. Syst Biol, 2009;58(1):130–145; doi: 10.1093/sysbio/syp017.
28.
LiuL.BEST: Bayesian estimation of species trees under the coalescent model. Bioinformatics, 2008;24(21):2542–2543; doi: 10.1093/bioinformatics/btn484.
29.
LiuL, YuL.Estimating species trees from unrooted gene trees. Syst Biol, 2011;60(5):661–667; doi: 10.1093/sysbio/syr027.
30.
LiuL, YuL, EdwardsSV. A maximum pseudo-likelihood approach for estimating species trees under the coalescent model. BMC Evol Biol, 2010;10:302; doi: 10.1186/1471-2148-10-302.
31.
LiuL, YuL, PearlDK, et al.Estimating species phylogenies using coalescence times among sequences. Syst Biol, 2009;58(5):468–477; doi: 10.1093/sysbio/syp031.
32.
MaddisonWP.Gene trees in species trees. Syst Biol, 1997;46(3):523–536; doi: 10.1093/sysbio/46.3.523.
33.
MahbubM, WahabZ, ReazR, et al.wQFM: Highly accurate genome-scale species tree estimation from weighted quartets. Bioinformatics, 2021;37(21):3734–3743.
34.
MahbubS, SawmyaS, SahaA, et al.QT-GILD: Quartet based gene tree imputation using deep learning improves phylogenomic analyses despite missing data. In: International Conference on Research in Computational Molecular Biology. Springer; Cham, 2022; pp. 159–176.
35.
MirarabS, BayzidMS, BoussauB, et al.Statistical binning enables an accurate coalescent-based estimation of the avian tree. Science, 2014a;346(6215):1250463; doi: 10.1126/science.1250463.
36.
MirarabS, ReazR, BayzidMS, et al.ASTRAL: Genome-scale coalescent-based species tree estimation. Bioinformatics, 2014b;30(17):i541–i548; doi: 10.1093/bioinformatics/btu462.
37.
MirarabS, WarnowT.Astral-ii: Coalescent-based species tree estimation with many hundreds of taxa and thousands of genes. Bioinformatics, 2015;31(12):i44–i52; doi: 10.1093/bioinformatics/btv234.
38.
MosselE, RochS.Incomplete lineage sorting: Consistent phylogeny estimation from multiple loci. IEEE/ACM Trans Comput Biol Bioinform, 2011;7(1):166–171; doi: 10.1109/TCBB.2008.66.
39.
NeiM.Stochastic errors in DNA evolution and molecular phylogeny. In: Evolutionary Perspectives and the New Genetics. (Gershowitz H, Rucknagel DL, Tashian RE. eds.) Alen R. Liss, New York, New York, 1986; pp. 133–147.
40.
NeiM.Molecular Evolutionary Genetics. Columbia University Press: New York: NY, USA, 1987.
41.
NuteM, ChouJ, MolloyEK, et al.The performance of coalescent-based species tree estimation methods under models of missing data. BMC Genomics, 2018;19(suppl 5):1–22; doi: 10.1186/s12864-018-4619-8.
ReazR, BayzidMS, RahmanMS. Accurate phylogenetic tree reconstruction from quartets: A heuristic approach. PLoS One,, 2014;9(8):e104008; doi: 10.1371/journal.pone.0104008.
44.
RobinsonD, FouldsL.Comparison of phylogenetic trees. Math Biosci, 1981;53:131–147; doi: 10.3390/microorganisms8010032.
45.
RochS, SteelM.Likelihood-based tree reconstruction on a concatenation of aligned sequence data sets can be statistically inconsistent. Theor Popul Biol, 2015;100C:56–62; doi: 10.1016/j.tpb.2014.12.005.
46.
RosenbergN.The probability of topological concordance of gene trees and species trees. Theor Popul Biol, 2002;61(2):225–247; doi: 10.1006/tpbi.2001.1568.
47.
SandersonMJ, McMahonMM, SteelM.Terraces in phylogenetic tree space. Science, 2011;333(6041):448–450; doi: 10.1126/science.1206357.
48.
SayyariE, MirarabS.Fast coalescent-based computation of local branch support from quartet frequencies. Mol Biol Evol, 2016;33(7):1654–1668; doi: 10.1093/molbev/msw079.
49.
SchmidtHA, StrimmerK, VingronM, et al.Tree-puzzle: Maximum likelihood phylogenetic analysis using quartets and parallel computing. Bioinformatics, 2002;18(3):502–504; doi: 10.1093/bioinformatics/18.3.502.
50.
SmithBT, HarveyMG, FairclothBC, et al.Target capture and massively parallel sequencing of ultraconserved elements for comparative studies at shallow evolutionary time scales. Syst Biol, 2013;63(1):83–95; doi: 10.1093/sysbio/syt061.
51.
SnirS, RaoS.Quartets MaxCut: A divide and conquer quartets algorithm. IEEE/ACM Trans Comput Biol Bioinform, 2010;7(4):704–718; doi: 10.1109/TCBB.2008.133.
52.
StreicherJW, SchulteJA, WiensJJ. How should genes and taxa be sampled for phylogenomic analyses with missing data? An empirical study in iguanian lizards. Syst Biol, 2016;65(1):128–145; doi: 10.1093/sysbio/syv058.
53.
StrimmerK, von HaeselerA.Quartet puzzling: A quartet maximim-likelihood method for reconstructing tree topologies. Mol Biol Evol, 1996;13(7):964–969.
54.
TajimaF.Evolutionary relationship of DNA sequences in finite populations. Genetics, 1983;105(2):437–460; doi: 10.1093/genetics/105.2.437.
55.
TakahataN.Gene geneaology in three related populations: Consistency probability between gene and population trees. Genetics, 1989;122(4):957–966; doi: 10.1093/genetics/122.4.957.
56.
UddinMR, MahbubS, RahmanMS, et al.SAINT: Self-attention augmented inception-inside-inception network improves protein secondary structure prediction. Bioinformatics, 2020;36(17):4599–4608; doi: 10.1093/bioinformatics/btaa531.
57.
VachaspatiP, WarnowT.Astrid: Accurate species trees from internode distances. BMC Genomics, 2015;16(suppl 10):S3; doi: 10.1186/1471-2164-16-S10-S3.
58.
VaswaniA, ShazeerN, ParmarN, et al.Attention is all you need. In: Advances in Neural Information Processing System. Long Beach, California, 2017, pp. 5998–6008.
59.
WickettNJ, MirarabS, NguyenN, et al.Phylotranscriptomic analysis of the origin and early diversification of land plants. Proc Natl Acad Sci U S A, 2014;111(45):E4859–E4868; doi: 10.1073/pnas.1323926111.
60.
XiZ, LiuL, DavisCC. The impact of missing data on species tree estimation. Mol Biol Evol, 2016;33(3):838–860; doi: 10.1093/molbev/msv266.
61.
XiZ, LiuL, RestJS, et al.Coalescent versus concatenation methods and the placement of amborella as sister to water lilies. Syst Biol, 2014;63(6):919–932; doi: 10.1093/sysbio/syu055.
62.
ZhangC, RabieeM, SayyariE, et al.Astral-iii: Polynomial time species tree reconstruction from partially resolved gene trees. BMC Bioinformatics, 2018;19(suppl 6):153; doi: 10.1186/s12859-018-2129-y.
63.
ZhangN, ZengL, ShanH, et al.Highly conserved low-copy nuclear genes as effective markers for phylogenetic analyses in angiosperms. New Phytol, 2012;195(4):923–937; doi: 10.1111/j.1469-8137.2012.04212.x.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
