Search

For a pair consisting of a gene tree and a species tree, the ancestral configurations at an internal node of the species tree are the distinct sets of gene lineages that can be present at that node. Ancestral configurations appear in computations of gene tree probabilities under evolutionary models conditional on fixed species trees, and the enumeration of root ancestral configurations -- ancestral configurations at the root of the species tree -- assists in describing the complexity of these computations. In the case that the gene tree matches the species tree in topology, we study the distribution of the number of root ancestral configurations of a random labeled tree topology under each of two models., 28 pages, 9 figures

The Kingman coalescent process is a classical model of gene genealogies in population genetics. It generates Yule-distributed, binary ranked tree topologies - also called histories - with a finite number of n leaves, together with n-1 exponentially distributed time lengths: one for each layer of the history. Using a discrete approach, we study the lengths of the external branches of Yule distributed histories, where the length of an external branch is defined as the rank of its parent node. We study the multiplicity of external branches of given length in a random history of n leaves. A correspondence between the external branches of the ordered histories of size n and the non-peak entries of the permutations of size n-1 provides easy access to the length distributions of the first and second longest external branches in a random Yule history and coalescent tree of size n. The length of the longest external branch is also studied in dependence of root balance of a random tree. As a practical application, we compare the observed and expected number of mutations on the longest external branches in samples from natural populations.

Compact coalescent histories are combinatorial structures that describe for a given gene tree G and species tree S possibilities for the numbers of coalescences of G that take place on the various branches of S. They have been introduced as a data structure for evaluating probabilities of gene tree topologies conditioning on species trees, reducing computation time compared to standard coalescent histories. When gene trees and species trees have a matching labeled topology $$G=S=t$$ , the compact coalescent histories of t are encoded by particular integer labelings of the branches of t, each integer specifying the number of coalescent events of G present in a branch of S. For matching gene trees and species trees, we investigate enumerative properties of compact coalescent histories. We report a recursion for the number of compact coalescent histories for matching gene trees and species trees, using it to study the numbers of compact coalescent histories for small trees. We show that the number of compact coalescent histories equals the number of coalescent histories if and only if the labeled topology is a caterpillar or a bicaterpillar. The number of compact coalescent histories is seen to increase with tree imbalance: we prove that as the number of taxa n increases, the exponential growth of the number of compact coalescent histories follows $$4^n$$ in the case of caterpillar or bicaterpillar labeled topologies and approximately $$3.3302^n$$ and $$2.8565^n$$ for lodgepole and balanced topologies, respectively. We prove that the mean number of compact coalescent histories of a labeled topology of size n selected uniformly at random grows with $$3.3750^n$$ . Our results contribute to the analysis of the computational complexity of algorithms for computing gene tree probabilities, and to the combinatorial study of gene trees and species trees more generally.

The Kingman coalescent process is a classical model of gene genealogies in population genetics. It generates Yule-distributed, binary ranked tree topologies—also calledhistories—with a finite number ofnleaves, together withn−1 exponentially distributed time lengths: one for each each layer of the history. Using a discrete approach, we study the lengths of the external branches of Yule distributed histories, where the length of an external branch is defined as the rank of its parent node. We study the multiplicity of external branches of given length in a random history ofnleaves. A correspondence between the external branches of the ordered histories of sizenand the non-peak entries of the permutations of sizen−1 provides easy access to the length distributions of the first and second longest external branch in a random Yule history and coalescent tree of sizen. The length of the longest external branch is also studied in dependence of root balance of a random tree. As a practical application, we compare the observed and expected number of mutations on the longest external branches in samples from natural populations.

A ranked tree topology is a tree topology with a temporal ordering of its coalescence events. Under the multispecies coalescent model, we consider ranked gene tree topologies realized along the branches of ranked species trees, where one gene copy is sampled for each species. Previous results have demonstrated that for almost all ranked species tree topologies with at least five species, there exists a set of branch lengths such that the maximally probable ranked gene tree topologies-those generated with the highest probability under the model-do not match the species tree ranked topology. Here, we focus on the agreement of a ranked species tree with its maximally probable ranked gene tree topologies in terms of their unranked topology, that is, disregarding the ordering of the coalescence events. We show that although the set of maximally probable ranked gene tree topologies for a ranked species tree can contain ranked trees with different unranked topologies, at least one of these maximal ranked gene tree topologies must have the same unranked topology as the species tree. Our results contribute to the study of the relationships between gene trees and species trees.

