Search

Whole-genome duplication (WGD), or polyploidization, is a major contributor to biodiversity. However, the establishment and survival of WGDs are often considered to be stochastic, since elucidating the processes of WGD establishment remains challenging. In the current study, we explored the processes leading to polyploidy establishment in snow carp (Cyprinidae: Schizothoracinae), a predominant component of the ichthyofauna of the Tibetan Plateau and its surrounding areas. Using large-scale genomic data from isoform sequencing, we analyzed ohnolog genealogies and divergence in hundreds to thousands of gene families across major snow carp lineages. Our findings demonstrated that independent autopolyploidization subsequent to speciation was prevalent, while autopolyploidization followed by speciation also occurred in the diversification of snow carp. This was further supported by matrilineal divergence and drainage evolution evidence. Contrary to the long-standing hypothesis that ancient polyploidization preceded the diversification of snow carp, we determined that polyploidy in extant snow carp was established by recurrent autopolyploidization events during the Pleistocene. These findings indicate that the diversification of extant snow carp resembles a coordinated duet: first, the uplift of the Tibetan Plateau orchestrated the biogeography and diversification of their diploid progenitors; then, the extensive Pliocene–Pleistocene climate changes acted as relay runners, further fueling diversification through recurrent autopolyploidization. Overall, this study not only reveals a hitherto unrecognized recent WGD lineage in vertebrates but also advances current understanding of WGD processes, emphasizing that WGD establishment is a nonstochastic event, emerging from numerous adaptations to environmental challenges and recurring throughout evolutionary history rather than merely in plants. [ABSTRACT FROM AUTHOR]

Abstract A terrace in a phylogenetic tree space is a region where all trees contain the same set of subtrees, due to certain patterns of missing data among the taxa sampled, resulting in an identical optimality score for a given data set. This was first investigated in the context of phylogenetic tree estimation from sequence alignments using maximum likelihood (ML) and maximum parsimony (MP). It was later extended to the species tree inference problem from a collection of gene trees, where a set of equally optimal species trees was referred to as a “pseudo” species tree terrace which does not consider the topological proximity of the trees in terms of the induced subtrees resulting from certain patterns of missing data. In this study, we mathematically characterize species tree terraces and investigate the mathematical properties and conditions that lead multiple species trees to induce/display an identical set of locus-specific subtrees owing to missing data. We report that species tree terraces are agnostic to gene tree heterogeneity. Therefore, we introduce and characterize a special type of gene tree topology-aware terrace which we call “peak terrace”. Moreover, we empirically investigated various challenges and opportunities related to species tree terraces through extensive empirical studies using simulated and real biological data. We demonstrate the prevalence of species tree terraces and the resulting ambiguity created for tree search algorithms. Remarkably, our findings indicate that the identification of terraces could potentially lead to advances that enhance the accuracy of summary methods and provide reasonably accurate branch support.

We consider the reconciliation problem, in which the task is to find a mapping of a gene tree into a species tree. In this paper we present a method, where for a given choice of parameters, we are able to compute the likelihood for alternative reconciliations. We describe a Markovian binary tree (MBT) model for the evolution of species trees, a quasi-birth-and-death (QBD) model for the evolution of gene trees, and provide a recursive algorithm to compute the likelihood of a given reconciliation between a species tree and a gene tree. We derive our results using the theory of matrix-analytic methods, prove them using rigorous mathematics together with decomposition of sample path arguments, and describe algorithms for the computation of a range of useful metrics. We illustrate the theory with examples and provide the physical interpretations of the discussed quantities, with a focus on the practical applications of the theory to incomplete data. [ABSTRACT FROM AUTHOR]

Studies of evolution and biodiversity require solid understanding of species systematics revealed by molecular phylogeny using multilocus genomic data. Multilocus analyses, nevertheless, remain difficult in non-model taxa due to limited access to samples and molecular resources. To help overcome this limitation, ultra-conserved elements (UCEs) have been developed to generate large nuclear datasets and build more robust species phylogenies. Recently, MitoFinder pipeline was developed to further extract mitochondrial genes from the off-target sequences in UCE libraries to allow mito-nuclear comparison and increase the mitochondrial genomic database. Here we applied MitoFinder to published UCE datasets of serotine bats (genus Eptesicus) and focused on E. (Histiotus) whose evolutionary history is poorly understood. Our results showed extensive mito-nuclear discordances in the divergence of major clades in Eptesicus and within E. (Histiotus), indicating potential incomplete lineage sorting and historical mitochondrial introgression within and across subgenera. Moreover, we collected several new samples of E. (Histiotus), including the first molecular data of the recently described E. (H) diaphanopterus, and combined available published sequences to generate the most taxa-complete mitochondrial phylogeny of E. (Histiotus) bats. Results supported the early divergence of E. (H.) magellanicus and the species status of E. (H.) diaphanopterus. In addition, we found strong evidence of cryptic diversity, with potentially new taxa in Peru, Uruguay, and Brazil, which needs to be evaluated in future studies using complementary data. Our study enriched the sequence database of serotine bats and shed light on the hidden diversity and complex evolutionary history of E. (Histiotus). [ABSTRACT FROM AUTHOR]