We examine combinatorial parameters of three models of random lattice walks with up and down steps. In particular, we study the height $$y_i$$ measured after i up-steps in a random weighted Dyck path of size (semilength) n. For a fixed integer $$w \in \{0,1,2\}$$ , the considered weighting scheme assigns to each Dyck path of size n a weight $$\prod _{i=1}^n y_i^w$$ that depends on the height of the up-steps of the path. We investigate the expected value $${\text{E}}_n(y_i)$$ of the height $$y_i$$ in a random weighted Dyck path of size n, providing exact formulas for $${\text{E}}_n(y_i)$$ and $${\text{E}}_n(y_i^2)$$ when $$w=0,1$$ , and estimates of the mean of $$y_i$$ for $$w=2$$ . Denoting by $$i^*(n)$$ the position i where $${\text{E}}_n(y_i)$$ reaches its maximum $${\text{m}}(n)$$ , our calculations indicate that, when n becomes large, the pair $$\big (i^*(n), {\text{m}}(n)\big )$$ grows like $$\big ( n/2 , 2\sqrt{n/\pi } \big )$$ if $$w=0$$ , $$\big ( 3n/4 , n/2 \big )$$ if $$w=1$$ , and $$\big ( (9+\sqrt{17})n/16 , (1+\sqrt{17})n/8 \big )$$ if $$w=2$$ . These results also contribute to the study of the variability of the number of “coalescent histories”: structures used in models of gene tree evolution to encode the combinatorially different configurations of a gene tree topology along the branches of a species tree. Relationships with other combinatorial and algebraic structures, such as alternating permutations and Meixner polynomials, are also discussed.

An ancestral configuration is one of the combinatorially distinct sets of gene lineages that, for a given gene tree, can reach a given node of a specified species tree. Ancestral configurations have appeared in recursive algebraic computations of the conditional probability that a gene tree topology is produced under the multispecies coalescent model for a given species tree. For matching gene trees and species trees, we study the number of ancestral configurations, considered up to an equivalence relation introduced by Wu (Evolution 66:763-775, 2012) to reduce the complexity of the recursive probability computation. We examine the largest number of non-equivalent ancestral configurations possible for a given tree size n. Whereas the smallest number of non-equivalent ancestral configurations increases polynomially with n, we show that the largest number increases with [Formula: see text], where k is a constant that satisfies [Formula: see text]. Under a uniform distribution on the set of binary labeled trees with a given size n, the mean number of non-equivalent ancestral configurations grows exponentially with n. The results refine an earlier analysis of the number of ancestral configurations considered without applying the equivalence relation, showing that use of the equivalence relation does not alter the exponential nature of the increase with tree size.

Coalescent histories provide lists of species tree branches on which gene tree coalescences can take place, and their enumerative properties assist in understanding the computational complexity of calculations central in the study of gene trees and species trees. Here, we solve an enumerative problem left open by Rosenberg ( IEEE/ACM Transactions on Computational Biology and Bioinformatics 10: 1253-1262, 2013) concerning the number of coalescent histories for gene trees and species trees with a matching labeled topology that belongs to a generic caterpillar-like family. By bringing a generating function approach to the study of coalescent histories, we prove that for any caterpillar-like family with seed tree $t$ , the sequence $(h_n)_{n\ge 0}$ describing the number of matching coalescent histories of the $n$ th tree of the family grows asymptotically as a constant multiple of the Catalan numbers. Thus, $h_n \sim \beta _t c_n$ , where the asymptotic constant $\beta _t > 0$ depends on the shape of the seed tree $t$ . The result extends a claim demonstrated only for seed trees with at most eight taxa to arbitrary seed trees, expanding the set of cases for which detailed enumerative properties of coalescent histories can be determined. We introduce a procedure that computes from $t$ the constant $\beta _t$ as well as the algebraic expression for the generating function of the sequence $(h_n)_{n\ge 0}$ .

The neighbor-joining algorithm for phylogenetic inference (NJ) has been seen to have three specific properties when applied to distance matrices that contain an admixed taxon: (1) antecedence of clustering, in which the admixed taxon agglomerates with one of its source taxa before the two source taxa agglomerate with each other; (2) intermediacy of distances, in which the distance on an inferred NJ tree between an admixed taxon and either of its source taxa is smaller than the distance between the two source taxa; and (3) intermediacy of path lengths, in which the number of edges separating the admixed taxon and either of its source taxa is less than or equal to the number of edges between the source taxa. We examine the behavior of neighbor-joining on distance matrices containing an admixed group, investigating the occurrence of antecedence of clustering, intermediacy of distances, and intermediacy of path lengths. We first mathematically predict the frequency with which the properties are satisfied for a labeled unrooted binary tree selected uniformly at random in the absence of admixture. We then introduce a taxon constructed by a linear admixture of distances from two source taxa, examining three admixture scenarios by simulation: a model in which distance matrices are chosen at random, a model in which an admixed taxon is added to a set of taxa that reflect tree-like evolution, and a model that introduces a perturbation of the tree-like scenario. In contrast with previous conjectures, we observe that the three properties are sometimes violated by distance matrices that include an admixed taxon. However, we also find that they are satisfied more often than is expected by chance when the distance matrix contains an admixed taxon, especially when evolution among the non-admixed taxa is tree-like. The results contribute to a deeper understanding of the nature of evolutionary trees constructed from data that do not necessarily reflect a tree-like evolutionary process.

Given a gene tree and a species tree, ancestral configurations represent the combinatorially distinct sets of gene lineages that can reach a given node of the species tree. They have been introduced as a data structure for use in the recursive computation of the conditional probability under the multispecies coalescent model of a gene tree topology given a species tree, the cost of this computation being affected by the number of ancestral configurations of the gene tree in the species tree. For matching gene trees and species trees, we obtain enumerative results on ancestral configurations. We study ancestral configurations in balanced and unbalanced families of trees determined by a given seed tree, showing that for seed trees with more than one taxon, the number of ancestral configurations increases for both families exponentially in the number of taxa n. For fixed n, the maximal number of ancestral configurations tabulated at the species tree root node and the largest number of labeled histories possible for a labeled topology occur for trees with precisely the same unlabeled shape. For ancestral configurations at the root, the maximum increases with \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$ k_0^n$$ \end{document}, where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${{k_0}} \approx \bf1.5028$$ \end{document} is a quadratic recurrence constant. Under a uniform distribution over the set of labeled trees of given size, the mean number of root ancestral configurations grows with \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\sqrt {\bf 3 / 2} { {\bf ( 4 / 3 ) ^n}}$$ \end{document} and the variance with ∼\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${{\bf 1.4048 ( 1.8215 )} ^n}$$ \end{document}. The results provide a contribution to the combinatorial study of gene trees and species trees.

We define the notion of a Catalan pair (which is a pair of binary relations (S,R) satisfying certain axioms) with the aim of giving a common language to several combinatorial interpretations of Catalan numbers. We show, in particular, that the second component R uniquely determines the pair, and we give a characterization of R in terms of forbidden configurations. We also propose some generalizations of Catalan pairs arising from some slight modifications of (some of the) axioms.

We define the notion of a Catalan pair, which is a pair of (strict) order relations ( S , R ) satisfying certain axioms. We show that Catalan pairs of size n are counted by Catalan numbers. We study some combinatorial properties of the relations R and S. In particular, we show that the second component R uniquely determines the pair, and we give a characterization of the poset R in terms of forbidden configurations. We also propose some generalizations of Catalan pairs arising from the modification of one of the axioms.

Coalescent histories are combinatorial structures that describe for a given gene tree and species tree the possible lists of branches of the species tree on which the gene tree coalescences take place. Properties of the number of coalescent histories for gene trees and species trees affect a variety of probabilistic calculations in mathematical phylogenetics. Exact and asymptotic evaluations of the number of coalescent histories, however, are known only in a limited number of cases. Here we introduce a particular family of species trees, the \emph{lodgepole} species trees $(\lambda_n)_{n\geq 0}$, in which tree $\lambda_n$ has $m=2n+1$ taxa. We determine the number of coalescent histories for the lodgepole species trees, in the case that the gene tree matches the species tree, showing that this number grows with $m!!$ in the number of taxa $m$. This computation demonstrates the existence of tree families in which the growth in the number of coalescent histories is faster than exponential. Further, it provides a substantial improvement on the lower bound for the ratio of the largest number of matching coalescent histories to the smallest number of matching coalescent histories for trees with $m$ taxa, increasing a previous bound of $(\sqrt{\pi} / 32)[(5m-12)/(4m-6)] m \sqrt{m}$ to $[ \sqrt{m-1}/(4 \sqrt{e}) ]^{m}$. We discuss the implications of our enumerative results for phylogenetic computations.