We developed phyloBARCODER (https://github.com/jun-inoue/phyloBARCODER), a new web tool that can identify short DNA sequences to the species level using metabarcoding. phyloBARCODER estimates phylogenetic trees based on the uploaded anonymous DNA sequences and reference sequences from databases. Without such phylogenetic contexts, alternative, similarity-based methods independently identify species names and anonymous sequences of the same group by pairwise comparisons between queries and database sequences, with the caveat that they must match exactly or very closely. By putting metabarcoding sequences into a phylogenetic context, phyloBARCODER accurately identifies (i) species or classification of query sequences and (ii) anonymous sequences associated with the same species or even with populations of query sequences, with clear and accurate explanations. Version 1 of phyloBARCODER stores a database comprising all eukaryotic mitochondrial gene sequences. Moreover, by uploading their own databases, phyloBARCODER users can conduct species identification specialized for sequences obtained from a local geographic region or those of nonmitochondrial genes, e.g. ITS or rbcL. [ABSTRACT FROM AUTHOR]

The Black-throated Gray Warbler (Setophaga nigrescens) is a migratory songbird with a widespread and continuous distribution in the North American West. Previously published morphological data support the designation of 2 putative subspecies based on subtle differences in plumage and song; however, whether these patterns are clinal or discrete has yet to be determined. Furthermore, given that patterns of morphological variation occur across multiple distinct habitats and geographical boundaries, underlying population genetic structure may be present. To investigate this question and explore the evolutionary history of S. nigrescens, we conducted the first range-wide phylogeographic analysis of this species using genetic (mitochondrial DNA [mtDNA], ND2 gene sequences), morphological (body measurements), and environmental (niche modeling) data. Overall, our results identified 2 major mtDNA clades. One clade occurs east of the Cascade-Sierra ranges throughout the southwestern, Great Basin, and Rocky Mountain regions in North America (Interior clade), while a second widespread clade is comprised of birds that span the Pacific Northwest, and also across the Great Basin and southwest into the Rocky Mountains (Coastal clade). Divergence time estimates suggest a Pleistocene epoch vicariance event. Environmental niche models predict habitat modification and fragmentation from glacial–interglacial cycles, which were frequent over the Pleistocene. Range expansion northwards following the Last Glacial Maximum was identified from neutrality tests and shifts in suitable habitat from the Mid-Holocene to present-day conditions, where both clades are likely experiencing secondary contact. We found support for nonequivalent environmental niches among both clades based on a spatial analysis of environmental variables, with the Coastal clade showing greater tolerance to both temperate and xeric climatic conditions across the North American West; however, the environmental space occupied by both clades was more similar to each other than expected by chance. High levels of geographic overlap and a lack of discrete patterns in morphology suggest few contemporary reproductive barriers to gene flow. [ABSTRACT FROM AUTHOR]

Abstract We present a novel problem, called MetaEC, which aims to infer gene-species assignments in a collection of partially leaf-labeled gene trees labels by minimizing the size of duplication episode clustering (EC). This problem is particularly relevant in metagenomics, where incomplete data often poses a challenge in the accurate reconstruction of gene histories. To solve MetaEC, we propose a polynomial time dynamic programming (DP) formulation that verifies the existence of a set of duplication episodes from a predefined set of episode candidates. In addition, we design a method to infer distributions of gene-species mappings. We then demonstrate how to use DP to design an algorithm that solves MetaEC. Although the algorithm is exponential in the worst case, we introduce a heuristic modification of the algorithm that provides a solution with the knowledge that it is exact. To evaluate our method, we perform two computational experiments on simulated and empirical data containing whole genome duplication events, showing that our algorithm is able to accurately infer the corresponding events.

Reticulations in a phylogenetic network represent processes such as gene flow, admixture, recombination and hybrid speciation. Extending definitions from the tree setting, an anomalous network is one in which some unrooted tree topology displayed in the network appears in gene trees with a lower frequency than a tree not displayed in the network. We investigate anomalous networks under the Network Multispecies Coalescent Model with possible correlated inheritance at reticulations. Focusing on subsets of 4 taxa, we describe a new algorithm to calculate quartet concordance factors on networks of any level, faster than previous algorithms because of its focus on 4 taxa. We then study topological properties required for a 4-taxon network to be anomalous, uncovering the key role of 3 2 -cycles: cycles of 3 edges parent to a sister group of 2 taxa. Under the model of common inheritance, that is, when each gene tree coalesces within a species tree displayed in the network, we prove that 4-taxon networks are never anomalous. Under independent and various levels of correlated inheritance, we use simulations under realistic parameters to quantify the prevalence of anomalous 4-taxon networks, finding that truly anomalous networks are rare. At the same time, however, we find a significant fraction of networks close enough to the anomaly zone to appear anomalous, when considering the quartet concordance factors observed from a few hundred genes. These apparent anomalies may challenge network inference methods. [ABSTRACT FROM AUTHOR]

We present a novel problem, called MetaEC, which aims to infer gene-species assignments in a collection of partially leaf-labeled gene trees labels by minimizing the size of duplication episode clustering (EC). This problem is particularly relevant in metagenomics, where incomplete data often poses a challenge in the accurate reconstruction of gene histories. To solve MetaEC, we propose a polynomial time dynamic programming (DP) formulation that verifies the existence of a set of duplication episodes from a predefined set of episode candidates. In addition, we design a method to infer distributions of gene-species mappings. We then demonstrate how to use DP to design an algorithm that solves MetaEC. Although the algorithm is exponential in the worst case, we introduce a heuristic modification of the algorithm that provides a solution with the knowledge that it is exact. To evaluate our method, we perform two computational experiments on simulated and empirical data containing whole genome duplication events, showing that our algorithm is able to accurately infer the corresponding events. [ABSTRACT FROM AUTHOR]

Introduction: The phylogenetic relationships within Pancrustacea (including Crustacea and Hexapoda) remain elusive despite analyses using various molecular data sets and analytical approaches over the past decade. The relationship between the major lineages of Allotriocarida, which includes Hexapoda, the most species-rich animal taxon, is particularly recalcitrant. Methods: To investigate and resolve the root of phylogenetic ambiguity in Pancrustacea, we re-evaluated the evolutionary relationships of major pancrustacean clades using a phylogenetically informed orthology approach and assessed the effect of systematic errors, with a major focus on long branch attraction (LBA) and incomplete lineage sorting (ILS). A data set comprising 1086 orthologs from 106 species representing all major extant classes of pancrustaceans was assembled and used in gene tree and species tree construction after various filtering processes. Results and discussion: Regardless of the filtering criteria and phylogenetic analyses, the resulting trees consistently supported (1) a sister relationship of Remipedia and Hexapoda (hence rejecting the monophyly of Xenocarida, i.e. Remipedia + Cephalocarida), and (2) refuted the monophyly of Multicrustacea, as Copepoda is either sister to or nested within Allotriocarida. Examination of gene trees reveals that the grouping of Multicrustacea and Xenocarida in previous phylogenetic studies may represent LBA artefacts. Phylogenetic signal analyses suggest a low resolution and an incidence of strong conflicting signals at the deep splits. Further analyses indicate a partial contribution of incomplete lineage sorting (ILS) to the contradictory signal in the allotriocaridan phylogeny, leading to limited support for any potential relationships between Branchiopoda, Cephalocarida and Copepoda. This study suggests the need for further examination of other potential sources of signal discordance, such as introgression and gene tree estimation error to fully understand the evolutionary history of Pancrustacea. [ABSTRACT FROM AUTHOR]

Abstract Background Evolutionary scenarios describing the evolution of a family of genes within a collection of species comprise the mapping of the vertices of a gene tree T to vertices and edges of a species tree S. The relative timing of the last common ancestors of two extant genes (leaves of T) and the last common ancestors of the two species (leaves of S) in which they reside is indicative of horizontal gene transfers (HGT) and ancient duplications. Orthologous gene pairs, on the other hand, require that their last common ancestors coincides with a corresponding speciation event. The relative timing information of gene and species divergences is captured by three colored graphs that have the extant genes as vertices and the species in which the genes are found as vertex colors: the equal-divergence-time (EDT) graph, the later-divergence-time (LDT) graph and the prior-divergence-time (PDT) graph, which together form an edge partition of the complete graph. Results Here we give a complete characterization in terms of informative and forbidden triples that can be read off the three graphs and provide a polynomial time algorithm for constructing an evolutionary scenario that explains the graphs, provided such a scenario exists. While both LDT and PDT graphs are cographs, this is not true for the EDT graph in general. We show that every EDT graph is perfect. While the information about LDT and PDT graphs is necessary to recognize EDT graphs in polynomial-time for general scenarios, this extra information can be dropped in the HGT-free case. However, recognition of EDT graphs without knowledge of putative LDT and PDT graphs is NP-complete for general scenarios. In contrast, PDT graphs can be recognized in polynomial-time. We finally connect the EDT graph to the alternative definitions of orthology that have been proposed for scenarios with horizontal gene transfer. With one exception, the corresponding graphs are shown to be colored cographs.

Genes are often selected for molecular taxonomy citing their agreement to taxonomically derived species trees. These results are then used to define and edit existing taxonomic hierarchies of species. We counter the validity of this practice experimentally using mitochondrial genes routinely employed for the purpose. We constructed trees from complete mitochondrial DNA sequence (except D-loop) and its thirteen protein-coding genes namely nd1, nd2, nd3, nd4, nd4L, nd5, nd6, atp6, atp8, COI, COII, COIII, and cytB of 255 species of Cypriniformes fish using the maximum likelihood and Bayesian methods. While nd4, nd5, COI, COII, COIII, and cytB formed trees at par with the species tree, no gene produced complete concurrence. Similarly, while few genes formed similar branching patterns at family (COI and COIII) or broad group (nd1, nd2, and nd3; nd5 and COII) levels, no two gene trees fully agreed with each other. Tajima's D estimates of all studied genes indicated non-random evolution, violating the basic assumption of molecular phylogenetics. Bootstrap or Posterior probability values were also poor for several taxa indicating low robustness. Our findings reiterate that tree concurrence noted in studies involving smaller sample sizes is not a reflection of the evolutionary signature of the species.

Background: Evolutionary scenarios describing the evolution of a family of genes within a collection of species comprise the mapping of the vertices of a gene tree T to vertices and edges of a species tree S. The relative timing of the last common ancestors of two extant genes (leaves of T) and the last common ancestors of the two species (leaves of S) in which they reside is indicative of horizontal gene transfers (HGT) and ancient duplications. Orthologous gene pairs, on the other hand, require that their last common ancestors coincides with a corresponding speciation event. The relative timing information of gene and species divergences is captured by three colored graphs that have the extant genes as vertices and the species in which the genes are found as vertex colors: the equal-divergence-time (EDT) graph, the later-divergence-time (LDT) graph and the prior-divergence-time (PDT) graph, which together form an edge partition of the complete graph. Results: Here we give a complete characterization in terms of informative and forbidden triples that can be read off the three graphs and provide a polynomial time algorithm for constructing an evolutionary scenario that explains the graphs, provided such a scenario exists. While both LDT and PDT graphs are cographs, this is not true for the EDT graph in general. We show that every EDT graph is perfect. While the information about LDT and PDT graphs is necessary to recognize EDT graphs in polynomial-time for general scenarios, this extra information can be dropped in the HGT-free case. However, recognition of EDT graphs without knowledge of putative LDT and PDT graphs is NP-complete for general scenarios. In contrast, PDT graphs can be recognized in polynomial-time. We finally connect the EDT graph to the alternative definitions of orthology that have been proposed for scenarios with horizontal gene transfer. With one exception, the corresponding graphs are shown to be colored cographs. [ABSTRACT FROM AUTHOR]

In phylogenomics, incongruences between gene trees, resulting from both artifactual and biological reasons, can decrease the signal-to-noise ratio and complicate species tree inference. The amount of data handled today in classical phylogenomic analyses precludes manual error detection and removal. However, a simple and efficient way to automate the identification of outliers from a collection of gene trees is still missing. Here, we present PhylteR, a method that allows rapid and accurate detection of outlier sequences in phylogenomic datasets, i.e. species from individual gene trees that do not follow the general trend. PhylteR relies on DISTATIS, an extension of multidimensional scaling to 3 dimensions to compare multiple distance matrices at once. In PhylteR, these distance matrices extracted from individual gene phylogenies represent evolutionary distances between species according to each gene. On simulated datasets, we show that PhylteR identifies outliers with more sensitivity and precision than a comparable existing method. We also show that PhylteR is not sensitive to ILS-induced incongruences, which is a desirable feature. On a biological dataset of 14,463 genes for 53 species previously assembled for Carnivora phylogenomics, we show (i) that PhylteR identifies as outliers sequences that can be considered as such by other means, and (ii) that the removal of these sequences improves the concordance between the gene trees and the species tree. Thanks to the generation of numerous graphical outputs, PhylteR also allows for the rapid and easy visual characterization of the dataset at hand, thus aiding in the precise identification of errors. PhylteR is distributed as an R package on CRAN and as containerized versions (docker and singularity). [ABSTRACT FROM AUTHOR]

IntroductionThe phylogenetic relationships within Pancrustacea (including Crustacea and Hexapoda) remain elusive despite analyses using various molecular data sets and analytical approaches over the past decade. The relationship between the major lineages of Allotriocarida, which includes Hexapoda, the most species-rich animal taxon, is particularly recalcitrant.MethodsTo investigate and resolve the root of phylogenetic ambiguity in Pancrustacea, we re-evaluated the evolutionary relationships of major pancrustacean clades using a phylogenetically informed orthology approach and assessed the effect of systematic errors, with a major focus on long branch attraction (LBA) and incomplete lineage sorting (ILS). A data set comprising 1086 orthologs from 106 species representing all major extant classes of pancrustaceans was assembled and used in gene tree and species tree construction after various filtering processes.Results and discussionRegardless of the filtering criteria and phylogenetic analyses, the resulting trees consistently supported (1) a sister relationship of Remipedia and Hexapoda (hence rejecting the monophyly of Xenocarida, i.e. Remipedia + Cephalocarida), and (2) refuted the monophyly of Multicrustacea, as Copepoda is either sister to or nested within Allotriocarida. Examination of gene trees reveals that the grouping of Multicrustacea and Xenocarida in previous phylogenetic studies may represent LBA artefacts. Phylogenetic signal analyses suggest a low resolution and an incidence of strong conflicting signals at the deep splits. Further analyses indicate a partial contribution of incomplete lineage sorting (ILS) to the contradictory signal in the allotriocaridan phylogeny, leading to limited support for any potential relationships between Branchiopoda, Cephalocarida and Copepoda. This study suggests the need for further examination of other potential sources of signal discordance, such as introgression and gene tree estimation error to fully understand the evolutionary history of Pancrustacea.

We consider the evolution of phylogenetic gene trees along phylogenetic species networks, according to the network multispecies coalescent process, and introduce a new network coalescent model with correlated inheritance of gene flow. This model generalizes two traditional versions of the network coalescent: with independent or common inheritance. At each reticulation, multiple lineages of a given locus are inherited from parental populations chosen at random, either independently across lineages or with positive correlation according to a Dirichlet process. This process may account for locus-specific probabilities of inheritance, for example. We implemented the simulation of gene trees under these network coalescent models in the Julia package PhyloCoalSimulations, which depends on PhyloNetworks and its powerful network manipulation tools. Input species phylogenies can be read in extended Newick format, either in numbers of generations or in coalescent units. Simulated gene trees can be written in Newick format, and in a way that preserves information about their embedding within the species network. This embedding can be used for downstream purposes, such as to simulate species-specific processes like rate variation across species, or for other scenarios as illustrated in this note. This package should be useful for simulation studies and simulation-based inference methods. The software is available open source with documentation and a tutorial at https://github.com/cecileane/PhyloCoalSimulations.jl. [ABSTRACT FROM AUTHOR]

Palaeognathae consists of five groups of extant species: flighted tinamous (1) and four flightless groups: kiwi (2), cassowaries and emu (3), rheas (4), and ostriches (5). Molecular studies supported the groupings of extinct moas with tinamous and elephant birds with kiwi as well as ostriches as the group that diverged first among the five groups. However, phylogenetic relationships among the five groups are still controversial. Previous studies showed extensive heterogeneity in estimated gene tree topologies from conserved nonexonic elements, introns, and ultraconserved elements. Using the noncoding loci together with protein-coding loci, this study investigated the factors that affected gene tree estimation error and the relationships among the five groups. Using closely related ostrich rather than distantly related chicken as the outgroup, concatenated and gene tree–based approaches supported rheas as the group that diverged first among groups (1)–(4). Whereas gene tree estimation error increased using loci with low sequence divergence and short length, topological bias in estimated trees occurred using loci with high sequence divergence and/or nucleotide composition bias and heterogeneity, which more occurred in trees estimated from coding loci than noncoding loci. Regarding the relationships of (1)–(4), the site patterns by parsimony criterion appeared less susceptible to the bias than tree construction assuming stationary time-homogeneous model and suggested the clustering of kiwi and cassowaries and emu the most likely with ∼40% support rather than the clustering of kiwi and rheas and that of kiwi and tinamous with 30% support each. [ABSTRACT FROM AUTHOR]

The nested Kingman coalescent describes the ancestral tree of a populationundergoing neutral evolution at the level of individuals and at the level ofspecies, simultaneously. We study the speed at which the number of lineagesdescends from infinity in this hierarchical coalescent process and prove theexistence of an early-time phase during which the number of lineages at time$t$ decays as $ 2\gamma/ct^2$, where $c$ is the ratio of the coalescence ratesat the individual and species levels, and the constant $\gamma\approx 3.45$ isderived from a recursive distributional equation for the number of lineagescontained within a species at a typical time.

We sequenced the mitochondrial ND2 gene for 290 Bushtits (Psaltriparus minimus) sampled from northern Washington to Guatemala. Phylogenetic analysis sorted specimens into 2 main lineages residing either west (coastal) or east (inland) of the Sierra Nevada and Cascades. These lineages are separated by 3.5% sequence divergence and correspond with the distributions of 2 long-recognized phenotype groupings (brown-capped and plumbeous, respectively). Three additional monophyletic geographically structured lineages were identified. Birds from southmost Baja California (Sierra de la Laguna) segregate from other coastal samples whereas the inland lineage includes additional lineages occurring in southeastern Mexico (Morelos, Puebla, Guerrero, and Oaxaca) plus Guatemala, and southwestern Mexico (Michoacán). Examination of museum specimens revealed that a black-eared phenotype occurs sporadically in the interior lineage in southern U.S. and northern Mexico, increasing in frequency to the south, corresponding roughly with these southern Mexican mtDNA lineages. Degree of sequence divergence between the 2 main lineages suggests a relatively early divergence, and ample time for 2-way introgression to occur. However, only 1 of our sampling localities (Lake Co., Oregon; n = 4) was mixed for coastal (n = 1) and interior (n = 3) lineages suggesting the possibility of reproductive isolation between the 2 main lineages. Secuenciamos el gen mitocondrial ND2 de 290 mitos colectados desde el norte de Washington hasta Guatemala. Los análisis filogenéticos clasificaron a los especímenes en 2 linajes principales que residían ya sea en al oeste (costero) o al este (interior) de la Sierra Nevada y Cascades. Estos linajes se separan por una divergencia de secuencias de 3.5% y corresponden a distribuciones de 2 agrupamientos fenotípicos reconocidos desde hace mucho tiempo (respectivamente capucha marrón y plomizo). Se reconocieron tres linajes adicionales monofiléticos estructurados geográficamente. Aves de la parte más sureña de Baja California (Sierra de la Laguna) se segregan de otras muestras costeras mientras que linajes del interior incluyen otros linajes que se encuentran en el sudeste mexicano (Morelos, Puebla, Guerrero y Oaxaca), sumado a Guatemala y al sudoeste mexicano (Michoacán). La examinación de especímenes de museo reveló que un fenotipo de oreja negra se encuentra esporádicamente en el linaje interior en el sudeste de Estados Unidos y norte de México, que aumenta su frecuencia hacia el sur y corresponde en general con linajes mtADN del sudeste mexicano. El grado de divergencia de secuencias entre los 2 linajes principales sugiere una divergencia relativamente temprana y un tiempo grande para que ocurriera una introgresión de 2 vías. Sin embargo, solo una de las localidades de muestreo (Lake Co., Oregon, n = 4) presentaba una mezcla de linajes costero (n = 1) e interior (n = 3), sugiriendo la posibilidad de aislamiento reproductivo entre los 2 linajes principales. Palabras clave: ADN mitocondrial, árbol genético, divergencia de linaje, filogeografía, modelos de nicho. [ABSTRACT FROM AUTHOR]

Estimating species trees from multiple genes is complicated and challenging due to gene tree-species tree discordance. One of the basic approaches to understanding differences between gene trees and species trees is gene duplication and loss events. Minimize Gene Duplication and Loss (MGDL) is a popular technique for inferring species trees from gene trees when the gene trees are discordant due to gene duplications and losses. Previously, exact algorithms for estimating species trees from rooted, binary trees under MGDL were proposed. However, gene trees are usually estimated using time-reversible mutation models, which result in unrooted trees. In this article, we propose a dynamic programming (DP) algorithm that can be used for an exact but exponential time solution for the case when gene trees are not rooted. We also show that a constrained version of this problem can be solved by this DP algorithm in time that is polynomial in the number of gene trees and taxa. We have proved important structural properties that allow us to extend the algorithms for rooted gene trees to unrooted gene trees. We propose a linear time algorithm for finding the optimal rooted version of an unrooted gene tree given a rooted species tree so that the duplication and loss cost is minimized. Moreover, we prove that the optimal rooting under MGDL is also optimal under the MDC (minimize deep coalescence) criterion. The proposed methods can be applied to both orthologous genes and gene families that by definition include both paralogs and orthologs. Therefore, we hope that these techniques will be useful for estimating species trees from genes sampled throughout the whole genome. [ABSTRACT FROM AUTHOR]

Abstract Background Phylogenetic networks are mathematical models of evolutionary processes involving reticulate events such as hybridization, recombination, or horizontal gene transfer. One of the crucial notions in phylogenetic network modelling is displayed tree, which is obtained from a network by removing a set of reticulation edges. Displayed trees may represent an evolutionary history of a gene family if the evolution is shaped by reticulation events. Results We address the problem of inferring an optimal tree displayed by a network, given a gene tree G and a tree-child network N, under the deep coalescence and duplication costs. We propose an O(mn)-time dynamic programming algorithm (DP) to compute a lower bound of the optimal displayed tree cost, where m and n are the sizes of G and N, respectively. In addition, our algorithm can verify whether the solution is exact. Moreover, it provides a set of reticulation edges corresponding to the obtained cost. If the cost is exact, the set induces an optimal displayed tree. Otherwise, the set contains pairs of conflicting edges, i.e., edges sharing a reticulation node. Next, we show a conflict resolution algorithm that requires $$2^{r+1}-1$$ 2 r + 1 - 1 invocations of DP in the worst case, where r is the number of reticulations. We propose a similar $$O(2^kmn)$$ O ( 2 k m n ) -time algorithm for level-k tree-child networks and a branch and bound solution to compute lower and upper bounds of optimal costs. We also extend the algorithms to a broader class of phylogenetic networks. Based on simulated data, the average runtime is $$\Theta (2^{{0.543}k}mn)$$ Θ ( 2 0.543 k m n ) under the deep-coalescence cost and $$\Theta (2^{{0.355}k}mn)$$ Θ ( 2 0.355 k m n ) under the duplication cost. Conclusions Despite exponential complexity in the worst case, our algorithms perform significantly well on empirical and simulated datasets, due to the strategy of resolving internal dissimilarities between gene trees and networks. Therefore, the algorithms are efficient alternatives to enumeration strategies commonly proposed in the literature and enable analyses of complex networks with dozens of reticulations.

It is common in phylogenetics to have some, perhaps partial, information about the overall evolutionary tree of a group of organisms and wish to find an evolutionary tree of a specific gene for those organisms. There may not be enough information in the gene sequences alone to accurately reconstruct the correct "gene tree." Although the gene tree may deviate from the "species tree" due to a variety of genetic processes, in the absence of evidence to the contrary it is parsimonious to assume that they agree. A common statistical approach in these situations is to develop a likelihood penalty to incorporate such additional information. Recent studies using simulation and empirical data suggest that a likelihood penalty quantifying concordance with a species tree can significantly improve the accuracy of gene tree reconstruction compared to using sequence data alone. However, the consistency of such an approach has not yet been established, nor have convergence rates been bounded. Because phylogenetics is a non-standard inference problem, the standard theory does not apply. In this paper, we propose a penalized maximum likelihood estimator for gene tree reconstruction, where the penalty is the square of the Billera-Holmes-Vogtmann geodesic distance from the gene tree to the species tree. We prove that this method is consistent, and derive its convergence rate for estimating the discrete gene tree structure and continuous edge lengths (representing the amount of evolution that has occurred on that branch) simultaneously. We find that the regularized estimator is "adaptive fast converging," meaning that it can reconstruct all edges of length greater than any given threshold from gene sequences of polynomial length. Our method does not require the species tree to be known exactly; in fact, our asymptotic theory holds for any such guide tree.

Phylogenetic diversity indices such as the Fair Proportion (FP) index are frequently discussed as prioritization criteria in biodiversity conservation. They rank species according to their contribution to overall diversity by taking into account the unique and shared evolutionary history of each species as indicated by its placement in an underlying phylogenetic tree. Traditionally, phylogenetic trees were inferred from single genes and the resulting gene trees were assumed to be a valid estimate for the species tree, i.e., the “true” evolutionary history of the species under consideration. However, nowadays it is common to sequence whole genomes of hundreds or thousands of genes, and it is often the case that conflicting genealogical histories exist in different genes throughout the genome, resulting in discordance between individual gene trees and the species tree. Here, we analyze the effects of gene and species tree discordance on prioritization decisions based on the FP index. In particular, we consider the ranking order of taxa induced by (i) The FP index on a species tree, and (ii) The expected FP index across all gene tree histories associated with the species tree. On the one hand, we show that for particular tree shapes, the two rankings always coincide. On the other hand, we show that for all leaf numbers greater than or equal to five, there exist species trees for which the two rankings differ. Finally, we illustrate the variability in the rankings obtained from the FP index across different gene tree and species tree estimates for an empirical multilocus mammal data set. [ABSTRACT FROM AUTHOR]

A multi-labeled tree (or MUL-tree) is a rooted tree in which every leaf is labeled by an element from some set X , but in which more than one leaf may be labeled by the same element of X. MUL-trees have applications in many fields. In phylogenetics, they can represent the evolution of gene families, where genes are represented by the species they belong to, the non-uniqueness of leaf-labels coming from the fact that a given genome may contain many paralogous genes (genes related through duplication). In this paper, we consider two problems related to the leaf-pruning (leaf removal) of MUL-trees leading to single-labeled trees. First, given a set of MUL-trees, the MUL-tree Set Pruning for Consistency (MULSETPC) Problem asks for a pruning of each tree leading to a set of consistent trees, i.e. a collection of label-isomorphic single-labeled trees. Second, processing one tree at a time, the MUL-tree Pruning for Reconciliation (MULPR) Problem asks for a pruning that minimizes a "reconciliation" cost, i.e. an evolutionary cost of the gene family through duplication, given a known species tree. We show that MULSETPC is NP-hard and that MULPR is W[2]-hard when parameterized by the duplication cost, NP-hard when the number of occurrences of each label in a MUL-tree is bounded by two and that the optimization version of MULPR is hard to approximate within factor (1 − o (1)) ln ⁡ | X |. We then develop a polynomial-time heuristic for MULPR and show its accuracy by comparing it to a brute-force exact method on a set of gene trees from the Ensembl Genome Browser. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Regional genetic differentiation of mitochondrial lineages occurs in migratory species with natal philopatry such as sea turtles. However, early juvenile dispersal represents a key opportunity for gene flow and colonization of new regions through founder events, making it an important yet under‐studied life stage. To assess connectivity among sea turtle life stages and ocean basins, we sequenced mitochondrial DNA (mtDNA) fragments from 35 juveniles sampled in the Gulf of Mexico from the rarely observed dispersal stage across three species: green turtles (Chelonia mydas; n = 30), hawksbills (Eretmochelys imbricata; n = 3), and loggerheads (Caretta caretta; n = 2). We estimated green turtle rookery contributions using a many‐to‐many Bayesian mixed stock analysis that incorporated dispersal probabilities based on rookery size and transport via ocean currents. We assembled a gene tree including 709 distinct mtDNA control region haplotypes from the literature for all seven extant sea turtle species to assess gaps in life‐stage data across ocean basins, as well as contextualize the lineages we sampled from dispersing juveniles. Our results indicate a high likelihood that green turtles sampled in the Gulf of Mexico originated from rookeries along the coast of Mexico, with smaller contributions from Costa Rica and Suriname. The gene tree analysis yielded species‐level relationships consistent with those presented previously, while intra‐species relationships between lineages and ocean basins differed, particularly within loggerhead and green turtle clades. Our results highlight the lack of genetic data from juvenile sea turtles, especially the early dispersal stage, and the potential for these data to answer broader questions of connectivity and diversification across species and lineages. [ABSTRACT FROM AUTHOR]

The millions of herbarium specimens in collections around the world provide historical resources for phylogenomics and evolutionary studies. Many rare and endangered species exist only as historical specimens. Here, we report a case study of the monotypic Pseudobartsia yunnanensis D. Y. Hong (=Pseudobartsia glandulosa[Bentham] W. B. Yu & D. Z. Li: Orobanchaceae) known from a single Chinese collection taken in 1940. We obtained genomic data of Pseudobartsia glandulosa using high‐throughput short‐read sequencing, and then assembled a complete chloroplast genome and nuclear ribosome DNA region in this study. We found that the newly assembled three plastid DNA regions (atpB‐rbcL, rpl16, and trnS‐G) and nuclear ribosomal internal transcribed spacer (nrITS) of Pseudobartsia glandulosa were more than 99.98% similar to published sequences obtained by target sequencing. Phylogenies of Orobanchaceae using 30 plastomes (including 10 new plastomes), using both supermatrix and multispecies coalescent approaches following a novel plastid phylogenomic workflow, recovered seven recognized tribes and two unranked groups, both of which were proposed as new tribes, that is, Brandisieae and Pterygielleae. Within Pterygielleae, all analyses strongly supported Xizangia D. Y. Hong as the first diverging genus, with Pseudobartsia D. Y. Hong as sister to Pterygiella Oliver + Phtheirospermum Bunge (excluding Phtheirospermum japonicum [Thunberg] Kanitz); this supports reinstatement of Pseudobartsia and Xizangia. Although elements of Buchnereae‐Cymbarieae‐Orobancheae and Brandisieae‐Pterygielleae‐Rhinantheae showed incongruence among gene trees, the topology of the supermatrix tree was congruent with the majority of gene trees and functional‐group trees. Therefore, most plastid genes are evolving as a linkage group, allowing the supermatrix tree approach to yield internally consistent phylogenies for Orobanchaceae. [ABSTRACT FROM AUTHOR]

AsymmeTree is a flexible and easy-to-use Python package for the simulation of gene family histories. It simulates species trees and considers the joint action of gene duplication, loss, conversion, and horizontal transfer to evolve gene families along the species tree. To generate realistic scenarios, evolution rate heterogeneity from various sources is modeled. Finally, nucleotide or amino acid sequences (optionally with indels, among-site rate heterogeneity, and invariant sites) can be simulated along the gene phylogenies. For all steps, users can choose from a spectrum of alternative methods and parameters. These choices include most options that are commonly used in comparable tools but also some that are usually not found, such as the innovation model for species evolution. While output files for each individual step can be generated, AsymmeTree is primarily intended to be integrated in complex Python pipelines designed to assess the performance of data analysis methods. It allows the user to interact with, analyze, and possibly manipulate the simulated scenarios. AsymmeTree is freely available on GitHub. [ABSTRACT FROM AUTHOR]

Abstract Background Phylogenies are a key part of research in many areas of biology. Tools that automate some parts of the process of phylogenetic reconstruction, mainly molecular character matrix assembly, have been developed for the advantage of both specialists in the field of phylogenetics and non-specialists. However, interpretation of results, comparison with previously available phylogenetic hypotheses, and selection of one phylogeny for downstream analyses and discussion still impose difficulties to one that is not a specialist either on phylogenetic methods or on a particular group of study. Results Physcraper is a command-line Python program that automates the update of published phylogenies by adding public DNA sequences to underlying alignments of previously published phylogenies. It also provides a framework for straightforward comparison of published phylogenies with their updated versions, by leveraging upon tools from the Open Tree of Life project to link taxonomic information across databases. The program can be used by the nonspecialist, as a tool to generate phylogenetic hypotheses based on publicly available expert phylogenetic knowledge. Phylogeneticists and taxonomic group specialists will find it useful as a tool to facilitate molecular dataset gathering and comparison of alternative phylogenetic hypotheses (topologies). Conclusion The Physcraper workflow showcases the benefits of doing open science for phylogenetics, encouraging researchers to strive for better scientific sharing practices. Physcraper can be used with any OS and is released under an open-source license. Detailed instructions for installation and usage are available at https://physcraper.readthedocs.io.

Monophyly is a feature of a set of genetic lineages in which every lineage in the set is more closely related to all other members of the set than it is to any lineage outside the set. Multiple sets of lineages that are separately monophyletic are said to be reciprocally monophyletic, or jointly monophyletic. The prevalence of reciprocal monophyly, or joint monophyly (JM), has been used to evaluate phylogenetic and phylogeographic hypotheses, as well as to delimit species. These applications often make use of a probability of JM under models of gene lineage evolution. Studies in coalescent theory have computed this JM probability for small numbers of separate groups in arbitrary species trees and for arbitrary numbers of separate groups in trivial species trees. In this study, generalizing existing results on monophyly probabilities under the multispecies coalescent, we derive the probability of JM for arbitrary numbers of separate groups in arbitrary species trees. We illustrate how our result collapses to previously examined cases. We also study the effect of tree height, sample size, and number of species on the probability of JM. We obtain relatively simple lower and upper bounds on the JM probability. Our results expand the scope of JM calculations beyond small numbers of species, subsuming past formulas that have been used in simpler cases. [ABSTRACT FROM AUTHOR]

Retroelement insertions (RIs) are low-homoplasy characters that are ideal data for addressing deep evolutionary radiations, where gene tree reconstruction errors can severely hinder phylogenetic inference with DNA and protein sequence data. Phylogenomic studies of Neoaves, a large clade of birds (>9000 species) that first diversified near the Cretaceous–Paleogene boundary, have yielded an array of robustly supported, contradictory relationships among deep lineages. Here, we reanalyzed a large RI matrix for birds using recently proposed quartet-based coalescent methods that enable inference of large species trees including branch lengths in coalescent units, clade-support, statistical tests for gene flow, and combined analysis with DNA-sequence-based gene trees. Genome-scale coalescent analyses revealed extremely short branches at the base of Neoaves, meager branch support, and limited congruence with previous work at the most challenging nodes. Despite widespread topological conflicts with DNA-sequence-based trees, combined analyses of RIs with thousands of gene trees show emergent support for multiple higher-level clades (Columbea, Passerea, Columbimorphae, Otidimorphae, Phaethoquornithes). RIs express asymmetrical support for deep relationships within the subclade Afroaves that hints at ancient gene flow involving the owl lineage (Strigiformes). Because DNA-sequence data are challenged by gene tree-reconstruction error, analysis of RIs represents one approach for improving gene tree-based methods when divergences are deep, internodes are short, terminal branches are long, and introgressive hybridization further confounds species–tree inference. [ABSTRACT FROM AUTHOR]

Background: Phylogenetic networks are mathematical models of evolutionary processes involving reticulate events such as hybridization, recombination, or horizontal gene transfer. One of the crucial notions in phylogenetic network modelling is displayed tree, which is obtained from a network by removing a set of reticulation edges. Displayed trees may represent an evolutionary history of a gene family if the evolution is shaped by reticulation events. Results: We address the problem of inferring an optimal tree displayed by a network, given a gene tree G and a tree-child network N, under the deep coalescence and duplication costs. We propose an O(mn)-time dynamic programming algorithm (DP) to compute a lower bound of the optimal displayed tree cost, where m and n are the sizes of G and N, respectively. In addition, our algorithm can verify whether the solution is exact. Moreover, it provides a set of reticulation edges corresponding to the obtained cost. If the cost is exact, the set induces an optimal displayed tree. Otherwise, the set contains pairs of conflicting edges, i.e., edges sharing a reticulation node. Next, we show a conflict resolution algorithm that requires 2 r + 1 - 1 invocations of DP in the worst case, where r is the number of reticulations. We propose a similar O (2 k m n) -time algorithm for level-k tree-child networks and a branch and bound solution to compute lower and upper bounds of optimal costs. We also extend the algorithms to a broader class of phylogenetic networks. Based on simulated data, the average runtime is Θ (2 0.543 k m n) under the deep-coalescence cost and Θ (2 0.355 k m n) under the duplication cost. Conclusions: Despite exponential complexity in the worst case, our algorithms perform significantly well on empirical and simulated datasets, due to the strategy of resolving internal dissimilarities between gene trees and networks. Therefore, the algorithms are efficient alternatives to enumeration strategies commonly proposed in the literature and enable analyses of complex networks with dozens of reticulations. [ABSTRACT FROM AUTHOR]

Divergence time estimation from multilocus genetic data has become common in population genetics and phylogenetics. We present a new Bayesian inference method that treats the divergence time as a random variable. The divergence time is calculated from an assembly of splitting events on individual lineages in a genealogy. The time for such a splitting event is drawn from a hazard function of the truncated normal distribution. This allows easy integration into the standard coalescence framework used in programs such as Migrate. We explore the accuracy of the new inference method with simulated population splittings over a wide range of divergence time values and with a reanalysis of a dataset of 5 populations consisting of 3 present-day populations (Africans, Europeans, Asian) and 2 archaic samples (Altai and Ust'Isthim). Evaluations of simple divergence models without subsequent geneflow show high accuracy, whereas the accuracy of the results of isolation with migration models depends on the magnitude of the immigration rate. High immigration rates lead to a time of the most recent common ancestor of the sample that, looking backward in time, predates the divergence time. Even with many independent loci, accurate estimation of the divergence time with high immigration rates becomes problematic. Our comparison to other software tools reveals that our lineage-switching method, implemented in Migrate, is comparable to IMa2p. The software Migrate can run large numbers of sequence loci (>1,000) on computer clusters in parallel. [ABSTRACT FROM AUTHOR]

The largest and most economically important conifer genus Pinus is widespread in the northern hemisphere. Comprehensive phylogenies relying on complete chloroplast gene sequences are now available for the entire genus. However, phylogenetic relationships remain unresolved for certain lineages. One such example, which is also inconsistent in terms of biogeography, is within the subsection Pinus and includes five taxa: Pinus densiflora, P. nigra, P. resinosa, P. sylvestris and P. mugo / uncinata species complex. In this study, we use this clade as an example to explain weak support in phylogenetic studies of closely related pine species and show that some of the most popular genetic markers, namely the chloroplast DNA barcoding sequences matK, psbAtrnH and rbcL, are not recommended for species identification purposes in European pines. In addition, we show that matK and psbA-trnH contain contradicting phylogenetic signals in some of the most economically important pine species. [ABSTRACT FROM AUTHOR]

The Gastropoda contains 80% of existing mollusks and is the most diverse animal class second only to the Insecta. However, the deep phylogeny of gastropods has been controversial for a long time. Especially the position of Patellogastropoda is a major uncertainty. Morphology and some mitochondria studies concluded that Patellogastropoda is likely to be sister to all other gastropods (Orthogastropoda hypothesis), while transcriptomic and other mitogenomic studies indicated that Patellogastropoda and Vetigastropoda are sister taxa (Psilogastropoda). With the release of high-quality genomes, orthologous genes can be better identified and serve as powerful candidates for phylogenetic analysis. The question is, given the current limitations on the taxon sampling side, how many markers are needed to provide robust results. Here, we identified single-copy orthologous genes (SOGs) from 14 gastropods species with whole genomes available which cover five main gastropod subclasses. We generated different datasets from 395 to 1610 SOGs by allowing species missing in different levels. We constructed gene trees of each SOG, and inferred species trees from different collections of gene trees. We found as the number of SOGs increased, the inferred topology changed from Patellogastropoda being sister to all other gastropods to Patellogastropoda being sister to Vetigastropoda + Neomphalina (Psilogastropoda s.l.), with considerable support. Our study thus rejects the Orthogastropoda concept showing that the selection of the representative species and use of sufficient informative sites greatly influence the analysis of deep gastropod phylogeny. [ABSTRACT FROM AUTHOR]

Abstract Background Inferring phylogenetic relationships of polyploid species and their diploid ancestors (leading to reticulate phylogenies in the case of an allopolyploid origin) based on multi-locus sequence data is complicated by the unknown assignment of alleles found in polyploids to diploid subgenomes. A parsimony-based approach to this problem has been proposed by Oberprieler et al. (Methods Ecol Evol 8:835–849, 2017), however, its implementation is of limited practical value. In addition to previously identified shortcomings, it has been found that in some cases, the obtained results barely satisfy the applied criterion. To be of better use to other researchers, a reimplementation with methodological refinement appears to be indispensable. Results We present the AllCoPol package, which provides a heuristic method for assigning alleles from polyploids to diploid subgenomes based on the Minimizing Deep Coalescences (MDC) criterion in multi-locus sequence datasets. An additional consensus approach further allows to assess the confidence of phylogenetic reconstructions. Simulations of tetra- and hexaploids show that under simplifying assumptions such as completely disomic inheritance, the topological errors of reconstructed phylogenies are similar to those of MDC species trees based on the true allele partition. Conclusions AllCoPol is a Python package for phylogenetic reconstructions of polyploids offering enhanced functionality as well as improved usability. The included methods are supplied as command line tools without the need for prior programming knowledge.

Abstract The classical gene and species tree reconciliation, used to infer the history of gene gain and loss explaining the evolution of gene families, assumes an independent evolution for each family. While this assumption is reasonable for genes that are far apart in the genome, it is not appropriate for genes grouped into syntenic blocks, which are more plausibly the result of a concerted evolution. Here, we introduce the Super-Reconciliation problem which consists in inferring a history of segmental duplication and loss events (involving a set of neighboring genes) leading to a set of present-day syntenies from a single ancestral one. In other words, we extend the traditional Duplication-Loss reconciliation problem of a single gene tree, to a set of trees, accounting for segmental duplications and losses. Existency of a Super-Reconciliation depends on individual gene tree consistency. In addition, ignoring rearrangements implies that existency also depends on gene order consistency. We first show that the problem of reconstructing a most parsimonious Super-Reconciliation, if any, is NP-hard and give an exact exponential-time algorithm to solve it. Alternatively, we show that accounting for rearrangements in the evolutionary model, but still only minimizing segmental duplication and loss events, leads to an exact polynomial-time algorithm. We finally assess time efficiency of the former exponential time algorithm for the Duplication-Loss model on simulated datasets, and give a proof of concept on the opioid receptor genes.

Abstract Background Many of the commonly used methods for orthology detection start from mutually most similar pairs of genes (reciprocal best hits) as an approximation for evolutionary most closely related pairs of genes (reciprocal best matches). This approximation of best matches by best hits becomes exact for ultrametric dissimilarities, i.e., under the Molecular Clock Hypothesis. It fails, however, whenever there are large lineage specific rate variations among paralogous genes. In practice, this introduces a high level of noise into the input data for best-hit-based orthology detection methods. Results If additive distances between genes are known, then evolutionary most closely related pairs can be identified by considering certain quartets of genes provided that in each quartet the outgroup relative to the remaining three genes is known. A priori knowledge of underlying species phylogeny greatly facilitates the identification of the required outgroup. Although the workflow remains a heuristic since the correct outgroup cannot be determined reliably in all cases, simulations with lineage specific biases and rate asymmetries show that nearly perfect results can be achieved. In a realistic setting, where distances data have to be estimated from sequence data and hence are noisy, it is still possible to obtain highly accurate sets of best matches. Conclusion Improvements of tree-free orthology assessment methods can be expected from a combination of the accurate inference of best matches reported here and recent mathematical advances in the understanding of (reciprocal) best match graphs and orthology relations. Availability Accompanying software is available at https://github.com/david-schaller/AsymmeTree .

Tree reconciliation costs are a popular choice to account for the discordance between the evolutionary history of a gene family (i.e., a gene tree), and the species tree through which this family has evolved. This discordance is accounted for by the minimum number of postulated evolutionary events necessary for reconciling the two trees. Such events include gene duplication, loss, and deep coalescence, and are used to define different types of tree reconciliation costs. For example, the duplication-loss cost for a gene tree and species tree accounts for the minimum number of gene duplications and losses necessary to reconcile these trees. Fundamental to the understanding of how gene trees and species trees relate to each other are the diameters of tree reconciliation costs. While such diameters have been well-researched, still absent from these studies are the unconstrained diameters for two of the classic tree reconciliation costs, namely the duplication-loss cost and the loss cost. Here, we show the essential mathematical properties of these diameters and provide efficient solutions for computing them. Finally, we analyze the distributions of these diameters using simulated datasets. [ABSTRACT FROM AUTHOR]

Abstract Species networks generalize the notion of species trees to allow for hybridization or other lateral gene transfer. Under the network multispecies coalescent model, individual gene trees arising from a network can have any topology, but arise with frequencies dependent on the network structure and numerical parameters. We propose a new algorithm for statistical inference of a level-1 species network under this model, from data consisting of gene tree topologies, and provide the theoretical justification for it. The algorithm is based on an analysis of quartets displayed on gene trees, combining several statistical hypothesis tests with combinatorial ideas such as a quartet-based intertaxon distance appropriate to networks, the NeighborNet algorithm for circular split systems, and the Circular Network algorithm for constructing a splits graph.