Analysis of probability distributions conditional on species trees has demonstrated the existence of anomalous ranked gene trees (ARGTs), ranked gene trees that are more probable than the ranked gene tree that accords with the ranked species tree. Here, to improve the characterization of ARGTs, we study enumerative and probabilistic properties of two classes of ranked labeled species trees, focusing on the presence or avoidance of certain subtree patterns associated with the production of ARGTs. We provide exact enumerations and asymptotic estimates for cardinalities of these sets of trees, showing that as the number of species increases without bound, the fraction of all ranked labeled species trees that are ARGT-producing approaches 1. This result extends beyond earlier existence results to provide a probabilistic claim about the frequency of ARGTs.

The Yule process generates a class of binary trees which is fundamental to population genetic models and other applications in evolutionary biology. In this paper, we introduce a family of sub-classes of ranked trees, called Ω-trees, which are characterized by imbalance of internal nodes. The degree of imbalance is defined by an integer 0 ≤ ω . For caterpillars, the extreme case of unbalanced trees, ω = 0 . Under models of neutral evolution, for instance the Yule model, trees with small ω are unlikely to occur by chance. Indeed, imbalance can be a signature of permanent selection pressure, such as observable in the genealogies of certain pathogens. From a mathematical point of view it is interesting to observe that the space of Ω-trees maintains several statistical invariants although it is drastically reduced in size compared to the space of unconstrained Yule trees. Using generating functions, we study here some basic combinatorial properties of Ω-trees. We focus on the distribution of the number of subtrees with two leaves. We show that expectation and variance of this distribution match those for unconstrained trees already for very small values of ω.

International audience; We present the design and the fabrication of a dual-wavelength micro-photonic resonator combining a photonic crystal membrane (PCM) and a vertical Fabry Perot (FP) cavity where the former is embedded in the latter. A strong optical coupling between a PCM Γ-point Bloch mode and a FP mode at the same frequency can be used to provide a dual-wavelength device with a frequency difference which is analysed in terms of modes overlapping. We propose and demonstrate a process flow that can be used to provide such a device. Optical reflectivity characterisation is presented for a monolithic device and photoluminescence dual-wavelength spontaneous emission is demonstrated in an extended vertical cavity. Finally the dual-mode laser emission stability is examined with numerical Monte Carlo simulation.

A permutominide is a set of cells in the plane satisfying special connectivity constraints and uniquely defined by a pair of permutations. It naturally generalizes the concept of permutomino, recently investigated by several authors and from different points of view [1, 2, 4, 6, 7]. In this paper, using bijective methods, we determine the enumeration of various classes of convex permutominides, including, parallelogram, directed convex, convex, and row convex permutominides. As a corollary we have a bijective proof for the number of convex permutominoes, which was still an open problem.

There is a deep connection between permutations and trees. Certain sub-structures of permutations, called sub-permutations, bijectively map to sub-trees of binary increasing trees. This opens a powerful tool set to study enumerative and probabilistic properties of sub-permutations and to investigate the relationships between 'local' and 'global' features using the concept of pattern avoidance. First, given a pattern {\mu}, we study how the avoidance of {\mu} in a permutation {\pi} affects the presence of other patterns in the sub-permutations of {\pi}. More precisely, considering patterns of length 3, we solve instances of the following problem: given a class of permutations K and a pattern {\mu}, we ask for the number of permutations $\pi \in Av_n(\mu)$ whose sub-permutations in K satisfy certain additional constraints on their size. Second, we study the probability for a generic pattern to be contained in a random permutation {\pi} of size n without being present in the sub-permutations of {\pi} generated by the entry $1 \leq k \leq n$. These theoretical results can be useful to define efficient randomized pattern-search procedures based on classical algorithms of pattern-recognition, while the general problem of pattern-search is NP-complete.

Using the notion of series parallel interval order, we propose a unified setting to describe Dyck lattices and Tamari lattices (two well-known lattice structures on Catalan objects) in terms of basic notions of the theory of posets. As a consequence of our approach, we find an extremely simple proof of the fact that the Dyck order is a refinement of the Tamari one. Moreover, we provide a description of both the weak and the strong Bruhat order on 312-avoiding permutations, by recovering the proof of the fact that they are isomorphic to the Tamari and the Dyck order, respectively; our proof, which simplifies the existing ones, relies on our results on series parallel interval orders.

We consider exact enumerations and probabilistic properties of ranked trees when generated under the random coalescent process. Using a new approach, based on generating functions, we derive several statistics such as the exact probability of finding k cherries in a ranked tree of fixed size n. We then extend our method to consider also the number of pitchforks. We find a recursive formula to calculate the joint and conditional probabilities of cherries and pitchforks when the size of the tree is fixed. These results provide insights into structural properties of coalescent trees under the model of neutral evolution.

Let the records of a permutation σ be its left-right minima, right-left minima, left-right maxima and right-left maxima. Conversely let a point ( i , j ) with j = σ ( i ) be an internal point of σ if it is not a record. Permutations without internal points have recently attracted attention under the name square permutations. We consider here the enumeration of permutations with a fixed number of internal points. We show that for each fixed i the generating function of permutations with i internal points with respect to the size is algebraic of degree 2. More precisely it is a rational function in the Catalan generating function. Our approach is constructive, yielding a polynomial uniform random sampling algorithm, and it can be refined to enumerate permutations with respect to each of the four types of records.

A Catalan pair is a pair of binary relations (S,R) satisfying certain axioms. These objects are enumerated by the well-known Catalan numbers, and have been introduced with the aim of giving a common language to most of the structures counted by Catalan numbers. Here, we give a simple method to pass from the recursive definition of a generic Catalan structure to the recursive definition of the Catalan pair on the same structure, thus giving an automatic way to interpret Catalan structures in terms of Catalan pairs. We apply our method to many well-known Catalan structures, focusing on the meaning of the relations S and R in each considered case., Comment: 14 pages

A permutomino of size n is a polyomino determined by particular pairs $(\pi_1, \pi_2)$ of permutations of length $n$, such that $\pi_1(i) \neq \pi_2(i)$, for $1 \leq i \leq n$. In this paper we consider the class of convex permutominoes which are symmetric with respect to the diagonal $x = y$. We determine the number of these permutominoes according to the dimension and we characterize the class of permutations associated to these objects as particular involutions of length $n$., Les permutominos de taille $n$ sont des polyominos déterminés par certaines paires de permutations $(\pi_1,\pi_2)$ de taille $n$, telles que $\pi_1(i) \neq \pi_2(i)$, pour tout $1 \leq i \leq n$. Dans cet article nous considérons la classe des permutominos convexes qui sont symétriques par rapport à la diagonale $x=y$. Nous déterminons le nombre de ces permutominos en fonction de leur taille et nous caractérisons la classe des permutations associées à ces objets comme un certain ensemble d'involutions de taille $n$.

In this paper we determine a closed formula for the number of convex permutominoes of size $n$. We reach this goal by providing a recursive generation of all convex permutominoes of size $n+1$ from the objects of size $n$, according to the ECO method, and then translating this construction into a system of functional equations satisfied by the generating function of convex permutominoes. As a consequence we easily obtain also the enumeration of some classes of convex polyominoes, including stack and directed convex permutominoes.

International audience; Monte Carlo markovian models of a dual-mode semiconductor laser with quantum well (QW) or quantum dot (QD) active regions are proposed. Accounting for carriers and photons as particles that may exchange energy in the course of time allows an ab initio description of laser dynamics such as the mode competition and intrinsic laser noise. We used these models to evaluate the stability of the dual-mode regime when laser characteristics are varied: mode gains and losses, non-radiative recombination rates, intraband relaxation time, capture time in QD, transfer of excitation between QD via the wetting layer... As a major result, a possible steady-state dual-mode regime is predicted for specially designed QD semiconductor lasers thereby acting as a CW microwave or terahertz- beating source whereas it does not occur for QW lasers.